Детерминант емеске келтірейік.

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

Детерминант емес шеткі автоматты анықтау, жоғарыда көрсетілген детерминант шеткі автоматты анықтауға ұқсас болады, тек екі айырмашылығы болады:

δ – өту функциясы. Аргументтер – мағына және кіру символы, нәтижесінде – мағынаның көптігі (бос – болуы мүмкін).
Егер автомат q_iжағдайында болса,ал кіруге b символы енгізіледі, онда автомат δ(q_i, b) жиын мағынасының жағдайына өтеді. Егер автомат жиын {q_i}, жағдайында болса, онда ол жиын жағдайға өтеді.

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

2 – ші суретте жай детерминант емес шеткі автомат көрсетілген, 0 ден және 1 тізіміне рұқсат беретін бау көрсетілген және ол 00 аяқталады.

Тура осы автомат кесте түрінде:

Кесте 2. Тура осы детерминант емес шеткі автомат.

Оның жұмысын қарастырайық.

Мысалға, автомат кірісіне «100100» тізбек келіп тұрсын делік.

Дейін	Кіру	Суреттелуі	Кейін
		Автомат {q₀} жағдайындағы жиынында жұмыс істей бастайды.	{q₀}
{q₀}		q₀күй- жағдайынан 1 символына тек бір ғана өту болады, ал q₀ да.	{q₀}
{q₀}		q₀ күй жағдайынан 0 символына тек екі өту болады. q₀ ге және q₁ге.	{q₀, q₁}
{q₀, q₁}		q₀ күй жағдайынан 0 символына екі өту болады, q₀ге және q₁ге q1 күй – жағдайынан – бір өту бар, q₂ге. Өйткені автомат екі күй – жағдайда орналасқандықтан, жиындар қосылады.	{q₀,q₁,q₂}
{q₀, q₁, q₂}		Автомат 3 күй – жағдайда орналасқан, бірақ q₁ дан және q₂ ден 1 символ бойынша өтулер жоқ. Нәтижесінде тек q₀ қалады.	{q₀}
{q₀}		Т с.с.	{q₀, q₁}
{q₀, q₁}		Т с.с. Дәл осылай алынған жиын қалып – күйінде q₂ – кіру күй – жағдайы бар, автомат тізбекті мақұлдайды.	{q₀,q₁,q₂}

№ 13 БИЛЕТ

Жобалаудың негізгі әдістері.

Ақпараттық жүйені жобалау – ұзақ мерзімді және динамикалық үрдіс. Қазіргі уақытта қолданылатын жобалау технологиялары жүйені кезеңдік жасауды ұсынады. АЖӨЦ дегеніміз - ААЖ–ні (автоматтандырылған ақпараттық жүйе) жасау қажеттілігінен бастап оның келесі сатысына көшу уақытымен бітетін кезең.

АЖӨЦ (өмірлік цикл) келесі кезеңдерден тұрады:

1.Жоба алдындағы кезең;

2.Жобаны әзірлеу кезең;

3Жобаны пайдалануға беру кезеңі;

4.Жаңа сатыға көшу кезеңі

1.Жоба алдындағы кезеңде екі құжат дайындалады:

а) Техника - экономикалдық тұжырымдама (ТЭТ)

б) Техникалық тапсырма (ТТ)

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

Каскадты модельдің негізгі мінездемесі АЖ-ні әзірлеуді кезеңдерге бөлу, бір кезеңнен екінші кезеңге өту ағымдағы кезеңдегі жұмыс толығымен аяқталғанда ғана жүреді. Әрбір кезең АЖ-ні әзірлеу әзірлеушілердің басқа командасына тапсырылатындай құжаттардың толық жиынымен аяқталады.

Каскадты модельде келесі этапқа өту алдыңғы этаптағы барлық жұмыстардың аяқталуын білдіреді.

Әр этап біткен кезде келесі этапта жұмысты жалғастыруға жетерліктей мөлшерде құжаттар жасалып шығарылады. Сонымен қатар жұмыстың этаптары логикалық тізбекте орындалады, ал бұл жұмысқа кететін барлық уақытты және шығынды алдын ала жоспарлауға ыңғайлы. Бұл модельдің кемшілігі бар. Оның кемшілігі – бір этап толық орындалып біткеннен кейін, келесі этапты орындау барысында қателіктер, жетіспеушіліктер пайда болуы мүмкін. Яғни алдыңғы этаптарға қайтадан баруға тура келетін жағдайлар көп кездеседі. Нәтижесінде жұмыстың орындалу мерзімі ұзаққа созылып кетуі мүмкін.

1. Деңгейлі (поэтапная) моделі.Бұл модельде алдыңғы этаптарға қайтадан барып, қажет болса түзетулер, толықтырулар енгізуге болады. Каскадты модельмен салыстырғанда деңгейлі (поэтапные) түзетулер бағдарламалық қамтаманы құру процесінің жұмыс сыйымдылығын (трудоемкость) азайтуға мүмкіндік береді. Әр этаптың өмір ұзақтығы бүкіл жұмыстың орындалу уақытына теңестіріледі.

Өмірлік циклдің қайта айналып келу (Спиральді) моделі.

Қайта айналып келу моделінде өмірлік циклдың бастапқы этаптарында талдау (анализ) және жобалау (проектирование) жүзеге асырылады.

Бұдан ақпараттық жүйенің деректре базасын жобалау процесінің негізгі кезендері шығады. ( 3 схемаға 3 кезең сәйкес келеді. )

1) Концептуальді жобалау – деректреге қойылатын талаптарды жинау, талдау және редакторлеу. Бұл кезеңнің соңыңда д.б.-ң құрылымын инвариантты болатын концептуальді модель алынады. Ол көбінесе «мән-байланыс» инфологиялық моделі түрінде болады.

2) Логикалық жобалау. Бұл деректерге қойылатын талаптарды деректердің ққұрылымына түрлендіру. Бұл кезеннің нәтижесі д.б.б.ж.-не бағыталған д.б.-ң құрылымын аламыз және қолданбалы программаның спецификациялары анықтанылады. Бұл кезенде деректер базасын әр түрлі және нақты д.б.б.бж-не қатысты моделдейді. Бұл моделдің салыстырмалы талдауын жасайды да даталогиялық модель құрылады.

3) Физикалық жобалау -деректерді анықтаудың ерекшеліктерін, қатынаудың әдістерін, т.б.-ды анықтау. Деректердің түрлі деңгейінің әр кезеңдегі айырмашылығын көрсету керек.

Деңгей	Кезең
1. Концептуальді деңгей: - мәндер - атрибуттар(қасиет) - байланыстар	Аналитиктің түсінуі, бейнелуі (инфологиялық моделі.)
2. Логикалық деңгей: - жазбалар - деректердің элементтері - байланыстар	Программистің түсінуі, бейнелуі (даталогиялық модель)
3. физакалық деңгей: - (деректерді топталу) - Индекстер - Қатынау әдістері	Администратордың түсінуі, бейнелуі (физикалық модель)

Нұсқағыштар. Ағаштар. Ағаштардың көрсетілімі.

Бейдетерминантты автомат бойынша детерминантты ақырлы автомат құру.

Детерминированный конечный автомат-распознаватель. Детерминированный конечный автомат (ДКА) — это пятерка X ,Y,δ , y0 ,F , где X — конечный алфавит входных символов, Y — конечное множество состояний, δ :Y × X → Y — функция переходов, y0 ∈Y — начальное (стартовое) состояние, F ⊂ Y — множество допускающих состояний. Расширенная функция переходов X ×Y → Y * : ˆδ , сопоставляющая новое состояние текущему состоянию и цепочке символов, определяется индуктивно следующим образом [5] : ∀y ∈Y ( ( , y) = y) ˆδ ε ; ( ( , ))) ˆ ( , ) ( , * ˆ ∀y ∈Y ∀ξ ∈ X ∀x∈ X δ ξx y = δ x δ ξ y . В таком случае, если δ ˆ (ξ, y0 )∈ F , то есть, стартуя в начальном состоянии и обработав цепочку ξ , автомат оказывается в одном из допускающих состояний, то говорят, что автомат допускает эту цепочку. Множество допускаемых цепочек образует язык L , распознаваемый ДКА: L = { ∈ X | ˆ ( , y0 )∈ F } * ξ δ ξ . Класс языков, распознаваемых ДКА, называют регулярными языками. Известно, что он совпадает с классом языков, описываемых регулярными выражениями и автоматными грамматиками [5].

Недетерминированный конечный автомат. Довольно часто используют модели, в которых считается, что автомат может на каждом такте находиться не в одном, а в нескольких состояниях одновременно. Такие автоматы называют недетерминированными конечными автоматами (НКА) и определяют аналогично ДКА, как пятерку X ,Y,δ ,s0 ,F , где X — конечный алфавит входных символов, Y — конечное множество состояний, Y δ : X ×Y → 2 — функция переходов, которая входному символу и состоянию сопоставляет уже не единственное состояние, а некоторое подмножество множества состояний, y0 ∈Y — начальное состояние, F ⊂ Y — множество допускающих состояний. По аналогии с ДКА, расширенная функция переходов Y : X Y 2 δ ˆ * × → определяется индуктивно: ( ( , ) { }) ˆ ∀y ∈Y δ ε y = y ;         ∀∈∀∈∀∈ = ∈ U ( , ) € * ( , ) ( , ) € q y y Y X x X x y x q δ ξ ξ δ ξ δ . Язык L , распознаваемый НКА, определяется следующим образом: L = { ∈ X | ˆ ( , y0 ) ∩ F ≠ ∅ } * ξ δ ξ . Известно, что недетерминизм не увеличивает вычислительной мощности модели и для каждого НКА существует эквивалентный (распознающий тот же язык) ДКА [5].

БИЛЕТ -14

Көпбайланысты құрылымдар.

Көпбайланысты структураның қасиеттері:

1. Әрбір элементке (түйін, төбе) саны еркін алынған сілтемелер болуы мүмкін.

2. Әрбір элемент кез келген басқа элементпен кез келген рет байланысады.

3. Әрбір байланыстырушы жасаушының (қабырға, доға) бағыты және салмағы болады.

Графтар күрделі объектінің қасиеттері мен қарым-қатынастарын көрсететін күрделі сызықты емес көбейтуге байланысты динамикалық құрылым болып табылады.

Графтың түйіндері нысанның элементтері туралы ақпаратты қамтиды. Түйіндер арасындағы байланыстар кестенің шеттері арқылы анықталады. бағытталмаған - Графтың жиектері, содан кейін олар жебелер жоқ бағдарланған шығыңқылар деп аталады, көрсеткі нұсқаған бағытта болуы мүмкін.

Барлық қосылыстары бар баған бағдарланған граф немесе гиграф деп аталады; барлық бағытталмаған қосылыстары бар граф - бағытталмаған граф; екі түрдегі қосылыстары бар граф - аралас граф. Symbol байланыстар: бағытталмаған - (А, В), бағдарланған -. Графтар суреттерінің мысалдары 6.1-суретте келтірілген. 6.1-графиктегі кестелердің кронштейндік көрінісі:

а). ((A, B), (В, А)) және б). (<A, B>, <B, A>).

2. ДБ инфологиялық моделін жобалау. Пәндік саланы жүйелік талдау, сипаттау.

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

Инфологиялық модельдер құру үшін ER-диаграмма тілін (ағылш. Entity-Relationship, яғни мән-байланыс) пайдалануға болады. Онда мәндер белгіленген тіктөртбұрыштармен, ассоциациялар – белгіленген ромбтармен немесе алтыбұрыштармен, атрибуттар – белгіленген сопақшалармен және олардың арасындағы байланыс – үстінде байланыс дәрежесі (1 немесе К «көп» деген мағынаны беретін) көрсетілген бағытталған қабырғалармен белгіленеді және қажетті түсініктеме беріледі.

8.1 ─ сурет –ER-диаграмма тілінің бөлшектері

Сипаттамаларды баяндау үшін жаңа инфологиялық модельдеу тілі (ИМТ) қосымшасы пайдаланылады, жалпы түрі төмендегідей:

СИПАТТАМА (атрибут1,атрибут2, ..., атрибут n)

АССОЦИАЦИЯ [МӘН S1, МӘН S2, ...]

(атрибут1,атрибут2, ...атрибут n),

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

Осылайша, мәндер арасындағы байланыстар көпшесінің үлгісін қарастырайық:

Дәрігер (Дәрігердің нөмірі , Аты – жөні, Мамандығы)

Науқас (Регистрациондық нөмірі, Аты-жөні, Мекен-жайы, Туған күні, Жынысы)

Емдейтін дәрігер [Дәрігер 1, Науқас К]

Дәрігер нөмірі, Регистрациондық нөмірі)

Консультант [Дәрігер 1, Науқас К]

(Дәрігердің нөмірі, Регистрациондық нөмірі)

Көп қолданылатын реляцияондық мәліметтер қоймалары үшін «Кесте-байланыс» инфологиялық модельді тілді ұсынуға болады, оны қолдану мысалы 2-суретте көрсетілген. Онда барлық мәндер мән аттары мен түрінен тұратын аты бар бірбағанды кестелермен көрсетіледі. Кесте жолдары – ол мәндер атрибуттары тізімінен, ал олардың алғашқы кілтті құрайтындары жақын орналасады және рамкамен бастырылады. Мәндер арасындағы байланыс алғашқы кілттер немесе олардың құрушыларынан бағытталған кесінділермен 6-суретте көрсетіледі.

8.2 - сурет - « Кестелер-байланыстар» схемасы

Сілтемелік бүтінділік – бұл байланысқан кестелер жазуларының арасындағы қатынастардың түзулігіне кепілдік беретін жғне бір-бірімен байланысқан мәліметтер бµлігінің кездейсоқ жойылуы немесе өзгертілуіне жол бермейтін ережелер жүйесі. Сыртқы кілті бар кестенің ғрбір жолы үшін сілтемелік бүтінділік – бұл алғаш кілті бар кестеде сәйкес жолдың бар болуын қамтамасыздандырады (егер б±л кесте сыртқы кілті бар кестемен байланысқан болса). Егер бұл ғрекетті орындайтын болсақ, алдымен кестелер байланысын жою қажет. Сілтемелік бүтінділікті периодты тексеру ДҚ-ның эволюциясы нғтижесінде қажетті мәліметтердің жоғалмауының негізі екендігіне көз жеткізу. Сілтемелік бүтінділік, сонымен қатар, біреуінің сыртқы кілті екіншісінің (кестенің) алғаш кілтінің мғнімен мғндес болса кестелердегі сәйкес мғндердің µзгерту операцияларын қосады

Пәндік аймақ ұғымы

Пәндік аймақ дегеніміз деректер базасын жүйелік талдау кезінде пәндік аймақтың объектілері мен олардың арасындағы нақты байланыстар табиғи тілде, сөздермен толық сипатталады.

Пәндік аймақтың ақпараттық моделі

Мекемедегі ақпараттық процестерді автоматтандыру мақсатында ақпараттық жүйені жасаудың бірінші кезеңіндегі бастысы – ол автоматтандырылатын объектіні, олардың қасиеттерін, осы объектілер арасындағы дара қатынастарды жан-жақта зерттеу және алынған ақпаратты деректердің ақпараттық моделі түрінде көрсету.

Деректердің ақпараттық моделі пәндік аймақтың семантикасын сипаттаудың субъективті құралдарының терминдерімен, яғни түпмәндер, атрибуттар, түпмәндердің идентификаторлары, супертиптер, ішкі типтер және т.б. арқылы бейнелеуге арналған.

Деректер базасының пәндік аймағының ақпараттық моделінің құрамы келесі конструкциялардан тұрады: Түпмән-байланыс диаграммалары, түпмәндердің анықтамалары, түпмәндердің бірегей идентификаторлары, түпмәндердің атрибуттарының анықтамалары, түпмәндер арасындағы қатынастар, супертиптер мен ішкі типтер.

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

Анық емес грамматикалар, автоматтар және тілдер.

Тiлдер және автоматтар теориясы абстрактiлi есептеуiш құрылымдарды немесе "Машиналарды" зерттеумен шұғылданады.
1930-шi жылдарда, компьютерлердiң пайда болуына дейiнгі көп уакыт бұрын, А.Тьюринг абстрактiлi машинаны зерттедi, кем дегенде есептеулердiң төңiрегiнде,қазiргi есептеу машиналарының барлық мүмкiндiктерiне ие болды. Тьюрингтiң мақсаты есептеу машинасы iстей алатын, не алмайтын шекарасын сипаттау болды. Алынған нәтижелер абстрактiлi тьюринг машиналарына ғана емес, сонымен катар,қазiргi кездегі компьютерлерге қолдануға болады.
1940-шi және 1950-шi жылдардағы бiраз зерттеушiлер ең оңай машиналарды зерттеумен шұғылданды, бүгiн олар "Шектi автоматтар" деп аталады. Мұндай автоматтар бастапқыда адам миының жұмыс жасау үлгiсі ретiнде ұсынылған. Соңында1950-шi жылдарда лингвист Н.Хомский формалды"Грамматик" зерттеуімен шұғылданды. Дәл мағынасында сөздер машиналар болмай, грамматикалар, әйтсе де, тығыз байланған абстрактiлi автоматтармен және кейбiр ең маңызды программалық қамтамасыз етуді негiзiмен құрайтын қызмет көрсетедi, жеке алғанда, компиляторлардың компоненттері менде.
1969 жылда С.Кук Тьюрингтің есептелу және есептелмеу туралы нәтижелерiн дамытты. Оған есеп бөлудi негiзiнен шешiлетін есепті, есептеу машинасы да шешетіндей бөлді,бiрақ ол үшiн машина уақыты көп талап етедi екен және компьютер дәл осылай есептiң түгелдей дерлiк даналарының шешiмдерi үшiн пайдасыз басқаларын қоспағанда. Соңғы класстың есептерi "Қиын есептелетiн" деп атайды"Қиын болатын" ) немесе "NP-қиын". Тiптi экспоненталық өсуде есептеу машиналарының жылдамдықтары("Мур заңы") тiптi күмәнді, ол бізге бұл сыныптың есептерiнiң шешiмiнде түбегейлi жетiстiктерге жетудiң сәтi түседi.
Бұның барлығы теориялық құрастырулар бүгiнгі кездегі ғалымдардың информатиканың төңiрегiдегi шұғылдануына тiкелей байланысты. Енгiзiлген ұғымдардың кейбiрi, мысалы,мұндай шектi автоматтар және үстiрт грамматикалардың кейбiр түрлерi ,программалық қамтамасыз етудің жобалау және маңызды компоненттердiң жасауында қолданылады.
Басқа ұғымдары, мысалы, Тьюринг машинасы, бiзге программалық қамтамасыз етудi маңызды мүмкiндiктерін анықтауға көмектеседі. Жеке алғанда, есептеулердiң күрделілер теориясы бізге есептi шеше алатынымызды"маңдайға" және оған тиiстi бағдарламаны жазуды ( егер буль есебі "Қиын рұқсат етiлетiн" сыныпқа жатса )немесе бiзге қиын есептелетін, жақын, эвристикалық немесе әйтеуiр бiр көмегiмен жұмсалатын уақытты шектеудiң сәтi түсетiн басқа әдiс қолдана шешiмді iздеукерек.
Автоматтардың теориясы және күрделiлiктiң теориясының себептерi қатарына байланысты ең маңызды информатиканың ядроның бiр бөлiктерi болып табылады.
Шектi автоматтардың теориясына кiрiспе
Шектi автоматтар көп компоненттер және программалық қамтамасыз етулер үшiн үлгi аппаратты болып табылады:
1. Өңдеу және тексеру үшiн цифрларға қолданылатын программалық қамтамасыз ету
2. Үйреншiктi компилятор "Лексикалық анализатор", яғни сол компилятордың компоненті, мұндайға түпнұсқаның бөлуiне логикалық бірліктер, идентификаторлар, түйін сөздер, жауап беретiн және тыныс белгiнiң таңба бiрлiктері осыларға жауап береді.
3. Сүзiп шығу үшiн программалық қамтамасыз ету мұндай үлкен мәтiндiк массив,Web- беттер, берілген сөздерді, сөйлемдердiң, (үлгiлер ) нышандардың тiзбектерiн іздеу мақсатымен.
4. Байланыстың хаттамалары жүйелердiң әр түрлi тектiң тексеруi үшiн программалық қамтамасыз ету(немесе қорғауға алған ақпар алмасу үшiн хаттамалар ), түпкi санда әр түрлi күйлерді болатын.
Әр түрлi жүйелер және олардың компоненттерiнiң жиыны бар, мысалы,дәл кәзiр есептелгені, әрбiр моментте оларды "Күйлердің" түпкi санның бiрiнен қарауға болады. Әрбiр күйдi тағайындау мен жүйенiң тарихының нақтылы моментiнiң есте сақтауы болып табылады. Сан болғандықтан, онда жүйенiң барлық тарихын еске сақтау мүмкiн емес, демек, жүйенi тек қана мұқият салу керек, ең маңызды мәлiметтi сақтап, жеңiл-желпiні ұмыту үшiн.
Күйлердi санның шектiлiгiнiң артықшылығы жүйенi шектелген қорлар арқылы жүзеге асыруға болатындығында. Мысалы, оны"темiрде" жүзеге асыруға болады схема түрінде немесе жай бағдарлама түрінде, негiзiнде шектелген санының мәлiметтерiн немесе ағымдағы машина кодының командалары шешiм қабылдауы.
Осыған ұқсас барлық жағдайларда лексемаларды оқып – тану үшін шектік автомат (ША) немесе қалыптар (жағдайлар) машинасы деп аталатын қарапайым модель қолданылады. Қай жағдайда екенімізді біле отырып, біз келесі енгізілетін символдың ізделінді лексема бөлігі болуы мүмкіндігін анықтай аламыз. Келесі суретте бірлерінің саны тақ болатын екілік байламды байаныстыр
1-шi мысал. Ең оңай қарапайым шектi автомат "Қосылу-өшірілу"ауыстырып қосқышы болып табылады. Бұл құрылымдар өз ағымдағы күйiн еске сақтайды, және бұдан батырманың басуынан күйі нәтижеге тәуелдi болады. "Өшiрген" күйлерден батырмаларды басу арқылы "Қосылған" күйге ауыстырып қосқыш ауыстырады және керiсiнше.
Кiретiн сигналдарға әрiптер сәйкес келедi. Лексикалық анализатор әрдайым бiр-бiрнышаннан құрастырылатын бағдарламаларды қарап шығады деп бiз мәлiмет санай аламыз. Әрбiр келесi нышан автомат үшiн мәлiмет кiретiн сигнал сияқты қаралады.
Автоматтың бастапқы күйі бос тiркеске сәйкес келедi, және әрбiр күй күйге then-ның сөзiнiң кезектi әрiбi бойынша өте алады, келесi префикске тиiстi. Белгi қойылған "Then" күйі әрiптерден барлық осы сөздер енгiзiлген бойынша жетедi. Автоматты функция болатындығы then-ның сөздерi айырып тану, онда соңғы рұқсат ететiн күйдi жалғыз санаймыз

Автомат – бұл қандай да бір жиынды анықтайтын алгоритм, мүмкін болған жағдайда ол жиынды басқа жиынға түрлендіруі мүмкін. Автоматтардың формальсыз сипатталынуы келесі түрде болады: автомат кіру лентасынан, күйдің нөмірін сақтайтын ақырлы жадысы бар басқару құрылғысынан тұрады, сонымен қатар көмекші және шығыстық лентасы болуы мүмкін. Автоматтардың екі типі бар:

1) танығыштар – шығыссыз автоматтар, олар кіру тізбегі берілген L жиынына тиісті ме соны таниды;

2) түрлендіргіштер – шығысы бар автоматтар, олар x ∈ L шарты орындалғанда кіру тізбегі х –ті у тізбегіне түрлендіреді.

Кіру лентасын ұяшықтардың сызықтық тізбегі ретінде қарастыруға болады, әрбір ұяшық ақырлы кіру алфавитінің бір символын сақтай алады.

Автоматтың лентасы шексіз, бірақ әрбір уақыт моментінде ұяшықтардың тек ақырлы саны ғана бос емес болады. Бос емес аймақтың шекаралы оң және сол жақтағы ұяшықтары арнайы соңғы маркерлерді алуы мүмкін. Маркер лентаның тек бір жақ соңында ғана тұруы немесе мүлдем болмауы мүмкін.

Кіру бас тиегі әрбір уақыт моментінде кіру лентасының бір ұяшығын оқиды. Автоматтың бір жұмысының тактісінде енгізу бастиегі бір ұяшық оңға жылжуы немесе бір орында тұруы мүмкін, мұндайда ол тек қана оқуды орындайды, яғни автоматтың жұмыс істеу барысында кіру лентасының ұяшықтарындағы символдар өзгермейді.

Жұмыс лентасы - ақпаратты сақтаудың көмекші қоймасы. Ондағы берілгендер автоматтың көмегімен оқылады және оған жазылуы да мүмкін.

Басқару құрылғысы – автоматтың тәртібін басқаратын бағдарлама. Ол кіру бастиегімен оқылатын ағымды кіру символына сәйкес күйдің және жұмыс лентасынан алынып тасталған ағымды ақпараттың қалай өзгеретінін сипаттайтын, бейнелеуі бар күйлердің ақырлы жиынын береді Басқару құрылғысы жұмыс бастиегінің жылжу бағытын және жұмыс лентасына қандай ақпарат жазу керектігін анықтайды. Автомат жұмыс тактілерінің қандай да бір тізбегін орындай отыра жұмыс істейді. Тактінің ең басында кіру символы оқылады және жұмыс лентасындағы ақпарат зерттеледі. Одан кейін оқылған ақпарат пен ағымды жағдайға байланысты, автоматтың іс - әрекеті анықталады:

1) кіру бастиегі оңға жылжиды немесе бір орында тұрады;

2) жұмыс лентасына қандай да бір ақпарат жазылады;

3) басқару құрылғысының жағдайы өзгереді;

4) шығу лентасына (егер ол бар болса) символ жазылады.

Автоматтың жұмыс істеу тәртібін автоматтың конфигурациясы терминімен сипаттаған ыңғайлы, ол келесіден тұрады:

а) басқару құрылғысының жағдайы;

б) кіру лентасындағы берілгендер кіру бастиегінің жағдайымен бірге;

в) жұмыс лентасындағы берлігендер кіру бастиегінің жағдайымен бірге;

г) шығу лентасындағы берілгендер, егер ол бар болса.

Басқару құрылғысы детерминделмеген болуы мүмкін. Мұндай жағдайда әрбір конфигурация үшін тактілердің ақырлы жиыны бар болуы мүмкін, оның әрқайсысын автомат осы конфигурациядан шыға отыра жасайды. Басқару құрылғысы детерминделген болады, егер әрбір конфигурация үшін тек бір ғана келесі такт мүмкін болса.

Тілдер теориясын оқуды бастамастан бұрын тіл деген терминді қалай ұғатынымызды анықтап алуымыз керек. Тілдің энциклопедиялық “сөйлесудің маңызды құралы, әрі адамзат қоғамында өзара ой алмасып түсінушілік” деген анықтамасы математикада тіл теориясына жеткілікті анықтама емес. Сондықтан біз тілді абстрактілі түрде математикалық жүйе ретінде қарастырамыз. Бұл бізге формальді тілдерге қатаң анықтау беретін мүмкіндік, ол алдағы уақытта модельденеді. Осы оймен біз төмендегідей анықтама береміз.

АНЫҚТАМА 1.1. Алфавит және сөздік шекті символдар жиыны. Символ дегеніміз не - анықталмайды, қалай анықталмайды, мысалы геометриядағы нүкте сияқты.

Алфавитке бірнеше мысалдар: латын тілінде {A,B,…Z}; грек тілінде {α٫β‚…ώ}; бинарлық {0,1}.

АНЫҚТАМА 1.2. Сөйлем (жол, сөз) алфавит символдарынан тұратын кез келген шекті ұзындық бауы. Бірде бір символдан тұрмайтын сөйлем, бос сөйлем деп аталады. Ол грек әрпі мен анықталады. Егер V - кез келген алфавит, онда V^* - барлық сөйлемдердің жиынымен анықталады, V алфавит символдарынан құралған, бос сөйлемді де қосып алады.

V⁺- пен анықтаймыз. Жиын V/{E}; Мысалы, егер V{0,1}, онда V^*={E,0,1,00,01,10,11,000,…}, a V^*={0,1,00,01,10,11,..}.

Егер х V^*, онда х баудың ұзындығын, х-ті, оны құратын символдар санын білдіреді. Бос баудың ұзындығы , 0-ге тең.

АНЫҚТАМА 1.3. Тіл кейбір алфавиттердегі кез келген сөйлем жиыны. Формальды түрде , егер V- алфавит, L-тіл, онда L V^*.

Әрине 3 сұрақ туады:

1) Тілді қалай ұсынамыз, тілді құрайтын ұсынысты қалай анықтаймыз?

2) Шекті ұсыныс әр тілде бар ма?

3) Шекті ұсынысы бар әрбір тіл класының құрамы қандай?

Егер тіл шекті болса, 1-сұраққа жауап беру оңай. Барлық ұсынысты санап олардың тізімін жасау керек. Екінші сұрақтың жауабы керісінше.

Анықтау: Тілді құрудың әдісінің бірі берілген тілде берілген сөйлемдердің бар жоқтығын анықтайтын алгоритм беруге негізделген.

Ортақ әдісі - тілдегі сөйлемге “иә” деген жауаппен жұмысты аяқтайтын процедура беру, немесе аяқталмайды, тілдегі емес сөйлемге “жоқ” деген жауаппен аяқталады. Сондай алгоритммен процедура тілді анықтайды дейді. Алгоритм емес процедураның көмегімен анықтайтын тілдер бар.

Пайда болу. Тілді ұсынудың басқа тәсілі - жүйелік түрде тілдің сөйлемін белгілі бір тәртіппен тудыратын процедура беру.

Егер алгоритм мен процедура берілсе, онда ол V – алфавиттінде тілді анықтайды. Сонда алгоритм және процедура механизмі пайда болады. V^* көпшілігінің жүйелік генерациялануын тілдің және механизмнің көмегімен тексеруге болады. Бірақ егер қолданылған процедура алгоритмдегі қауіпті сезсе, онда бұл өзгеріс бірінші сөйлемдегі процедура орындалады. Осыған орай процедураны табу үшін оның қатесін тексеру керек. Оны келесі мүмкіндіктерден табуға болады. V- алфавитінде символдар болсын. V^*- сөйлеміндегі жиынды жүйедегі Р- санымен қосу бос сөйлемдегі Е арқылы қарастыруға болады. Енінің ұлғаюымен V^* сөйлемін тәртіппен нөмірлейміз. Мысалы: егер {a,b,c}, онда V^* сөйлемі төмендегідей нөмірленеді.

1.е 5.aa 9.bb

2.a 6.ab 10.bc

3.b 7.ac 11.ca

4.c 8.ba 12. …

Соныменсөйлемдержиынындағы V-алфавитісаналынды.

№ 15 БИЛЕТ

1. Жадыны динамикалық бөлу

үшінші нұсқа MS-DOS та қолданылады. ПЗУ-дағы сол бөлігі BIOS –деп аталады
Жадыны фиксирленген бөлімдермен орналастыру Жады бірнеше бөлімдерге бөлінеді. Процестер әр түрлі болуы мүмкін, сондықтан әрбір бөлімге әр түрлі көлемде жады керек.

Жүйе ие болуы мүмкін:

· Барлық бөлімге бір кезек

· әрбір бөлімге жеке-жеке кезек

Жадыны фиксерленген бөлімдермен орналастыру

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

· Кезектес

· Бөлімде максималды орын алатын тапсырма таңдалады

Сонымен қатар аралас жүйе болуы мүмкін.

3. Динамикалық бөлімдермен жадыны орналастыру

4. Бұл жүйеде басында жады бос болады,тек содан соң жадыны динамикалық орналастыру басталады

Д инамикалық бөлімдермен жадыны орналастыру.Кемшіліктер:

· қиыншылық

· Жады фрагменттеледі

Жылжымалы бөлімдер

Бұл фрагментациямен көресетін бір әдіс түрі. Бірақ оған көп уақыт кетеді.

Жылжымалы бөлімдер

Бөлімдердің өсімі

Басында ойлағандай емес, процеске кейбір кезде көп жады қажет болуы мімкін.

Бөлімдердің өсімі.

Мекен жайларды қалыпқа келтіру және жадыны қорғау

Алдағы мысалдардан біз екі негізгі проблемманы көре аламыз.

· Мекен жайларды қалыпқа келтіру және жадыны ауыстыру

· әрбір программаның мекен жай кеңістігін қорғау.

Бұл екі проблеманың шешілуі арнайы аппаратық регистрмен шешіледі

· базалық

· шекті

2. ішкі жадымен қолданылатын әдіс (Свопинг және виртуалды жады)

Ереже бойынша жады жетпегендіктен процестерді ауыстыру үшін көбіне диск қолданылады

Дискті қолданудың негізгі әдісі:

· свопинг (подкачка) мұнда процесс жұмыс істеу үшін жадыға толығымен жүктеледі

· виртуалды жадыпроцесс жұмыс істеу үшін жадыға кейбір бөлігі ғана жүктеледі.

2. Функционалды тәуелділіктер. Байланысты декомпозициялау. Транзитивті тәуелділік

Функционалдық тәуелділік. А→В және В→А функционалды тәуелділік болса, А және В бір мәнге сәйкес, немесе функционалды байланыс А↔В (В↔А). Мысалы, Аты-жөні мен РНН арасындағы функционалдық өзара тәуелділік – Аты-жөні↔РНН.

Транзитивті тәуелділік. С атрибуты А атрибутына транзитивті тәуелді болады, егер А,В,С атрибуттары А→В және В→С шартын орындаса, бірақ қайтару тәуелділігі жоқ. Мысал: ФИО→ Атағы →Жалақы.

Деректер базасының пәндік аймағындағы барлық функционалдық тәуелділіктер анықталған соң, қатынастарды бөлшектеу процесіне кірісуге болады, оны «қатынастар схемасының декомпозициясы» деп атайды. Қатынастар схемаларының декомпозициясы реляциялық деректер базасының логикалық моделін құрудың негізгі әдісі болып табылады.

Декомпозицияның нәтижесі нормальданған деректер моделі болады.

Реляциялық деректер базасын жобалаудың мақсаттарының бірі әмбебап қатынастарды нормальді форма талаптарын қанағаттандыратын қатынастардың жиынтығына декомпозициялау (бөлшектеу) болып табылады.

R(A_1,A_2,..,A_n) қатынасының схемасының декомпозициясы деп оны R – дің мынадай R= R_1∪R_2∪…∪R_k болатын R_1,R_2,…,R_kішкі жиындарының жиынтығымен алмастыруды айтады.

Қатынастардың декомпозициясы әдісінің алгоритмі:

Деректер базасының әмбебап қатынасын құру;

Қатынастың атрибуттары арасындағы барлық функционалдық тәуелділіктерді анықтау;

Қатынастың Бойс – Коддтың нормальді формасында болуын анықтау. Егер болса, онда жобалауды аяқтау, әйтпесе қатынасты екі басқа қатынасқа бөлшектеу;

2-ші және 3-ші пункттерді декомпозиция нәтижесінде алынған әрбір жаңа қатынасқа қайта орындау.

3. Белгілерді тану. Лексикалық талдауды программалау

Лексикалық анализдің фазасының қажеттілігі.Лексикалық анализ- трансляция процесінің бірінші фазасы, Лексема деп аталатын кіру тізбегінің символдарын әлдеқайда үлкен конструкцияларға топтау.

Әрбір лексемамен 2 ұғым байланысты:

1. Лексема класы;

2. Лексема мәні.

Транслитератор.

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

1. Әріп-әріптер жиынына сәйкес қойылатын класс, бұл әріптердің бір

алфавиттен болуы шарт емес.

2. Сан-көбінесе 0 ден 9-ға дейінгі сандарға қатысты символдар жиыны;

3. Бөлектегіш - пробел, жолды ауыстыру;

4. Ескерту-тілдің алфавитіне тиісті емес символдар;

5. Басқалар-белгілі категориялардың ешбіріне жатпайтын символдар.

Символдар. Лексикалық анализдің грамматикасы. Лексикалық анализаторлар көбінесе элементар конструкцияларды тану үшін қолданылады. Вирт диаграммасымен ақырлы автомат арасындағы байланыс ақырлы автоматты құрастыру үшін Вирт диаграммасын жәнес ол

жақтың рекурссиялы грамматикалар қатарын қолдануға болады. Ережежелерді сипаттауда олар анағұрлым көрнекті. Сонымен бірге Вирт

диаграммасымен ақырлы автоматтар арасында бір мәнді сәйкестік бар.

Терминалдардан ғана тұратын Вирт диаграммасына эквивалентті ақырлы

автомат мынадай түрде құралады:

1. Диаграмманың бастапқы доғасы арқылы автоматтың бастапқы жағдайына түрленеді.

2. Диаграмманың доғасы ақырлы автоматтың бекітуші жағдайына түрленеді.

3. Ақырлы автоматтың құралуын идентификатордың сипаттау мысалында көруге болады.

Вирт диаграммасымен оң сызықты диаграммалар арасындағы байланыс, оң жақ рекурсияны итерацияға түрлендіру. Оң сызықты грамматика болған жағдайда ақырғы автомат құрамай-ақ, бастапқы грамматиканы Вирт диаграммасына түрлендіруге болатыны туралы айта аламыз.

А) Қарапайым грамматиканы түрлендіру:

Вирт диаграммасымен сол жақ рекурсияның грамматикасы арасындағы

байланыс. Сол жақ рекурсияны итерацияға түрлендіру. Құрамында сол жақ рекурсиясы бар ережелер үшін итерацияға түрлендіруге болады:

1) Рекурсивті анықталатын терминал емес тен шығатын доға, цикл құру

арқылы ереженің ең соңын әкеліп қосылады.

2) Адресаты жоқ терминал еместер сызылып тасталынады, ал оған

кіретін доға алынып тасталады.

Лексикалық талдау.

Программаның берілуі текстік шығаруда компилятор жұмысына өте ыңғайлы сондықтан программа анализінің уақытында кезегі пайда болады немесе лексема пайда болады. Лексемалардың көпшілігі лексикалық класстарға өтеді. Лексемалар бір лексикалық класқа көшеді. Егер олар синтаксистік анализаторда болса. Мысалы: синтаксистік анализ уақытында барлық идентификаторлардыбірдей деп санауға болады. Лексикалық класстардың көлемі өте алуан түрлі. Мысалы: лексикалық класс идентификатордан өте шексіз. Басқа жағынан, лексикалық класстар бар, олар бір ғана лексемадан тұрады. Мысалы көпшілік ішінде if лексемасынан тұрады.

Программалау тілінің көпшілігінде келесі лексикалық класстар бар:

* негізгі сөздер

*идентификаторлар

*жолдық интегралдар

*сандық константтар

Барлық көпшілік ішіне кейбір сандар беріледі. Олардың лексикалық класстың идентификаторы немесе лексикалық класс деп аталады.

Мысалы: const pi = 3.1416.

Паскаль тілінің операиторын қарастырайық. Бұл оператор келесі лексемалардан тұрады:

- Const – лексикалық класс, const LS

- Pi лексикалық класс Identifier LS

- =- лексикалық класс Relation LS

- 3.1416- блексикалық класс Number LS

- ; - лексикалық класс Semicolon LS

Программалау тілінің әртүрлі лексикалық талдауы.

Кейбір тілдердің ерекшеліктері бар, олар лексикалық талдауды құрайды. Мұндай тілдер Фортран және Кобол, тілдері конструкциясының алмасуын енгізу жолында позициясы болады. Мысалы: жолды ауыстырғанда Коболда арнайы 6 колонколы символдар қолданылады. Әйтпесе келесі жол дұрыс болмайды. Қазіргі кездегі тілдердің негізгі тенденциясы программалауда текстік программада еркін алмасады. Бір тілден екіншісіне тілдегі символдарды қолдану ережесі пайда болады. Кейбір тілдерде,

Алгол 98 немесе Фортран пробелдері жолдық интегралдарға байланысты.

Мысалы: ДО5= 1,25 операторында ДО кілті сөздің 10- дық нүктесінен анықтауға болады. Басқа жағынан, ДО 5=1,25 операторында біз лексеманы табамыз.

Кілтті сөз ДО нұсқа5, идентификатор 1, оператор =, констант 1, үтір және констант 25. Сондықтан, үтірді кездестіргенше, бізДО – кілтті сөздің деңгейін береді. Бұл жағдайды шешу үшін, FORTRAN 77 әрбір үтірде нұсқа мен индекспен ДО операторында орындалады. Мұндай үтірдің қолданылуы ДО операторын анықтап береді. Қазіргі кезде прогрммалау тілдерінде кілтті сөз анықталмайды. Егер кілтті сөз анықталмаса, онда лексикалық талдау кілтті сөзді анықтайды. Шын мәнінде, нгер лексикалық талдау, мысалы, PL/I келесі операторда толық болады.

If then then then = else ; else; else =then;

Лексикалықанализатордыңтағайындалуы.

Лексикалықанализатордықарастырғанғадейін, лексеманеекенінбіліпалуымызкерек.

Лексема (тілдіңлексикалықбірлігі) – бұлтілдіңқұрылымдықбірлігі, олқарапайымтілдердіңсимволдарынантұрадыжәнеқұрамындабасқатілдердіңқұрылымдықбірліктеріболмайды.

Қарапайымсөйлесутілініңлексемасысөздерболады. Программалаутілдерініңлексемасыидентификаторлар, тұрақтылар, тілдіңнегізгісөздері, операциябелгілеріжәнетағыбасқаболады.

Программалаутілдерініңқұрамыосытілдіңсинтаксисіменанықталады.

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

Теориялықжағынананализаторкомпилятордыңміндеттісіболмайды. Оныңбарлықфункцияларысинтаксистікталдаудыңқадамындаорындалады, өйткеніолтолығыменкірутілініңсинтаксисірегламентпенберілген. Сондабірнешесебептерболады, осысебептернегізіндебарлықкомпиляторларқұрамындалексикалықанализбар:

• лексикалықанализаторшығупрограммасыныңсинтаксистікқадамындағымәтінменжұмыстыжеңілдетедіжәнеөңделетінақпараттыңөлшемінқысқартады.

• мәтінделексемаларталдауынбелгілеуүшін, қарапайым, эффектілікжәнетоериялықжағынансараптаутехникасыжақсыболса, осыуақыттасинтаксистіканализдіңқадамында, шығутілініңқұрылымындақиын, күрделіталдауалгоритмдеріқолданылады.

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

Лексикалықанализаторменорындалатынфункцияларжәнелексемақұрамы, олардыолшығупрограммасыныңмәтініндебелгілейді, оларкомпиляторверсиясынабайланыстыөзгереалады. Ондақандайфункциялардылексикалықанализаторорындайдыжәнеқандайлексематиптерінолшығыспрограммасындабелгілеуікерек, алқандайтиптердісинтаксистікталдаудыңқадамына, осыныңбәрінкомпилятордыөңдеушішешеді. Негізіненлексикалықанализаторларшығыспрограммасыныңайтылуынанерекшеліктердіорындайды. Соныменқатартабуляциясимволдарыныңжәнежолаударуларының, соныменқатаркелесітиптерлексемаларсимволдарының: идентификаторлар, сандықжәнесандықтұрақтылардың, негізгікірутілініңсөздерін, операциябелгілерініңжәнебөлгіштердіңерекшеліктерінорындайды.

Қарапайым түрде лексикалық және синтаксистік анализдер компилятормен орындала алады. Бірақ көптеген программалау тілдеріне, лексикалық анализдің қадамына ақпарат жеткіліксіз болуы мүмкін. Осындай жағдайдың мысалы болып, FORTRAN тіліндегі оператор программасы бола алады. Егер мәтін бойынша DO 10 I=1 оператордың типін анықтауға болмайды.

Басқа тағы мысал бола алатын С тілінің операторы. Оның сыртқы пішіні мынадай болады: k = i+++++j; Бұл оператордың тек бір ғана түсіндірмесі бар: k = i++ + ++j; Оның лексикалық анализаторын табу үшін, барлық операторды аяғына дейін қарап шығу керек. Қате нұсқалары тек семантикалық анализдің қадамында байқалуы мүмкін. (Мысалы, k = (i++)+++j; нұсқасы синтаксистік жағынан дұрыс болады, бірақ С тілінің семантикасымен рұқсат етілмейді). Бұл конструкция дұрыс болу үшін, оған кіретін және операндалар бейнеленуі керек және тілінің операциясына рұқсат беру керек.

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

Лексикалық және синтаксистік анализаторлар арасындағы байланыстардың екі түрлі әдісі бар:

• жүйелік

• параллельдік

Жүйелік нұсқада лексикалық анализатор шығыс программасының мәтінін басынан, аяғына дейін қарастырады. Сонымен қатар бұл мәліметтердің жиынтығын лексемалар кестесі деп атайды. Лексема кестесінде тілдің негізгі сөздері, идентификаторлар және тұрақтылар, ереже бойынша, айтылған кодтарға өзгертіледі. Сонымен қатар идентификаторлар және тұрақтылар үшін, лексема кестелерінің және идентификаторлар кестелерінің арасында байланыс орнатылады.

Бұл нұсқада лексикалық анализатор барлық шығыс программасының мәтінін бір рет басынан аяғына дейін қарастырады. Лексемалар кестесі толығымен құрылады және оған компилятор қайта оралмайды. Барлық келесі өңдеуді компиляцияның келесі фазалары орындайды.

Параллельдік нұсқада шығу мәтінінің лексикалық талдауы қадам бойынша орындалады, сонымен синтаксистік анализатор, келесі тілдің құрамындағы талдауды орындап, сканерге келесі лексема туралы хабарлайды. Сонымен қатар ол қандай лексеманы күту керектігін хабарлайды. Талдау барысында қателік болса “қайта қайтару” орындалуы мүмкін, мәтіннің талдауын басқа негізде орындау үшін. Синтаксистік анализатор келесі тіл құрамының конструкциялық талдауын орындаса, лексикалық анализатор табылған лексемаларды лексема кестесіне және идентификатор кестесіне орналастырып, талдауды сол тәртіппен жалғастырады. Параллельдік нұсқауда берілген синтаксистік және лексикалық анализаторлардың жұмысы 1.1 кестеде көрсетілген.

... Begin

For i: = 1 to N do

Fg : = fg *0.5

2. Лексикалық анализатордың құрылу принциптері.

Лексикалық анализатор тұрақтылар және идентификатор сияқты объектілермен қарым қатынаста болады. Тұрақтылар және идентификаторлар тілі – көп жағдайда қайталанбас болады және қайталанбас грамматикаларының көмегімен жазылуы мүмкін. Қайталанбас тілдердің анықтамасы соңғы автоматтар болады. Мынадай ережелер болады, осы ережелер арқылы кез келген қайталанбас грамматика үшін детерминировалданған емес соңғы автомат құрылуы мүмкін. Әрбір кіру тізбегінің тілі үшін соңғы автомат сұраққа жауап қайтарады.

Сканер келесі іс - әрекеттерді орындау керек:

• лексеманың шекарасын толық анықтауы керек, олар шығу мәтінінде берілмеген;

• ақпаратты сақтау үшін, белгілі бір іс - әрекеттерді орындауы керек.

Лексемалардың шекараларын анықтау.

Лексемалардың шекараларын белгілеу қателіктер туғызады. Өйткені кіру программасының мәтінінде лексемалар арнайы символдармен шектелмеген. Егер сканер – программасының терминында айтатын болсақ, онда лексемалардың шекараларын анықтау – бұл дегеніміз кіру символдарының жалпы ағымына кіретін жолдардың белгіленуі. Жалпы түрде бұл мақсат қиын болуы мүмкін, онда сканердің параллельдік жұмысы керек болды (лексикалық анализатордың), синтаксистік талдаудың және семантикалық талдаудың да жұмысы керек болды. Көптеген кіру тілдеріне лексема шекаралары берілген терминалдық символдармен шешіледі. Бұл символдар – пробелдер, операция белгілері, коментарий символдары, сонымен қатар бөлінділер (үтірлер, нүктелі үтірлер және тағы басқа). Бұндай терминалдық смиволдардың жиынтығы кіру тілінің синтаксисіне байланысты болады.

Маңыздысы, операция белгілері лексемалар болады және оларды жіберуге болмайды.

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

Мысалы, жоғарыда көрсетілген С тілінің жолы k = i +++++ j; лексемаларға келесі түрде бөлінеді:

K = I ++ ++ +j; - және бұл бөлу дұрыс емес, компилятор қолданушыға қате туралы хабарлама жібереді.

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

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

Лексикалық анализатордың құрылуы.

Енді сканерлердің практикалық орындалуын қарастыруға болады: Компилятордың құрамында бір емес, бірнеше лексикалық анализатор болуы мүмкін. Олардың әрқайсысы анықталған лексеманың типін тексеру және таңдау үшін арналған.

Сонымен қарапайым лексикалық анализатордың компиляторда жұмысын келесі түрде бейнелеуге болады:

• кіру ағымынан бір символ таңдалады, ол қандай сканер іске қосылатынына байланысты (символ қате болуы мүмкін);

• жіберілген сканер негізгі тілде программаның кіру символының ағымын қарастырады, келесі символды анықтағанша талап ететін лексемаға кіретін символдарды белгілейді, ол лексеманы шектеуі керек.

• белгіленген лексема туралы анықтаманың табысты анықталуы лексема кестелерін және идентификаторлар кестесіне енгізіледі, алгоритм бірінші қадамға қайтады және кіру ағымының символдарын қарастыруға жалғастырады. Жалғасы сканерлер тоқталған жерден басталады;

• егер танылу дұрыс орындалмаса қате туралы хабарлама келеді, ал қалғаны сканердің жұмысына байланысты болады – оның жұмысы тоқтатылады немесе келесі лексеманы орындайды. (алгоритмнің бірінші қадамына өту жүріп жатыр).

Лексикалық анализатордың құрылу автоматизациясы (LEX программасы).

Лексикалық танушылар (сканерлер) – бұл компилятордың маңызды бөлігі ғана емес. Сонымен қатар лексикалық анализ басқа да облыстарда қолданылады, мысалға компьютерде мәтіндік ақпаратты өңдеумен байланысты. Ең алдымен, лексикалық анализ барлық командалық процессорларды және утилиттерді талап етеді. Сонымен қатар, енгізілу мәтінінің лексикалық анализін барлық мәтіндік редакторлар және мәтіндік процессорлар қолданады.

Лексикалық анализаторды құруға арналған көптеген программалар бар. Олардың арасынан ең танымалысы LEX программасы.

LEX – сканерлерді генерациялауға арналған прграмма (лексикалық анализатордың).

LEX программасының нәтижесі, программалау тілінің кейбіреуінде болады, ол ену файлын оқиды және одан берілген айтылуларды белгілеп алады.

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

Қазіргі кезде кез келген OC үшін LEX программасының көптеген түрлері бар.

LEX тің жұмыс принципі өте жеңіл: оған енгізілуге мәтіндік файл беріледі, ал шығу кезінде сканер программасының шығу мәтінімен файл алынады. Сканердің шығу программасының мәтіні кез келген кітапханалардың кез келген функцияларымен толықтырылуы мүмкін. Осындай жағдайда LEX лексикалық анализатордың өңделуін жеңілдетеді.

№ 16 БИЛЕТ

1. Ішкі сұрыптау алгоритмдері: қосып сұрыптау, таңдап сұрыптау

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

Сұрыптау алгоритмдерінің мәліметтер құрылымын таңдауына байланысты 2 түрі бар:

а) Ішкі сұрыптау алгоритмі (массивтерді

сұрыптау);

b) Сыртқы сұрыптау алгоритмі (файл

қабырданған құрылым);

Ішкі сұрыптау алгоритмі – ішкі жадыдағы мәліметтерді сұрыптау алгоритмі. Бұл жағдайда ең қолайлы мәлімет құрылымы – массив. Бұл сұрыптау алгоритміне қойылатын ең басты талап машина жадын үнемдеу.

Сұрыптау әдістері:

а) Қарапайым сұрыптау әдісі;

b) Жетілдірілген қарапайым сұрыптау әдісі;

Қарапайым сұрыпталу әдістерінің түрлері:

а) Кірулермен сұрыптау (сортировка с простыми

включениями );

b) Таңдаумен сұрыптау (сортировка с выбором);

c) Алмасумен сұрыптау – «көбікше» сұрыпталу

(сортировка обменом или « пузырковая »

сортировка);

Жетілдірілген қарапайым сұрыптау түрлері:

а) Кемімелі өсімшелі кірулер бойынша Шелл әдісімен

сұрыптау ;

b) Ағаш көмегімен сұрыптау немесе пирамидалық;

c) Бөліктеу арқылы сұрыптау немесе жылдам

сұрыптау;

Сұрыптау алгоритмдерінің мәліметтер құрылымын таңдауына байланысты 2 түрі бар: а) Ішкі сұрыптау алгоритмі (массивтерді сұрыптау); b) Сыртқы сұрыптау алгоритмі (файл қабырданған құрылым);

Ішкі сұрыптау алгоритмі – ішкі жадыдағы мәліметтерді сұрыптау алгоритмі. Бұл жағдайда ең қолайлы мәлімет құрылымы – массив.

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

Алгоритмінің негізгі идеясы өте қарапайым. a[1], a[2], …, a[n] элементтен тұратын массив берілсін. Массивтің екінші элементінен бастап индексі кіші элементтерімен салыстыра бастаймыз. Егер a[i]>a[i-1]болса a[i+1]-ші элементті a[i]-ші элементімен т.с.с.салыстыра береміз. Осылай a[i+1]<a[i] шарты немесе массивтің басына жеткенше жалғастыра береміз. Егер a[i+1]<a[i] орындалса a[i+1] мен a[i] элементтерін орындарымен ауыстырамыз.

Кірулермен сұрыптаудың таблицалық мысылы

Бастапқы массив	8 23 5 65 44 33 1 6
1-ші қадам	8 23 5 65 44 33 1 6
2-ші қадам	8 5 23 65 44 33 1 6 5 8 23 65 44 33 1 6
3-ші қадам	5 8 23 65 44 33 1 6
4-ші қадам	5 8 23 44 65 33 1 6
5-ші қадам	5 8 23 44 33 65 1 6 5 8 23 33 44 65 1 6

6-ші қадам	5 8 23 33 44 1 65 6 5 8 23 33 1 44 65 6 5 8 23 1 33 44 65 6 5 8 1 23 33 44 65 6 5 1 8 23 33 44 65 6 1 5 8 23 33 44 65 6
7-ші қадам	1 5 8 23 33 44 6 65 1 5 8 23 33 6 44 65 1 5 8 23 6 33 44 65 1 5 8 6 23 33 44 65 1 5 6 8 23 33 44 65

2. Қатынасты нормалдау. Нормалды пішіндер

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

Нормалды формалар:

Бірінші нормальды форма. Егер қатынастың барлық атрибуттары қарапайым болса, яғни атрибуттың компоненттері болмаса, онда қатынас бірінші нормальды формада болады. Мысалы, Дата қарапайым атрибут бола алмайды, өйткені ол күн, ай, жылдар тұрады.

Екінші нормальды форма. Егер қатынастың атрибуты қатынастың қандай да бір кілтінің элементі болса, онда оны кілттік деп санаймыз. Керісінше жағдайда атрибут кілттік емес атрибут болады. Мысалы, (Қала, Адрес, Пошта_индексі) қатынасында барлық атрибуттар кілттік болады, өйткені берілген Қала, Адрес –>Пошта_индексі және Пошта_индексі- >Қала ФТ-де мына жұптар: Қала, Адрес және Адрес, Пошта_индексі кілттер болады.

Анықтама. Егер 1НФ-да болса және қатынастың барлық кілттік емес атрибуттары функциональды түрде тек қатынастың құрама кілтіне тәуелді болса, онда бұл қатынас екінші нормальды формада (2НФ) болады.

Үшінші нормальды форма.

Егер 2НФ-да болса және қатынастың барлық кілттік емес атрибуттары тек бастапқы кілтке тәуелді болса, онда бұл қатынас үшінші нормальды формада (3НФ) болады.

Бойс-Коддтың нормальды формасы.

Егер 3НФ-да болса және қатынаста кілттік атрибуттардың кілттік емес атрибуттарға тәуелділіктері болмаса, онда бұл қатынас Бойс-Коддтың нормальды формада (БКНФ) болады.

Төртінші нормальды форма.

Егер 3НФ-да немесе БКНФ-да болса және барлық тәуелсіз көп мағыналы ФТ бірдей кілтпен жеке қатынастарға жазылса, онда қатынас төртінші нормальды формада (4НФ) болады.

Бесінші нормальды форма.

Егер қатынас 4НФ-да болса және өздерінің проекцияларына қатынасты қосылу тәуелділіктерін қанағаттандырса, онда қатынас бесінші нормальды формада (5НФ) болады.

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

Атрибут қатынас құрамы келесі талаптарды қанағаттандыру қажет:

- атрибуттар арасында қажетсіз функционалды тәуелдіктер болмау қажет;

- атрибуттардың топтасуы деректердің минималды қайталануын қамтамасыз ету қажет, олардың өңдеуін және жаңаруын қамтамасыз ету қажет.

Бұл талаптар қатынастардың нормализациясы арқылы орындалады.

Қатынастарды нормализациялау –қажетсіз функционалды тәуелдіктерді және әртүрлі ауытқуларды жою мақсатында ДБ-ның бастапқы қатынастарын ұсақ және қарапайым қатынастарға декомпозициялау процесі. Яғни, деректер базасындағы қатынастарды қандай да бір қалыпты түрге түрлендіру процесі.

Алты нормальды форма бар: 1НФ, 2НФ, 3НФ, Бойсс-Кодд нормальды формасы, 4НФ, 5НФ. Әрбір нормальды форма рұқсаты етілген функционалды тәуелділіктердің анықталған типтерді шектейді.

Қатынасы 1НФ болады, егер оның барлық атрибуттары қарапайым болып табылса, барлық қолданылған домендер тек скалярлы мәннен тұруы керек. Кестеде қайталанатын жолдар болмауы керек.

Екінші нормальды форма

Қатынас 2НФ болады, егер ол 1НФ – те табылса және әрбір кілттік емес атрибут Алғашқы Кілттен келтірілмеген(неприводима) тәуелді.

Үшінші нормалды форма

Қатынас 3НФ болады, ол 2НФ-те табылса және әрбір кілтті емес атрибут алғашқы кілттен транзитивті емес тәуелді болады. Былайша айтқанда, бөлек кестелердегі бірнеше жазбаларына қатысты болатын мазмұны, екінші ереже барлық кілттік емес алаңдарды көтеруді талап етеді.

Бойс-Кодд нормалды формасы (БКНФ).

3НФ анықтамасы келесі қатынастарға мүлдем келіспейді:

1) Қатынас екі немесе одан да көп потенциалды кілтке ие;

2) Екі немесе одан да көп потенциалды кілт құрамды болып табылады;

3) Олар қиылысады, яғни, тым болмағанда бір атрибутқа ие.

Алғашқы кілтке ие қатынас үшін БКНФ, 3НФ болып табылады.

Қатынас БКНФ-те табылады, егер әрбір нақты(нетривиальные) және келтірілмеген сол жақты функциональды тәуелділік детерминант қасиетінде потенциалды кілтке ие болса.

БКНФ-ты кейде нығайтылған үшінші нормалды форма деп те атайды, ойткені ол алдында анықталған 3НФ-пен салыстырғанда күштірек болғандықтан.

Төртінші нормалды форма.

Қатынас 4НФ-те табылады, егер ол БКНФ-те табылса және барлық нақты (нетривиальные) көпмәнді тәуелділіктер фактілі түрде оның потенциалды кілтінен функционалды тәуелділік болып табылады.

R қатынасында R көпмәнді тәуелділік болады. A -> -> R. Сол жағдайда және тек сол жағдайда, егер B көпмәндері, А және C жұп мәніне сәйкес болса, тек А – дан тәуелді және С – ға тәуелді емес.

Алтыншы нормалды форма

Айнымалы қатынас алтыншы нормалды формада табылады сонда және тек сонда, егер ол бірігудің барлық нақты тәуелділіктерін қанағаттандырғанда. Анықтамадан айнымалы 6НФ-те табылады, сонда және тек қана сонда, егер ол келтірілмген, яғни одан арғы ыдыруға жоғалтусыз ұшырамаған болса ереді. Әрбір 6НФ-те табылатын айнымалы қатынас, сонымен қатар, 5НФ-те де табылады.

3. LEX лексикалық талдау құрастырушысы

Әрбір лексемамен 2 ұғым байланысты:

1. Лексема класы;

2. Лексема мәні.

Транслитератор.

1. Әріп-әріптер жиынына сәйкес қойылатын класс, бұл әріптердің бір

алфавиттен болуы шарт емес.

2. Сан-көбінесе 0 ден 9-ға дейінгі сандарға қатысты символдар жиыны;

3. Бөлектегіш - пробел, жолды ауыстыру;

4. Ескерту-тілдің алфавитіне тиісті емес символдар;

5. Басқалар-белгілі категориялардың ешбіріне жатпайтын символдар.

диаграммасымен ақырлы автоматтар арасында бір мәнді сәйкестік бар.

Терминалдардан ғана тұратын Вирт диаграммасына эквивалентті ақырлы

автомат мынадай түрде құралады:

1. Диаграмманың бастапқы доғасы арқылы автоматтың бастапқы жағдайына түрленеді.

2. Диаграмманың доғасы ақырлы автоматтың бекітуші жағдайына түрленеді.

3. Ақырлы автоматтың құралуын идентификатордың сипаттау мысалында көруге болады.

А) Қарапайым грамматиканы түрлендіру:

Вирт диаграммасымен сол жақ рекурсияның грамматикасы арасындағы

1) Рекурсивті анықталатын терминал емес тен шығатын доға, цикл құру

арқылы ереженің ең соңын әкеліп қосылады.

2) Адресаты жоқ терминал еместер сызылып тасталынады, ал оған

кіретін доға алынып тасталады.

Лексикалық талдау.

Программалау тілінің көпшілігінде келесі лексикалық класстар бар:

* негізгі сөздер

*идентификаторлар

*жолдық интегралдар

*сандық константтар

Мысалы: const pi = 3.1416.

Паскаль тілінің операиторын қарастырайық. Бұл оператор келесі лексемалардан тұрады:

- Const – лексикалық класс, const LS

- Pi лексикалық класс Identifier LS

- =- лексикалық класс Relation LS

- 3.1416- блексикалық класс Number LS

- ; - лексикалық класс Semicolon LS

Программалау тілінің әртүрлі лексикалық талдауы.

Алгол 98 немесе Фортран пробелдері жолдық интегралдарға байланысты.

If then then then = else ; else; else =then;

Лексикалықанализатордыңтағайындалуы.

Лексикалықанализатордықарастырғанғадейін, лексеманеекенінбіліпалуымызкерек.

Программалаутілдерініңқұрамыосытілдіңсинтаксисіменанықталады.

Лексикалық және синтаксистік анализаторлар арасындағы байланыстардың екі түрлі әдісі бар:

• жүйелік

• параллельдік

... Begin

For i: = 1 to N do

Fg : = fg *0.5

2. Лексикалық анализатордың құрылу принциптері.

Сканер келесі іс - әрекеттерді орындау керек:

• лексеманың шекарасын толық анықтауы керек, олар шығу мәтінінде берілмеген;

• ақпаратты сақтау үшін, белгілі бір іс - әрекеттерді орындауы керек.

Лексемалардың шекараларын анықтау.

Маңыздысы, операция белгілері лексемалар болады және оларды жіберуге болмайды.

Мысалы, жоғарыда көрсетілген С тілінің жолы k = i +++++ j; лексемаларға келесі түрде бөлінеді:

K = I ++ ++ +j; - және бұл бөлу дұрыс емес, компилятор қолданушыға қате туралы хабарлама жібереді.

Лексикалық анализатордың құрылуы.

Сонымен қарапайым лексикалық анализатордың компиляторда жұмысын келесі түрде бейнелеуге болады:

Лексикалық анализатордың құрылу автоматизациясы (LEX программасы).

LEX – сканерлерді генерациялауға арналған прграмма (лексикалық анализатордың).

Қазіргі кезде кез келген OC үшін LEX программасының көптеген түрлері бар.

№ 17 БИЛЕТ

1. Екілік қосылуға талдау. Алмасып сұрыптау алгоритміне талдау

Екілік қосылуға талдау- бұл әдіс қарапайым кірістіру әдісінің жақсартылған нұсқасы болып табылады. Бұның негізгі түсінігі ең алдымен элементке қойылатын орын іздейміз содан кейін сонда орналастырамыз. Бұның ең басты айырмашылығы орын табу әдісінде болып тұр.

Егер массив реттелген болса, онда бинарлы-екілік іздеуді қолдануға болады. Оны логарифмдік іздеу немесе дихотомия әдісі дейді.

Мұнда екі көрсеткіш пайдаланады: l=1 массивтің алғашқы элементін көрсетеді, u=n массивтің соңғы элементін көретеді:

1. l=1; u=n; болады

2. егер u<l болса, онда алгоритм сәтсәз аяқталады, әйтпесе [l,u] аралығының ортасын табамыз. Осы моментте ізделінді k элементі массивте бар болса, al<=k<=au шартының орындалатынын білеміз. I=(l+u) div 2 деп аламыз , сонда I массивтің ортасын көрсетеді.

3. Егер k<ai болса, онда 4-ші пунктке көшеді, егер k>ai болса, онда 5-ші пунктке көшеді, егер k=ai болса, онда іздеу сәтті аяқталады.

4. u=i-1 деп орналастырамыз және 2-ші пунктке көшеміз

5. l=i+1 деп орналастырамыз және 2-ші пунктке көшеміз.

Бұл алгоритмде күрделілік дәрежесі -ге тең болады.

Алмасып сұрыптау алгоритміне талдау

Алмастыру (көпіршікті) арқылы сұрыптау

1. Бірінші екі элементті салыстырамыз. Егер бірінші элемент екіншісінен үлкен болса, онда олардың орындарын ауыстырамыз.

2. Екінші элементте үшіншісімен, үшіншісі мен төртіншіні, дәл солай ... барлық элементтерді соңғысына дейін салыстырып, қажеттілік болса олардың орындарын ауыстыру керек. Мұнда ең үлкен элемент соңғы орында болады.

3. Массивты элементтерін бір бірлікке азайту арқылы қарау. Массив бірінші мен екінші элементтерді қарастырғаннан кейін сұрыпталады.

Алмастыру(көпіршікті) арқылы сұрыптау

for i:=2 to n do

for j:=n downto i do

if a[j-1]>a[j] then

begin

x:=a[j-1];

a[j-1]:=a[j];

a[j]:=x;

end;

Бұлалгоритмдітүсінужәнеіскеасыру - еңқарапайым, бірақолшағынмассивтерүшінтиімді.Бұлалгоритмкүрделілігімынағантең - O(N*N).

2. «Болмыс-байланыс» (ER-диаграмма) әдісін қолданып жобалау

«Болмыс-байланыс» ER-диаграмма әдісі деп аталады:ең алдымен ER Entity (болмыс) и Relationship (байланыс сөздерінің аббревиатурасы).Бұл әдіс диаграамаларға негізделген.

«Болмыс-байланыс» әдісінің негізгі ұғымдары мынала кіреді:

1) болмыс;

2)болмыс атрибуты;

3) болмыстың кілті;

4) субъектілер арасындағы қарым-қатынас;

5) байланыс дәрежесі;

6) болмыс экземплярына тиесілі класс;

7) ER-даналарының диаграммалары;

8) ER-типті диаграммалар.

Болмыс ақпараты дерекқорда сақталатын объект болып табылады.Болмыс атаулары, әдетте, зат есімдер болып табылады, мысалы: ОҚЫТУШЫ, Пән аты, Кафедра, ТОБЫ.

Атрибут - бұл болмыс сипаты. Осылайша, ОҚЫТушы болмысының сипаты оның Тегі, қызметі, тәжірибесі және т.б. болуы мүмкін.

Болмыстың кілті – атрибут, болмыс экземплярын анықтауға арналған ;

Қарапайым мысал: ОҚЫТУШЫ Беретін Пәні (Иванов үйретеді Деректер базасы).

3. Төмендемелі синтаксистік талдау. LL(1)-грамматикалары. Рекурсивті түсу
Синтаксистік талдау – бұл процесс, онда лексем таблицасы орнатылады. Ол құрылымды шартты қамтамассыз етеді. Формуляцияланған және синтаксистік тілде анықалғаны анық.Синтаксистік талдаудың нәтижесі синтаксистік ағаш таблица объектісіне жіберу болып табылады. Синтаксистік талдаудың процесінде қателар табылады, программа құрылымымен байланысты.

2- алгоритмі бар

-Төмендемелі синтаксистік талдау (LL(1)-грамматикалары. Рекурсивті түсу)

- Өрлеуші синтаксистік талдау. (Жылжыту-үйіртпе түріндегі типтерді төменнен жоғары қарай жіктеу. LR(1)-талдауыштары)

Төмендемелі талдауы кіріс жолы LL (k) деп сипатталған кейбір ресми тілге жататындығын анықтаудың әдістерінің бірі болып табылады, бұл контекстсіз грамматика.

LL (1) грамматикалық анықтамасы.

Бұл идеяның логикалық жалғасуы, рекурсивтік көшуге байланысты , ол енгізу тізбегінде бірнеше символдарды қолданумен қатар , альтернативті біреуін ғана қолданумен түсіндіріледі. Егерде альтернативті алгоритмді таңдайтын болсақ, онда ереже бойынша, грамматикалық әртүрлі тізбектері бар екендігін көреміз. Сонымен қатар грамматикалар классы пайда болды, бұл негізгі принципке арналған- альтернативті бір тізбекті таңдасақ, онда көршілік мүмкіндіктердің негізінде бірнеше кезекті тізбек символдарын кездестіреміз. Бұл тізбекті біз LL (1) грамматикасы деп атаймыз. Шынымен, жұмыс алгоритмі бұларға өте оңай келмейді, қарастырылған жоғарыдағы алгоритм рекурсивті өтуге сәйкес келеді.

LL (1) - LL-анализатор, талдаудың төмендетілген алгоритмі. 1 нөмірі парсинг жолын анықтау үшін тек бір лексем қажет.

Автоматты генераторларды пайдаланбай қолмен жазу оңай. Паскаль сияқты бағдарламалау тілдерінде кодты талдау үшін пайдаланылады.

Өте жылдам орындалуда және «мұндай символы күткен болатын» сияқты қате туралы хабар бар.

Рекурсивтік түсу.

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

Рекурсивтік түсудің негізгі әдісі, әрбір грамматиканың терминалсыздығына процедура сәйкес келеді, ол процедура терминалсыздықты тудыратын тізбекті анықтайды. Сондықтан, МП – түрлендіргіштің модельдеуі рекурстік процедуралардың механизмімен алмасады. Жоғарғы деңгейдегі тілдер қиын стектік механизмдерді қолданады, МП – автоматы орындалуына қарағанда. Рекурсивтік түсудің әдісі уақыт мөлшерін және жадының синтаксистік сараптаудың әдісіне қарағанда жол береді.

Рекурсивтік түсудің әдісі кез – келген LL(1) – грамматикасына қолданылады, ол баламалық оң бөлшектерінің формасында жазылу керек.

№ 18 БИЛЕТ

1. Ішкі сұрыптау алгоритмдері: шейкерлік сұрыптау, бөліп сұрыптау

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

Шейкерлік сұрыптау: ішкі циклдің ішіндегі өтулердің бағыттаррын өзгертіп отыру керек, сөйтіп элементтердің орындарын ауыстыруларынның бағыт бойынша және кері бағыттағы «ассиметриялылығын» компенсациялауға болады.

Біріншіден, егер массив бөлігінде қозғалыстарда орын ауыстырулар болмаса онда массивтің бұл бөлігі сұрыпталған болып есептеледі, сондықтан, оны қарастырудан алып тастауға болады.
Екіншіден, массивтің соңынан басына дейін өткенде минималды элемент бірінші позицияға тұрады, ал максималды элемент тек бір позицияға оң жаққа қарай қозғалады.
Массивтің жұмыс бөлігінің шектері әр итерацияның орын ауыстыруында орнықтырылады. Массив рет бойынша оң жақтан сол жаққа және сол жақтан оң жаққа кезек кезек қарастырылады.
Бұл сұрыптаудың үздік жағдайы — сұрыпталған массив (О(n)), ең жаманы — кері бағытта сұрыпталған массив (O(n²)).
Салыстырулар санының ең кіші мәні Шейкер-сұрыптауында C=N-1. Бұл сұрыпталған массивте тек бір өтуге сәйкес (үздік жағдай)

Бөліктеу арқылы сұрыптау немесе жылдам сұрыптау

Бөліктеу арқылы сұрыптау Чарльз Хоармен 1962 жылы ұсынылған. Бұл үрдіс сұрыптау үрдістерінің жетілген және соншалықты тиімді әдісі болғандықтан оны жылдам сұрыптау депте атап кеткен.

Алгоритмнің негізгі идеясы кездейсоқ тәсілмен массивтің кез-келген х элементі таңдалынып алынып, сол жақтан бастап х элементінен үлкен элемент кездескенше қарастырыла береді. Содан кейін оң жақтан бастап кіші элемент кездескенше қарастырады. Осы екі элементтер орындарымен алмастырылады да, ары қарай х элементіне жеткенше жалғастырыла береді. Нәтижесінде оң жағында х санынан үлкен және сол жағында х санынан кіші екіге бөлінген массив аламыз.

Ары қарай рекурсивті түрде оң және сол жақ бөліктерге қайталанады. Бұл процесс әр бөлікте бір элемент қалғанша жалғасады. Әрине, егер массивтің индекстерін сақтап отырса рекурсияны итерациямен алмастыруға болатыны түсінікті.

2. Заманауи ДҚБЖ таңдау. Дара, топтық, корпоративтік ДҚБЖ

Қазіргі заманғы ДҚБЖ таңдау. Реляциялық деректер базасының объектілері ДҚБЖ таңдауда әсер ететін факторлар:

1) Қолданушының талабы;

2) Деректер қорының (Ақпараттық жүйенің архитектурасына бйланысты (м/ы; клиент – сервер, орталықтандырылған, объектіге бағытталған т.б);

3) Деректердің моделі;

Әдетте ДББЖ таңдағанда барлық тең мүмкіндікті жағдайда өндірістік стандартқа үміткер болатын ДББЖ – де деректер базасын жасауға тырысады. ДББЖ таңдау бұл таңдаудың көп өлшемді есептеріне жатады. Жалпы түрде айтсақ, ДББЖ деректердің тек бір моделін: реляциялық, иерархиялық желілік, көпөлшемді, объектіге бағытталған, объектілік – реляциялық модельдердің біреуін ғана қолдайтынын есте сақтау керек. ДББЖ – нің біразы бұған қосылмайды. М/ы, ADABAS, Software AG (желілік және реляциялық модельдер), немесе Oracle 9i, Oracle inc (реляциялық және объектілік – реляциялық модельдер).

Реляциялық деректер базасының объектілерінің иерахиясы SQL-дің стандарттарында баяндағанда, соның ішінде SQL-92 стандартында жазылған. Бұл стандартта іс жүзінде барлық қазіргі заманғы ДББЖ, соның ішінде үстелдік ДББЖ дейін қолдайды.

Ең төменгі деңгейде реляйиялық деректер базасы жұмыс істейтін ең кіші объектілер – бағандар мен жолдар орналасады. Олар өз кезегінде кестелер мен көрсетімдерге топтастырылуы мүмкін.

Дара, топтық, корпоративтік ДҚБЖ.Ақпараттық жүйелер мен деректер базасы масштабына байланысты Жеке(дара), топтық, корпоративтік түрлерге бөлінеді.

Дара түрі. Дара(жеке) ақпараттық жүйе ортақ деректер қорымен байланысатын бірнеше қарапайым қолданбадан (программа) тұрады (Clarion, Clipper, FoxPro, Paradox, dBase, MS Access)..

Топтық түрі. Топтық жүйелер бір мекеменің жұмыс тобының мүшелерінің ақпаратты ұжымдық түрде қолдануына бағытталып, көбінесе жергілікті есептеу желісі, сирек түрде көп терминалды орталықтанған есептеу жүйесі түрінде қолданылады.(Btrieve, NetWare SQL, Gupta SQLBase, Sybase Anywhere SQL, MS SQL Server, Progress, Informix-SE, Workgroup Oracle идр.).

Корпоративтіктүрі. Кампустықжелініңдамығантүріболыптабылатын, үлкентерриториянықамтитынжанжаққатаратылғантүйіндергебағытталғанақпараттықжүйелердікорпоративтіктүрідепаталады. Корпоративтік ДББЖ-лардың көбінесе 2 деңгейлік: клиент-сервер модель түрінде болады. Мысалы, корпоративтік ақпараттық жүйелерде қолданылатын ДББЖ Oracle 7, Sybase және тағы басқа жатады.

3. Төмендемелі синтаксистік талдау. Контексті-еркін грамматикаларды түрлендіру. Сол жақ рекурсияны алып тастау. Сол жақ факторизация. LL(1) талдаудың артықшылықтары мен кемшіліктері

Синтаксистік талдау – бұл процесс, онда лексем таблицасы орнатылады. Ол құрылымды шартты қамтамассыз етеді. Формуляцияланған және синтаксистік тілде анықалғаны анық.Синтаксистік талдаудың нәтижесі синтаксистік ағаш таблица объектісіне жіберу болып табылады. Синтаксистік талдаудың процесінде қателар табылады, программа құрылымымен байланысты.

2- алгоритмі бар

-Төмендемелі синтаксистік талдау (LL(1)-грамматикалары. Рекурсивті түсу)

Төмендемелі талдауы кіріс жолы LL (k) деп сипатталған кейбір ресми тілге жататындығын анықтаудың әдістерінің бірі болып табылады, бұл контекстсіз грамматика. Бұл жерде ереже бастапқы символдан басталады, және қажетті токен реті анықталғанша жүреді.

Сол жақ факторизацияның негізгі идеясы

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

Егер A ₁ | ₂ - екі A-ереже және енуші тізбек -дан шығатын бос емес қатардан басталса, біз қайыруды бірінші немесе екінші ереже бойынша жасауды білмейміз. Былайша қайырып: A A' , шешімді қоя тұруға болады. -дан не шығатынын анализ жасап болған соң A' ₁бойынша немесе A' ₂ бойынша қайыруға болады.

LL(1) талдаудың артықшылықтары мен кемшіліктері

-Уақыт үнемдейді

- 1- рет символды тексеру арқылы тексеруге болады

Кемшілігі

-бұл тілдің бұл классқа жататыны не жатпайтынын анықтайтын нақты алгоритм жоқ.

Сол жақ рекурсияны алып тастау.

Тікелей сол жақ рекурсиясы, яғни мына формадаы рекурсияны , келесі жолмен жойылуы мүмкін. Алдымен A-ережесін жасаймыз:

онда жолдары A басталмайды. Содан кейін осы ережелер жиынтығын мынаған

Ауыстырыңыз . A' – жаңа нетерминал.

Контексті-еркін грамматикаларды түрлендіру.

Контексті-еркін- бұл барлық өнімдердің сол жақ бөліктері бірыңғай нетерминал (тілдің кез-келген субъектісін білдіретін (мысалы, формула, арифметикалық өрнектер, командалар) және нақты символдық мәнге ие емес) болатын формальды грамматиканың ерекше жағдайы. CS-грамматикасы арқылы анықталатын тіл Контексті-еркінтіл немесе CS-тілі деп аталады.

№ 19 БИЛЕТ

1. Медиананы табу.(латын МЕДІАНА -. Орта) математикалық статистика - үлгісі сипаттайтын саны (мысалы, сандар жиынтығы). үлгідегі барлық элементтері, медианасы түрлі болса - бұл үлгісі элементтерінің дәл жартысы ол артық, және оған басқа жартысы кем үлгілердің саны болып табылады. Тұтастай алғанда, медианасы элементін арту немесе кему үлгі элементтері сұрыптау және орташа қабылдау арқылы табуға болады. тапсырыс {3, 5, 5, 9, 11} түрлендіріледі және элементтердің үлгісі тіпті саны болса, оның орташа саны 5. кейін Мысалы, үлгісі {11, 9, 3, 5, 5}, медианасы мағыналы анықталады болуы мүмкін емес: сандық деректер жиі екі көрші құндылықтарды жартысы сомасын пайдалану үшін, көп см (жиынтығы яғни, медианасы {1, 3, 5, 7} 4 тең қабылданады). төмен.

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

Медиа́на (от лат. mediāna — середина) в математической статистике — число, характеризующее выборку (например, набор чисел). Если все элементы выборки различны, то медиана — это такое число выборки, что ровно половина из элементов выборки больше него, а другая половина меньше него. В более общем случае медиану можно найти, упорядочив элементы выборки по возрастанию или убыванию и взяв средний элемент. Например, выборка {11, 9, 3, 5, 5} после упорядочивания превращается в {3, 5, 5, 9, 11} и её медианой является число 5. Если в выборке чётное число элементов, медиана может быть не определена однозначно: для числовых данных чаще всего используют полусумму двух соседних значений (то есть медиану набора {1, 3, 5, 7} принимают равной 4), подробнее см. ниже.

Также медиану можно определить для случайных величин: в этом случае она делит пополам распределение. Грубо говоря, медианой случайной величины является такое число, что вероятность получить значение случайной величины справа от него равна вероятности получить значение слева от него (и они обе равны 1/2); более точное определение см. ниже.

Сыртқы сұрыптау алгоритмдерін талдау.

Сыртқы сұрыптау - перифериялық құрылғыларда орналасқан және жадыда емес деректерді сұрыптау, яғни ішкі сұрыптардың бірі қолданылмайды. Айта кету керек, ішкі сұрыптау сырттай қарағанда әлдеқайда тиімді, себебі магниттік дискілерге, таспаларға және т.б. қарағанда, ЖЖҚ-ға кіруге әлдеқайда аз уақыт кетеді.

ДББЖ-да жиі сыртқы сұрыптау қолданылады. Сыртқы сұрыптауды пайдалану кезінде негізгі ұғым - бұл сегменттің ұғымы. Сегмент ұзындығы {\ displaystyle K} К жазбалардың тізбегі {\ displaystyle A_ {Мен}} A_ {Мен}, {\ displaystyle A_ {і + 1}} A _ {{і + 1}}, ..., {\ displaystyle A_ { i + k}} A _ {{i + k}}, онда барлық жазбалар кейбір кілтпен реттеледі. {\ Displaystyle N} N файлындағы сегменттердің ең көп саны (барлық элементтер тапсырыс берілмеген). Сегменттердің ең аз саны - 1 (барлық элементтер тапсырыс берілді).

Мысалы, кейбір файлда бір өлшемді массив бар:

12 35 65 0 24 36 3 5 84 90 6 2 30

Жиынды сегменттерге бөлейік:

12 35 65 | 0 24 36 | 3 5 84 90 | 6 | 2 30

А файлындағы файл 5 сегменттен тұрады деп айтуға болады.

Мысалы, кейбір файлда бір өлшемді массив бар:

1 2 3 4 5 6 7 8 9 10

Жиынды сегменттерге бөлейік:

| | 1 2 3 4 5 6 7 8 9 10 |

B файлындағы жиым 1 сегменттен тұрады деп айтуға болады.

Мысалы, кейбір файлда бір өлшемді массив бар:

20 17 16 14 13 10 9 8 6 4 3 2 0

Жиынды сегменттерге бөлейік:

| | 20 | 17 | 16 | 14 | 13 | 10 | 9 | 8 | 6 | 4 | 3 | 2 | 0 |

А файлдағы массив 13 сегменттен тұрады деп айтуға болады.

Сыртқы сұрыптау - бұл сыртқы құрылғыларда орналасқан және ЖЖҚ-ға сәйкес келмейтін деректерді сұрыптау.

Сыртқы сұрыптар үшін ең танымал алгоритмдер:

Сұрыптаудың негізгі әдістері:

Табиғи сұрыптау (табиғи синтез әдісі)

Екі жақты теңдестірілген біріктіру әдісі бойынша сұрыптау

N-way біріктіру бойынша сұрыптау.

Көпфазалы сұрыптау (Fibonacci)

біріктіру сұрыптау (қарапайым біріктіру және табиғи біріктіру);

Жақсартылған сұрыптау (көпфазалық сұрыптау және каскадты сұрыптау).

Ұсынылған сыртқы сұрыптаудан ең маңыздысы біріктіру әдісімен сұрыптау әдісі болып табылады. Біріктіру сұрыптау алгоритмін сипаттамас бұрын, біз бірнеше анықтаманы енгіземіз.

Сыртқы сұрыптауды пайдалану кезінде негізгі ұғым - серия ұғымы. Серия (реттелген сегмент) - кілтпен реттелетін элементтер тізбегі.

Сериядағы элементтер саны серияның ұзындығы деп аталады. Бір элементтен тұратын серия әрдайым тапсырыс берілді. Соңғы сериялар файлдардың қалған серияларынан ұзынырақ болуы мүмкін. N файлындағы эпизодтардың ең көп саны (барлық элементтер тапсырыс берілмеген). Эпизодтардың ең аз саны - бір (барлық элементтер тапсырыс берілді).

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

Фаза - бұл элементтердің бүкіл тізбегін бір рет өңдеуге арналған әрекет. екі фазалы сұрыптау - сұрыптау, екі фаза бөлек сатылады онда: бөлу және біріктіру. Бір фазалық сұрыптау - бөлу және біріктіру фазалары бір біріктірілетін сұрыптау.

Сұрыптаудың баламалы әдістері

Алгоритмдерді сұрыптау түрлері

Көпіршікті әдіспен сұрыптаудың алгоритмі - іргелес жұп элементтерін дәйекті ауыстыруды жүзеге асыратын дәйектілікті қарапайым және баяу сұрыптау. Іріктеу тәртібінде сұрыптау кезінде үлкен мәнге ие элементтер массивтің соңына дейін жылжиды және басталу шамасына дейін азаяды.

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

Жылдам сұрыптау алгоритмі - ең жылдам, қолданыстағы ішкі сұрыптау алгоритмдері.

Араластыру сұрыптау алгоритмі - баламалы атаулар - шайқаушы сұрыптау немесе қос бағытты көпіршікті сұрыптау. Көпіршікті сұрыптаудың вариацияларының бірі.

Араластыру сұрыптау алгоритмі (Шейкер сұрыптау, қос бағытты көпіршікті сұрыптау)

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

Сұрыптау алгоритмінің өсу тәртібіндегі механизмі келесідей:

- алаптың диапазонының басы мен соңы таңдалады. Алаптың соңында біреу аз;

- массивтің соңына дейін үлкен мәнді шығаратын жүйелі түрде салыстыру және ауыстыру орындалады;

- массивтің өңдеу ауқымы бірінен соңына дейін азаяды;

- массивтің дәйектілікпен өтуі, басталуына кіші мәнді шығару;

- массивтің өңдеу ауқымын басынан бірлікке дейін азайту.

2. ДҚ құру және түрлендіру

1.Концептуалды жобалау. Логикалық жобалау. Физикалық жобалау.

Реляциялық Деректер базасы моделi объектiнiң барлық ерекшелiктерiн сипаттай алмайды. Ал, концептуальдық модельдер объектiнi толығырақ сипаттайды.

Концептуальды деректер моделi екiге бөлiнедi:

Объектiге бейiмделген модель (объектно-ориентированная модель)-бұл деректердi жазба түрiнде емес объектi тұрiнде суреттейтiн модель.

Семантикалық модель-бұл қатынастың мағынасын және категориясын сипаттайтын модель.

Концептуальды деректер моделiнiң негiзгi элементтерi: объект және қатынас.

Объектi дегенiмiз-тұтынушы қолданатын модельденетiн зат. Объектiге мысал ретiнде адамдарды, үйдi, заводтарды, машиналарды және т.б. алуға болады. Бұлардың барлығы нақты объектiге жатады.

Концептуальды объектiлерге компаниялар, мекемелер, құрылыстардың жобалары, жұмыс операциялары жатады.

Мыс: Бiртектес заттарды сипаттау үшiн “объектiлiк жиын“ терминiнi қолданамыз. Ал, оның 1 элементiн объектiлiк элемент деп атаймыз. Объектiлiк жиынның аты үлкен әрiппен жазылады. (жекеше түрде). Кiшi әрiптермен оның элементтерi жазылады.

Объектiлiк жиын дегенiмiз бiртектес элементтер жиыны.

Ал объектiнiң элементi дегенiмiз жиынның арнайы бiр элементi.

Екi объектiлiк жиынның элементiнiң байланысын қатынас деп атаймыз.

Концептуалды модель құру жолдары

ДБ жобалау нәтижесіндегі жүйені құру барысы, ақпарат жинақтау, талдау процесі, қолданылу кезеңі жүйенің өмір сүру циклідеп аталады. Ол процесс талап-тілекті анықтау, жүйені жобалау, тексеру, жүйе жұмысын бағалау және қолдау жасап отыру қадамдарынан тұрады.

ДБ-ның өмір сүру циклі 6 кезеңнен тұрады:

Алдын-ала жоспарлау;
Жүзеге асырылу мүмкіндігін тексеру;
Талаптарды анықтау;
Концептуалды жобалау;
Жүзеге асыру;
Жұмысты бағалау және оған қолдау жасау.

Алдын-ала жоспарлау–ДБ-ның стратегиялық жоспарын құру процесі. Мұнда пәндік облысқа сәйкес жобаланатын ДБ-ң қандай мақсатта құрылатыны, оған қандай және қанша қолданбалы программалар пайдаланылатыны, қосымшалар мен файлдар саны мен байланысы, қандай ДББЖ-сін қолдану тиімділігі анықталады.

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

Талаптарды анықтау кезеңі ДБ мақсатын анықтау, оның пайдаланушыларының міндеттері мен талап-тілектерін айқындау, техникалық және программалық қамсыздандыру мәселелерін шешеді.

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

Бағалау – пайдаланушылар арасында ДБ туралы пікір жинау, бұл жіберілген қателіктер мен кемшіліктерді анықтау және келешекте жетілдіру барысында аталмыш қателерді жібермеу мақсатында жүргізіледі.

Жүйені қолдау – оны жетілдіру үшін қажетті программалар, қосымшалар, мәліметтер элементтерін кірістіру жұмыстарын қамтиды.

Деректер базасын жабалауда алдымен негiзгi екi проблема шешiлуi керек:

1) Деректер базасының моделiн қандай тәсiлмен өрнектегенде оның (сипаттамасына) қайшылық келмейдi, тiптi ең қолайлы болатындай жолды қалай табу керек. Бұл проблеманы Деректер базасын жобалаудың логикалық проблемасы деп атайды.

2) Деректер базасына қойылған сұраныстың тиiмдi орындалуын қандай жолмен қамтамасыз етуге болатын, яғни арнайы Деректер базасын басқару жүйелерi ерекшеленгiн ескере отырып, сыртқы жадыға деректердi қалай орналастыруға болатынын табу керек болып табылады. Бұл проблеманы Деректер базасын жобалаудың физикалық проблемасы деп аталады.

Реляциялық Деректер базасын жобалаудың проблемалары негiзделген шешiмдердi қабылдаудан тұрады.

Олар:

- Деректер базасы қандай қатынастарын құру керек;

- бұл қатынастардың қандай атрибуттары болу керек

Деректер базасын жобалағанда тек кейбiр онша үлкен емес мекемелер деректерiн толығымен бiр интегралдық Деректер базасына сыйғыза алады. Деректер базасы администраторы мекеменiң қызметкерлерiнiң барлық ақпараттық талаптарын қамтамасыз ете алмайды.

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

Инфологиялық мәліметтер моделi математикалық формулалармен, кестелермен, графиктермен өрнектеледi. Деректер базасын жобалайтын мұндай адамдарды инфологиялық модель құрушылар деп атайды.

Деректер базасының қатынастары арасындағы байланысты, байланыс қуаттылығын көрсетуде ER-диаграммасы қолданылады. Бұл “объект-қатынас” моделі деп аталады.

Деректер базасын басқару жүйесiнен керектi деректердi iздеп табу сыртқы жадыдан физикалық модель арқылы табылады. Деректер базасын басқару жүйесiнiң тiлiмен өрнектейтiн модель даталогиялық модель деп атайды.

Банкiнiң объектiлерiнiң арасындағы қарапайым қатынастарды анықтау үшін төмендегі мәселелерді шешу керек:

Бiзде қанша ағымдағы шот бар?
Қанша жинақ шоты бар?
Қанша клиент бар?

Бұл сұраққа жауапты осы объектiлiк жиындардың әрқайсысының элементтерiнiң санын есептеп шығарып алуға болады. Мұнда файлдық жүйелерге қарағанда ДБ-сы бұл сұрақтарды түсiнiктi қылып түсiндiредi.

Файлдық жүйеде ДБ-сын қамтамасыз ететiн файл аралық байланыс болмаған кезде онда тек екi файл болуы мүмкiн. Оның бiреуi жинақ шотына арналған, ал екiншiсi ағымдағы шотқа арналған. Осы файлдардың әр қайсысында клиент туралы ақпараттар бiрнеше өрiстерге бөлiнiп жазылады. Ал қанша клиент бар деген сұраққа жауап алу оңай емес. Себебi, осы файлдан клиент туралы деректердi ажыратып алып, қайталаннған тұстарды алып тастау керек.

ДБ-сында клиенттер туралы деректер жеке сақталынады. Клиенттердiң қайсысының ағымдағы және жинақ шоты бар деген сұраққа жауап iздейiк. Бұл сұраққа тек қатынастарға қарап жауап беруге болады. Айталық, клиенттiң ағымдағы шоты бар, егер объектiлiк жиынның кейбiр ағымдық шоты элементi ағымдағы шоты бар клиентпен байланысты болса.

3. Өрлеуші синтаксистік талдау.

Талдау - бұл ресми грамматикамен тілдің таңбалауыштарының (сөздер, белгілер) сызықтық реттілігін сәйкестендіру процесі. Нәтиже, әдетте, талдау парағы (синтаксистік ағаш) болып табылады. Әдетте лексикалық талдауымен бірге қолданылады. Парсер - бұл бағдарлама немесе талдауды жүзеге асыратын бағдарламаның бөлігі.

Ағаштағы өрнекті талдаудың мысалы

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

Әдетте, талдаудың нәтижесі - құрамдас ағаш ретінде немесе бірінші және екінші көрсетілім әдістерінің кейбір комбинациясы ретінде тәуелділік ағаш ретінде ұсынылған сөйлемнің синтаксистік құрылымы.

«Синтаксис» бар, яғни құрылым, автоматты түрде талдау жасайды:

бағдарламалау тілдерін - аудару кезінде (компиляция немесе интерпретация) бағдарламалау тілдерінің бастапқы кодын талдау.

мысалы, XML, HTML, CSS, ini-файлдары, мамандандырылған конфигурация файлдары және т.б.

SQL сұраулары (DSL-тіл)

математикалық өрнектер

Тұрақты өрнектер (өз кезегінде лексикалық талдауды автоматтандыру үшін пайдаланылуы мүмкін)

формальды грамматикалар

лингвистика - адам тілдері. Мысалы, машиналық аударма және басқа мәтін генераторлары.

Алгоритмдерді талдаудың түрлері

Тікелей талдаушы (ағылшын жоғарыдан төмен талдаушысы) - грамматикалық өнімдер басталу таңбасынан бастап қажетті таңбалар қатарына дейін ашылады.

LL-анализатор

Өсу паластері (ағылшын төменгі-жоғары талдаушысы) - өнім оң жақ бөліктерден қалпына келтіріледі, таңбалармен басталатын және бастау белгісімен аяқталады.

LR-анализаторы

GLR талдағышы

Синтаксический анализ (парсинг) - это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Обычно применяется совместно с лексическим анализом. Синтаксический анализатор (парсер) - это программа или часть программы, выполняющая синтаксический анализ.

Пример разбора выражения в дерево

При парсинге исходный текст преобразуется в структуру данных, обычно - в дерево, которое отражает синтаксическую структуру входной последовательности и хорошо подходит для дальнейшей обработки.

Как правило, результатом синтаксического анализа является синтаксическая структура предложения, представленная либо в виде дерева зависимостей, либо в виде дерева составляющих, либо в виде некоторой комбинации первого и второго способов представления.

Жылжыту-үйіртпе түріндегі типтерді төменнен жоғары қарай жіктеу.

B.7.1. Назначение горизонтальной и вертикальной полос прокрутки.

Размеры рабочей области окна порой значительно превосходят размер рабочей области экрана. Поэтому может случиться, что даже в распахнутом во весь экран окне не будет целиком помещаться текст или изображение, с которым работает пользователь.

B.7.1. Көлденең және тік жылжыту жолақтарын тағайындау.

Терезенің жұмыс аймағының өлшемі кейде экранның жұмыс аймағының өлшемінен айтарлықтай асып кетеді. Сондықтан, тіпті толық экрандағы терезеде, пайдаланушы жұмыс істейтін мәтін немесе сурет толығымен орналастырылмайды.

Ж мыс ке істігіні мазм нын к ру шін, п рмен жолыны интерфейсінде немесе жылжытуда айналдыру рекеті пайдаланылды. Белгілі бір пернелерді басқан кезде, бейнебет жоғары, төмен, оң және сол жаққа жылжиды. Басқа пернелерді басқанда, мәтін бір экранға солға, оңға, жоғары және төмен жылжытады. WIMP интерфейсі пайда болған кезде, сол операцияларды тінтуірмен бастай бастады. Осылайша, айналдыру жолақтары пайда болды. Терезедегі мәтінді жоғары және төмен жылжыту үшін тік сызық пайдаланылды және оңнан солға айналдыру үшін көлденең жылжыту жолағы пайдаланылды.

В.7.2. Жылжыту жолақтарының орны.

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

В.7.3. Айналдырудың бақылау жолдары қандай және қандай қиындықтар болуы мүмкін?

(Пернетақта мәтін жүгіргіні басқарады, өйткені әрқашан, бұл iс-әрекеттер, үндестіріледі емес, және ол әрқашан сарп сызықтар жылжыту емес, дегенмен.) Айналма сызықтар курсор қозғалысы пернелерін бақыланатын, және тышқанның көмегімен болуы мүмкін Тек пернетақтаны пайдаланып Сондықтан, кепілдік Жылжытуға мәтін курсор!

LR(1)-талдауыштары

Негізгі идея - дұрыс емес пакеттерді жасаудан аулақ болу үшін ағылшын тіліндегі элементтерді сақтау.

Жағдайға екінші компонентті қосып көрейік: терминал белгісі. Осылайша, LR (1) -терстеулер келесідей болады:

[A → α⋅β, a], онда бірінші бөлік - шығыс, ал екіншісі - терминал немесе соңғы сызық маркері \ char36. Мұнда жағдайды алдын ала қарау деп аталады, ал LR-дегі (1) нөмірі 1 ұзындығын білдіреді. символы енгізу - Қазір біз тек жағдайда, А → а өндіру сәйкес свертки шырқайды жағдайдың [A → α⋅β, бір] және болып табылады.

Анықтама:

Біз кез келген γ = δα, онда үш бірі оң, егер бар оң қорытынды S⇒ * δAw⇒δαβw, белсенді префикс Г (. Engl жарамды) [A → α⋅β, бір] рұқсат етілген (1) -situatsiyu LR қоңырау немесе a - w бірінші белгісі, w = ε және a = \ char36.

№ 20 БИЛЕТ

1. ДҚ-да іздеу, сұрыптау, деректер базасын индекстеу.

Жаңа жазбаны жасаған кезде, осы жазбаның жадында орналасуы ұсынылған, ол іріктеу уақытына үлкен әсер етеді. Деректерді орналастырудың ең қарапайым стратегиясы - жаңа жазба бірінші тегін сайтқа немесе бұрынғы жазбалардың соңғы нұсқасынан кейін орналастырылғаны. Деректерге қол жеткізудің негізгі әдістері OBD аймағының рет-ретімен өңделуі жүйе беттерді кезекті түрде сканерлеп, бос аумақтарды босатады және оларды сақтаудың физикалық дәйектілігімен жазады. Дерекқор кілті (CBD) арқылы кіру. CDB компьютердің жадындағы жазбаның орнын анықтайды. Оны білу үшін жүйе жадыға бір қол жеткізу үшін қажетті жазбаны шығара алады. Қатынастың бұл түрі топтық қатынастар үшін пайдаланылады және топтық қарым-қатынастың алдыңғы немесе келесі данасына, топтық қарым-қатынастың даналық иесіне немесе бағыныстағы даналар тізіміне өтуге мүмкіндік береді. Бастапқы кілт арқылы кіру Бастапқы кілт түрдегі жазбаларды анықтайды. Егер жүйе бастапқы кілтке қол жеткізуді қамтамасыз етсе, ол (кілт) жазуды есте сақтау кезінде және оның мәнін әдетте еске салу кезінде пайдаланылады. Негізгі кілттерге қол жеткізудің негізгі механизмдері индекстеу және хэширлеу болып табылады.

Негізгі төлсипатқа арналған жазбаларға кіруді жылдамдату үшін арнайы құрылым жасалады - атрибут мәні мен жазбаның орнын арасындағы сәйкестік анықтайтын индекс. Индекс әдетте жеке файлда немесе жекелеген жадта сақталады. Атрибуттардың бос мәндері (нөл) индекстелмейді Индекстеу үдерісі екі кезеңде орындалады: алдымен атрибуттың қажетті мәні және жазбаның тиісті мекен-жайы индекс құрылымында орналасады, содан кейін осы мекен-жайда сыртқы сақтау құрылғысы (VCD) қол жетімді болады. Индекс бүкіл бағдарламаға жүктеледі (немесе дерекқормен жұмыс істеген кезде үздіксіз сақталады). Егер индекстің әрбір мәні бірегей кілт мәніне сәйкес келсе, онда бастапқы кілт. Егер индекс қайталанатын мәндерге мүмкіндік беретін кілтке орнатылса, мұндай индекс қайталама деп аталады. Бірыңғай индекстер мен композициялар бар. Құрамдас индекс бір кестенің екі немесе одан да көп бағандарын қамтиды, индекстерді ұйымдастырудың көптеген жолдары бар: 1. Шұғыл индекстерде, әрбір кілт үшін, нақты жазбаның орнын көрсететін бөлек индексті мақаласы бар. Қатты емес индекстер әрбір жадтың (немесе блокта) индекстеу кілтінің мәндері бойынша сұрыпталған жазбаларды қамтитынын болжамына негізделеді. 2. Кілттерді қысу әдісі сақталған деректердің артық болуын болдырмауға негізделген. Кілттің дәйектілік мәндері әдетте бірдей бастапқы бөліктерге ие, сондықтан индекстің әр мақаласында кілттің толық мәнін емес, тек белгілі алдыңғы мәннен қалпына келтіруге мүмкіндік беретін ақпаратты ғана сақтауға болады. Бір деңгейлі индекс - бір немесе бірнеше жазу өрістерінің мәндерінің сызықтық жиынтығы. Индекстелген жазбалардың саны аз болған кезде қарапайым жағдайларда қолданылады. Неғұрлым күрделі жағдайларда индексте көп жады бар (кейде бірнеше бет) және оған қол жеткізуді азайту мәселесі туындайды. Содан кейін индекс бірнеше иерархиялық деңгейге бөлінеді, бұл сізге қажетті мәнді іздестіруді жеделдетуге мүмкіндік береді.

Ағаш бойынша іздеу әдісі, хештеу.

Хеш-деревом, деревом Меркла (англ. Merkle tree) называют полное двоичное дерево, в листовые вершины которого помещены хеши от блоков данных, а внутренние вершины содержат хеши от сложения значений в дочерних вершинах. Корневой узел дерева содержит хеш от всего набора данных, то есть хеш-дерево является однонаправленной хеш-функцией. Дерево Меркла применяется для эффективного хранения транзакций в блокчейне криптовалют (например, в Bitcoin'е, Ethereum'е). Оно позволяет получить «отпечаток» всех транзакций в блоке, а также эффективно верифицировать транзакции[1

Индекстер

Индекс (латын әріпсандары, тізілім, индекс және индекстік саусақ) - бір жүйенің жай-күйі немесе элементтің орналасқан жерін көрсететін рәміздердің басқа комбинациясы, мысалы, қандай да бір іс-әрекеттің көрсеткіші, өнімділігі, дамуы, бір нәрсенің өзгеруі.

2. Сызықты іздеу.

Сызықтық (тізбектік) іздеу (Линейный (последовательный) поиск; serial search) — іздестіру аймағының элементтері тізбектік түрде бір-бірлеп талданатын іздестіру. Сонымен іздестіру логикалық немесе физикалық тізбекте орындалады.^[1]

Екілік іздеу.

Екілік (Бинарлық) іздеу - Сұрыпталған массив элементтерінің классикалық алгоритмделініп ізделінуі. Яғни, х қатарының у берілген санын немесе бөлімін табу үшін, оны жақындаған сайын екіге бөліп отыру болып табылады.

Жол бойынша іздеу

3. Өрлеуші синтаксистік талдау.

Синтаксистік талдау кестелерін құру және қолдану

Ағаштағы өрнекті талдаудың мысалы

«Синтаксис» бар, яғни құрылым, автоматты түрде талдау жасайды:

мысалы, XML, HTML, CSS, ini-файлдары, мамандандырылған конфигурация файлдары және т.б.

SQL сұраулары (DSL-тіл)

математикалық өрнектер

Тұрақты өрнектер (өз кезегінде лексикалық талдауды автоматтандыру үшін пайдаланылуы мүмкін)

формальды грамматикалар

лингвистика - адам тілдері. Мысалы, машиналық аударма және басқа мәтін генераторлары.

Алгоритмдерді талдаудың түрлері

LL-анализатор

LR-анализаторы

GLR талдағышы

Пример разбора выражения в дерево

№ 21 БИЛЕТ

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

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

⇐ Предыдущая 6 7 8 9 10 11 121314 15 Следующая ⇒

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