Тізімдер. Циклдік тізімдер. Ортогоналды тізімдер 4 страница

⇐ ПредыдущаяСтр 4 из 15Следующая ⇒

Ақпараттық жүйелердің қауіпсіздігі жөнінде негізгі стандарттар 1983(АҚШ) шыққан. “Оранжевая книга” деп аталатын “Критерий, оценки надежных компьютернх систем” кітабында негізі қаланған. Осы кітаптың талабына сәйкес мынадай жүйе қауіпсіз деп саналады: ақпаратқа қол жетіді бақылайтын қауіпсіздікті сақтау механизмдері арқылы арнаулы өкілеттілігі бар тұлғалар немесе олардың атынан орыдалатын процесстер ғана информацияны оқуға, жазуға, құруға, жоюға мүмкіндік беретін жүйе. Бұл кітата қауіпсіздікті сақтау деңгейлері көрсетілген: А- ең жоғары, Д- ең төмен деңгей (А, В, С, Д). Д класына басқа кластардың талабына жатпайтын барлық кластар жатады (А, В, С).

С- екі ішкі деңгейге бөлінеді: с1 және с2, бұнда барлық оқиғалар есепке алынады (қауіпсіздікке байланысты), қатынауды бақылау таңдамалы (іріктемелі) түрде болады.

С1- деректерді қолданушының қателерінен сақтайды (қаскүнемдерден сақтай алмайды).

С2- құпия кіру құралы бар, ол арнаулы қайталанбас (уникальный) есім және пароль арқылы қолданушыларды айқындап, жүйеге кіруге рұқсат береді.

Қатынауды іріетеу түрде бақылау С деңгейінде рұқсаттың иесіне, кім ресурсқа еіре алады және ол онымен не істей алатыны туралы анықтауға мүмкіндік береді. Ресурстың иесі оны қолданушыға берілген немесе топқа берілген қатынау құқықтары арқылы іске асады.

Есепке алу және қадағалау құралдары жүйелік ресурстарға қол жеткізу, жасау және жоюға байланысты түолі әрекеттерді немесе қауіпсіздікке байланысты түрлі оқиғаларда анықтап, оны есепке алады. Жадыны қорғау барысында жады қайталап қолданудың алдында инициализацияланады. Бұл деңгейде жүйеде қолданушының қателерінен қорғаныс жоқ, бірақ олардың әрекеттері аудит құралдры арқылыжазылған журналмен бақыланады.

В деңгейі. Белгіліленген деректерге және қолданушылврды категорияларға бөлу үшін негізделген, яғни қатынауды мандатты бақылау іске асады мандатный контроль доступа. Әр қолданушыға қорғаныс рейтингі беріледі. Осы рейтенкке сәйкес деректер базасына қатыный алады. Бұл деңгейде жүйе қолданушының қателерінен қорғана алады (Ұлттық Қауіпсіздік Комитетінде қолданылады).

А деңгейі ең жоғарғы деңгей. Мұнда В деңгейінің барлық талаптарына қосымша жүйенің қауіпсіздігін сақтауды қамтамасыз ететін формаларды математикалық негізделген дәлелдеулердің орындалуын талап етеді. Бұл деңгей ядролық құралдарды басқару жүйелерінде қолданады.ДҚБЖ-ның привилегиясы екі категорияға бөлінеді:

1. қауіпсіздік

2. қатынау

Объектілерге байланысты қатынау привилегиясы 5-ке бөлінеді:

1. кестелер және көріністер

2. процедуралар

3. деректер базасы

4. деректер базасының сервері

5. оқиғалар

Кестелер мен көріністер мынадай қатынау құқықтары арқылы басқарылады:

Select- деректерді алу (таңдау)

Insert- деректерді қосуға құқық

Delete- деректерді жоюға құқық

Update- деректерді жаңалауға құқық.

Деректер құрылымы. Динамикалық және статикалық құрылымдар.

Деректер құрылымы – қолданушының деректерді бейнелеуге деген көзқарасын сипаттайды.

Деректер құрылымы, динамикалық және статикалық құрылымдар программалау тілдеріндегідей («Алгоритмдер және деректер құрылымы» атты пәннен таныссыздар) ЭЕМ жадысында сақталатын деректер, нөлдер мен бірлер (биттер) жиыны түрінде сипатталады. Биттер тізбектей жалғанады: байттар, сөз және т.с.с. Оперативтік жадының бір байт немесе сөз сиятын әрбір бөлігіне реттік нөмір (адресі) меншіктеледі. Кез-келген деректер келесі екі типтің біреуіне жатады: сипатталу формасы ЭЕМ-нің архитектурасы бойынша анықталатын негізгі (қарапайым) немесе нақты есептерді шешу үшін қолданушы құрастыратын күрделі тип.

Қарапайым тип деректері – бұл әрі қарай бөлшектеудің ешқандай мағынасы болмайтын, символдар, сандар тағы басқа элементтер. Элементарлы деректерден, құрылымды деректердің (күрделі тип) құрылады.

Сызықты құрылымдар:

· Массив (шектелген анықталу облысы бар функция) – бір типті элементтердің қарапайым жиынтығы, бір типті деректер тобымен амалдар орындау құралы. Массивтің жекелеген элементтері индекс арқылы беріледі. Массив екі өлшемді, бір қлшемді және т.с.с. болуы мүмкін. Айнымалылы ұзындықты бір өлшемді массивтің әртүрлілігі ретінде сақина, стек және екіжақты кезек типті структура болады.

· Жазба (декарттық көбейтінді) - әртүрлі типтегі деректер элементінің жиынтығы. Қарапайым жағдайда жазбаларда, өрістер деп аталатын тұрақты элементтер саны бар болады. Біртекті структуралы жазбалар жиынтығы файл деп аталады. (Сыртқы жадыдағы деректер жиыны да файл деп аталады. Мысалы магниттік дискідегі). Файлдан жекелеген жазбаларды алып шығу мүмкіндігі болу үшін, әрбір жазбаға бірегей ат немесе нөмір беріледі, ол оның идентификаторы ретінде қызмет етеді және жеке өрісте жазылады. Бұл идентификаторды кілт деп атайды.

Массив немесе жазбалар түріндегі деректердің құрылымы ЭЕМ жадысында тұрақты көлем алып тұрады, сондықтан оларды статикалық структура деп атайды. Статикалық структураға жиын да жатады.

Сызықты құрылымдар өзінің ұзындығын өзгертуі мүмкін. Оларды динамикалық құрылым деп атайды. Оларға ағаш, тізім, нұсқау жатады.

Күрделі типтердің көптеген түрлері бар, бірақ үлкен практикалық материалдарда жүргізілген зерттеулер, олардың ішінен ең ортақтарын ерекшелеуге болатының айтады.

3. Хомскийдің формальдық тілдер иерархиясы

Хомский иерархиясы (Иерархия Хомского; chomsky hierarchy) — 1959 ж. Н. Хомский ұсынған формальдық тілдер иерархиясы: 0 тобы — рекурсивтік тізімделетін тілдер, 1 тобы — рекурсивті-қарабайыр функциялармен анықталатын тілдер, 2 және 3 топтар — қайталау және рекурсияның сәйкес түрдегі есептеу принциптерінің абстрактілі ұсынымын жасақтайтын тілдер. Дәлелдейміз бірінші екі теореманыңнормалыларды туралы КС-граматикті көрсетеміз . Әрбіреуііндеолар түрлерінде бекітеді , не барлық граматикалар эквиваленттік граматикасы ережелердің түріне шек қойылады.

Теорема 4.5.- Хомскидіңнормальді түрі. Мүмкін граматика кез келген КС-тілді туындайды, онда барлық ережелер түрі немесе терминалды емес ,а- терминалды .)

Дәлелдеу. Мейлі - грамматикасы және сәйкесінше теоремамен 4.4 біз эквиваленттік таба аламыз , сондайды , не жиын оны Р бірде бір шынжырды ережелерде асырмайды. Солай келгенде, егер ереже оң бөлімі бір символдан түзелсе, онда мына символ - терминал болады, және мына ереже қабылдауға болатын түрде орнында болады .

Екі элементті В жиынын және В-дан мән қабылдайтын екілік айнымалыларды қарастырайық. Оның элементтері жиі 0 және 1 деп белгіленеді, бірақта олар кәдімгі мағынадағы сандар емес (кейбір қасиеттері бойынша ұқсас). Екілік айнымалының ең кең тараған интерпретациясылогикалық: "ия" - "жоқ", "ақиқат" (А) - "жалған" (Ж). Бір уақытта екілік және арифметикалық шамалар және функциядан тұратын контексте, бұл интерпретация әдетте айқын түрде бекітіледі: мысалы, программалау тілінде арнайы айнымалы типі –мәні true және false болатын логикалық айнымалы енгізіледі. Арифметикалық мағынасы жоқ, 0 мен 1-ді формальді символдар ретінде қаастыра отырып, В = {0, 1} деп есептейік.

В жиынымен және онымен бірге орындалатын мүмкін болатын операциялардан құралған алгебра- логика алгебрасы деп аталады. n айнымалының логика алгебрасның функциясы (немесе логикалық алгебра) В-дағы n-ші операция деп аталады. Бірінші термин нақтырақ, бірақ екінші, әсіресе қосымшада кең таралған. Сонымен, f(x₁, ..., x_n) – логикалық функциясы – бұл 0,1 мәндерінқабылдайтын функция. Барлық логикалық функциялар жиыны - Р₂, n айнымалылы барлық логикалық функциялар жиыны - Р₂(n) деп белгілейміз.

k-элементі жиынмен бірге, онда орындалатын барлық операциялардан құралған алгебра k-мәнді логика алгебрасы, ал k-элементіжиындағы n-ші операция n – айнымалылардың k-мәнді логикалық функциясы деп аталады; барлық k-мәнді логикалық функциялар жиыны Р_kдеп белгіленеді.

n айнымалылы барлық логикалық функциялар кесте түрінде беріледі, сол бөлігінде айнымалылардың барлық 2ⁿ мәнді жиынтықтары (яғни n ұзындықты екілік векторлар), ал оң бөлігінде осы жиынтықтағы функциялардың мәндері тізілген. Мысалы, 1 кестеде үш айнымалылы функция берілсін. Функция f = l тең жиынтығы жиі f функциясының бірлік жиынтығы деп, ал сәйкесінше f = 0 жиынтық f нөлдік жиынтығы деп аталады.

№ 5 БИЛЕТ

1.Қарапайым рекурсиялар.

Рекурсия (өздігінен қайталану) – «өзіне-өзі» қатынайтын іс-әрекет. Екі түрлі рекурсия бар: 1) түзу рекурсиясы, процедура өзін-өзі шақырады; 2) жанама рекурсиясы, мұнда бір процедура екінші процедураны шақырады, ал бұл тура немесе жанама түрде бастапқы процедураны шақырады. Егер есеп рекуссивті есептеуіне жатса, рекурсияны пайдалануға болады. Кез келген есеп рекурсияда шығарылса, осы есеп сонымен қатар рекурсиясыз да шығарылады. Рекурсия түсінігімен «рекуррентті тізбектелу» түсінігі сәйкес келеді, мұндағы n мүшесін есептеу үшін рекурсия қолданылады. Бұл түсініктің анықтамасын анықтайық: сандық тізбектелу {x_k} рекурренттілік деп аталады, егер сонымен қатар, егер p=1 егер р=2: .

Рекурсивті алгоритмдер үлкен есепті бірнеше фрагменттерге бөледі және алгоритм әр фрагментке жеке орындалады. Мұндай алгоритмдерді қолдану тиімді, өйткені үлкен есеп шағын қарапайым түсінікті алгоримдерге бөледі. Рекурсивті алгоритмдердің күрделілігін талдау есепті бөліктерге бөлуге қажетті және әр бөлікте орындалуы тиіс және жеке есептелген нәтижелерді біріктіруге кететін операциялар санын санауды талап етеді. Осы ақпаратты және олардың бөліктері мен өлшемі туралы ақпаратты біріктіріп алгоритмнің күрделілігіне арналған реккуренттік қатынастарды шығара аламыз. Бұл реккуренттік қатынасты басқалармен салыстыруға болады. Рекурсияның бір түрі – функция мәнін осы функцияның бұдан бұрын есептелген мәндері арқылы есептеу. Мұндай тәсілді рекурренттік тәсіл деп те атайды. Мысал. cosх функциясын функционалдық қатарға (шексіз қосындыға) жіктеу формуласы:

Қатардың ерs-інен кем емес мүшелерінің қосындысын табу керек. (Ерs – қандай кіші болса да, есептеу дәлдігін білдіретін алдын ала берілген оң сан. Ерs дәлдігі бойынша табылған мән осы дәлдікпен алынған соsх мәні де болатыны математика курсынан белгілі.)

Нұсқау. Қатардың жалпы мүшесі (к=0, 1, 2,...): Жалпы, берілген есепті бастапқы берілгендер мен шешуі бірдей болатын оңайлатылған ішкі есепке ауыстыру (ол бәсеңдету стратегиясы деп аталады), ал кезегімен оны да осы сияқты басқа ішкі есепке ауыстыру процесі рекурсия деп аталады (Информатикада ішкі программаны қайталап өзін-өзі шақыру жағдайлары да жиі кездеседі. Мұндай тәсіл де рекурсия делінеді).

2 Сұлбалар және ішкі сұлбалар түсінігі. Деректер моделі түсінігі, түрлері

Схема- қандай да бір объекті құрылымының шартты символдар мен графиктік кескіні; кейбір логикалық операцияларды жүзеге асыратын логикалық элемент; мәліметтер базасы құрылымының арнама тізімі.

ДБ- ның бірініші итерациясы мынандай әрекеттер алгоритімінен тұрады:

- Деректерге сақтауға арналған объектілерді жасау;

- Кестелерді жасау;

- Кестені индентификациялау;

- Бағандардағы деректер типтерін анықтау;

- Бастапқы кілтті анықтау;

- Шектеулерді қосу;

- «көптің- көпке » байланысы үшін кестелерді құру;

- Индекстерді жасау;

- Көрсетімдерді жасау;

- ДБ- ның басқа объектілерін жасау;

- Жасалған физикалық моделдің дұрыстығын тексеру.

Ішкі схема – компьютерлік технология мүмкіндіктерімен анықталады.Ішкі схемадегеніміз – ол деректер базасының өзі. Деректтердің құрылымы бұл жағдайда нақты компьютерлік технологияға және деректерді өңдеуге қойылған тиімділік талаптарына тәуелді болады.

3 Алгоритмдік проблемалар: бостық, идентификациялау, тілдердің эквиваленттілігі.

ПРОБЛЕМАЛАР:Формалды грамматикалардағы секілді, автоматтардың да өз алгоритмдік проблемалары бар. Оларға мыналар жатады:

Бостық проблемасы–берілген M автоматы үшін L(M)бос тіл бола ма,яғни , L(M)= Ø?

Шексіздік проблемасы – берілген M автоматы үшін L(M)шексіз тіл бола ма?

Тиістілік проблемасы – кез келген  тізбе берілген M автоматы танитын L(M)тіліне тиісті бола ма, яғни, L(M)?

Эквиваленттілік проблемасы – кез келген екі Mi және Mj (i≠j) автоматтарэквиваленттібола ма, яғни, L(Mi)=L(Mj)?

Тұйықтылық проблемасы – белгілі бір типтегі кез келген екі тілге жиындық амалдарды қолданғанда нәтижесі сол типке жататындығын анықтау.

Тоқтау проблемасы–берілген M автоматы үшін ол қосылғаннан кейін тоқтай ма жоқ па?

Дата добавления: 2018-08-06; просмотров: 459; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!