Тізімдер. Циклдік тізімдер. Ортогоналды тізімдер 5 страница
k-элементі жиынмен бірге, онда орындалатын барлық операциялардан құралған алгебра k-мәнді логика алгебрасы, ал k-элементіжиындағы n-ші операция n – айнымалылардың k-мәнді логикалық функциясы деп аталады; барлық k-мәнді логикалық функциялар жиыны Рk деп белгіленеді.
n айнымалылы барлық логикалық функциялар кесте түрінде беріледі, сол бөлігінде айнымалылардың барлық 2n мәнді жиынтықтары (яғни n ұзындықты екілік векторлар), ал оң бөлігінде осы жиынтықтағы функциялардың мәндері тізілген. Мысалы, 1 кестеде үш айнымалылы функция берілсін. Функция f = l тең жиынтығы жиі f функциясының бірлік жиынтығы деп, ал сәйкесінше f = 0 жиынтық f нөлдік жиынтығы деп аталады.
1 кестеде жиынтықтар белгілі – екілік сан ретінде қарастырылатын, жиынтықтардың өсу ретімен сәйкес келетін лексика – грамматикалық ретпен орналасқан. Жиынтықтың кез –келегн ретінде n айнымалылы әртүрлі функциялардың | Р2(n) | саны 2nұзындықты әртүрлі екілік векторлар санына тең, яғни 
-не тең.
f(x1, ..., xi-1, xi, xi+1, ..., хn) функциясының xi айнымалысы маңызды емес (немесе жалған) деп аталады, егер қалған айнымалылардың кез –келегн мәнінде f(x1, ..., xi-1, 0, xi+1, ..., хn) = f(x1, ..., xi-1, 1, хi+1, .... хn) болса, яғни егер кез –келегн x1, …, xn жиынтық мәнінде xi –дің мәнінің өзгеруі функцияның мәнін өзгертпесе. Осы жағдайда f(x1, ..., хn) функциясы мәні бойынша n-1 айнымалысынан тәуелді, яғни n-1 айнымалысынан тәуелді, яғни n-1 айнымалының g(x1, ..., xi-1, xi+1, ..., хn) функциясы болып табылады. g функциясы жалған айнымалыны өшірумен f функциясынан алынады, ал f функциясы жалған айнымалыны енгізумен g –дан алынады, сонымен бірге осы функциялар анықтама бойынша тең деп есептеледі. Мысалы, f(x1,x2,x3) = g(x1, x2) екені, кез –келген х1 және x2 мәндері f = g x3 мәнінен тәуелсіз екенін білдіреді.
|
|
|
Жалған айнымалыларды өшіру мағынасы ақиқат, бірақ ол функцияның мәніне әсері жоқ және артық болып табылады. Бірақта кейде жалған айнымалыларды енгізген пайдалы. Функцияларды кез-келген үлкен санды айнымалылар функциясы ретінде жасауға болады. Сондықтан функцияның кез –келген ақырлы жиынтығы ыңғайлы болатындай бір айнымалы жиынынан тәуелді деп есептеледі. Жеке жағдайда | Р2(n) | = теңдігі Р2(n) - n айнымалылы барлық мүмкін болатын функциялардан, соның ішінде жалған айнымалылы функциялардан тұрады деген шартта ғана орындалады.
Бір айнымалылы логикалық функциялар – төртеу; Олар 2-кестеде келтірілген.
|
|
|
| X1 | X2 | y0 | y1 | y2 | y3 | y4 | y5 | y6 | y7 | y8 | y9 | y10 | y11 | y12 | y13 | y14 | y15 |
y0 және y15 функциялары— сәйкесінше 0 және 1 тұрақтылары, яғни екі маңызы жоқ айнымалылар функциялары.
y1(x1, х2) функциясы х1 және х2 конъюнкциясы деп аталады; оның белгіленулері: х1&х2, x1Ùх2, х1×х2 ( конъюнкция белгісі көбейтіндіге ұқсас, ол жиі қалдырылып х1х2деп жазылады). Ол 1-ге тең, тек егер х1 және х2 1-ге тең болса сондықтан оны ЖӘНЕ функциясы деп атайды. Оның тағы бір атауы - "логикалық көбейтінді", оның кестесі 0 мен 1 сандары үшін кәдімгі көбейту кестесімен сәйкес келеді.
y7(х1, х2) функциясы х1 және х2 дизьюнкциясы деп аталады; оның белгіленулері: х1Úх2, х1+х2. Ол 1-ге тең болады, егер х1 немес х2 1-ге тең болса ("немесе" мұнда бөлінбейтін мағынада – екеуінің біреуі деген мағынада түсініледі). Сондықтан оны НЕМЕСЕ функциясы деп атайды.
|
|
|
y6(x1, х2) функциясы – бұл модуль 2 бойынша қосу. Оның белгіленуі: x1Åх2. Ол 1-ге тең болады, оның аргументтерінің мәндері әртүрлі болғанда, және 0-ге тең болады ,олар тең болса. Сондықтан x1Å х2 функциясын кейде тең мәнді емес деп те атайды.
y9(x1, х2) функциясы эквивалентті немес тең мәнді деп аталады. Оның белгіленулері: х1~х2, x1=x2. ОЛ 1-ге тең болады, егер оның аргументтерінің мәні тең болса, және 0-ге тең болады, егер олар әртүрлі болғанда.
y13(x1, х2) функциясы - импликация; белгіленулері: x1 ® х2, x1 É х2 ; "егер x1 , онда х2" деп оқылады; y11(x1, х2) функция - x2 ® х1 импликация.
y8(x1, х2) функциясы- Пирса бағдаршасы (Вебба функциясы); белгіленулері x1 ¯ х2; ол дизъюнкция терістеуі болып табылады.
БИЛЕТ -6
1. Алгоритмдерді талдау мысалдары. Есептеудің негізгі программалық-тиімділік схемалары.
Алгоритмдерді талдаудың негізгі әдістері:
1. Сөздік-формулалық (табиғи тілдерде);
2. Құрылымды немесе блок-схемалар;
3. Арнайы алгоритмдік тілдерді қолдану;
4. Граф-схемалар көмегімен (граф – әр сызық екі нүктені қосатын, нүктелер мен сызықтар жиынтығы). Нүктелер шыңдар деп аталады, сызықтар – қабырғалар;
|
|
|
5. Петри торының көмегімен.
Бағдарламаны жасау алдында көбінесе сөздік-формулалық және блок-схемалық әдістер қолданылады. Кейде ассемблер сияқты төменгі деңгейдегі тілдерде бағдарламаны жасау алдында, бағдарлама алгоритмін кейбір жоғарғы деңгейдегі бағдарламалау тілінің конструкцияларын қолдана отырып жазады. Күрделі бағдарламалық жүйелер алгоритмдерінің бағдарламалық сипаттамаларын қолдану ыңғайлы. Мысалы, ОЖ жұмыс істеу принциптерін сипаттау үшін Алголға ұқсас жоғарғы деңгейдегі бағдарламалау тілі қолданылды
Сөздік-формулалық әдісте алгоритм әрекеттер тізбегін анықтайтын, құрамында формулалары бар мәтіндік түрде жазылады. Мысалы, келесі өрнектің мәнін анықтау қажет болсын: у=2а-(х+6).Сөздік-формулалық әдістпен бұл есептің алгоритмі келесі түрде жазылуы мүмкін:
1. а және х мәндерін енгізіңіз.
2. х және 6-ны қосу.
3. а на 2-ге көбейту.
4. 2а –дан (х+6) қосындысын азайту.
5. Өрнектің есептелген нәтижесі ретінде у-ті шығару.
Блок-схемада бағдарламадағы барлық тармақтар, циклдар және ішкі бағдарламалар болуы қажет.
2. Иерархиялық деректер моделі.
ДҚБЖ-да иерархиялық типтегі деректерді ұйымдастыру келесі терминдер арқылы анықталады: элемент, агрегат, жазба (топ), топтық қатынастар деректер базасы.
Атрибут (деректер элементі) – деректер структурасының ең кіші бірлігі. Деректер базасын сипаттау кезінде, әдетте оның әрбір элементіне бірегей ат беріледі. Өңдеу кезінде осы ат бойынша назар аударамыз. Деректер элементін де кейде өріс деп атайды.
Жазба – атрибуттардың аталған жиынтығы. Жазбаларды пайдалану базаға бір рет кіру арқылы бірқатар логикалық байланысы бар деректер жиынтығын алуға мүмкіндік береді. Нақ осы жазбаларды өзгертеміз, қосамыз және өшіреміз. Жазба типі оның құрамындағы атрибуттар арқылы анықталады. Жазба данасы – ол нақты элементтер мәні бар нақты жазбалар.
Топтық қатынас – екі типті жазбалар арасындағы иерархиялық қатынас. Ата-аналық жазба (топтық қатынас иесі) бастапқы жазба деп, ал ұрпақтық жазбалар (топтық қатынас мүшелері) – бағынушы деп аталады. Деректердің иерархиялық базасы тек ғана агаш типті структураны сақтайды.
Иерархиялық модельде анықталған деректерге қолданылатын амалдар:
• Деректер базасына жаңа жазба ҚОСУ. Бастапқы жазба үшін кілт мәнін анықтау міндетті.
• Жазбадан алдын-ала алынған деректер мәнін ӨЗГЕРТУ. Кілттік деректер өзгертуге түспеу керек.
• Бірқатар жазбалар мен оның барлық бағыныңқы жазбаларын ӨШІРУ.
• ШЫҒАРЫП АЛУ:
o кілт мәңі бойынша түпкі жазбаны шығарып алу, сонымен қоса, түпкі жазбаны тізбектей көру мүмкіндігі болады
o келесі жазбаны шығарып алу (келесі жазба сол жақты айналып өту реті арқылы шы,арылып алынады)
3. Детерминантты ақырлы автоматтар. Мур диаграммалары (ауысу жүйелері).
Ақырлы автоматтар танығыштардың ішіндегі ең көп тарағаны болып есептелінеді. Кез келген ақырлы автоматтың құрамындаақырлы кіріс таспасы, ішкіжад, сыртқы жад, оң жақты бастиек, басқарушы құрылғы болады.Ақырлы автоматтың құрылымы төмендегі суретте көрсетілген.
| ⊢,⊣ |
| ti-1 |
| Таспа |
| Солжақ шетінің белгісі |
| Оң жақ шетінің белгісі |
| Кіріс символы |
| Бастиек |
| Басқарушы құрылғы |
| Сурет ІІ.2.1.1.Ақырлы автоматтың құрылымы |
| ti+1 |
| … |
| Сыртқы жад |
| ⊣,⊣ |
| … |
| t1 |
| t2 |
| ti |
| tn |
| tn-1 |
| Сыртқы жад |
Ақырлы автомат (АА) бейдетерминді немесе детерминді болуы мүмкін, бірақ оның бастиегі бір жақты және тек оң жаққа жылжи алады. Детерминді ақырлы автомат (ДАА) БАА-ың дербес жағдайы.
II.2.1.2-анықтама. Ақырлы автомат M=<Q, Т, I,F,⊢,⊣,Δ>детерминді деп аталады, егер:
(1) алғашқы күйлер жиыны I бір ғана элемент қамтиды;
(2) әрбір ауысу <q, τ, p>∈Δ үшін |τ| = 1 орындалады;
(3) кез келген күй q∈Qжәне кез келген кіріс символы t∈T үшін <q, t, p>∈Δ қасиетіне ие болатын бірден көп күй p∈Qбар;
(4) қалған символдар БАА-ндағыдай болады.
II.2.1.2-ескерту:
1. Кейде мәні ‘ақиқат’ немесе ‘жалған’ болатын Δ ауысулар қатынасының жиынының орнына мәні Q жиынында жататын ауысулар функциясын пайдаланады, мұнда δ: Q´T*→J(Q) - БАА үшін және δ: Q´T*→Q - ДАА үшін. δ ауысулар функциясынан Δ ауысулар қатынасына былай көшуге болады:
Δ = {<q, τ, d(q, τ)> | qÎQ, τÎT*}.
2. Ары қарай, біз айырықша ескертусіз, ауысулар қатынасын да, ауысулар функциясын да пайдаланамыз. Сонымен, кез келген qÎQ, pÎQ және τÎT* үшін былай да жазуға болады:
1) ауысулар қатынасы: <q, τ, {p}>-БАА үшін, <q, τ, p>-ДАА үшін;
2) ауысулар функциясы: d(q,τ) = {р} - БАА үшін, d(q,τ) = p-ДАА үшін.
3. Егер біз ауысулар қатынасының орнына ауысулар функциясын пайдаланғымыз келсе, АА-ның формалды анықтамасында Δ символын δ символына алмастырып, ал қалған символдарды олардың мәндерін өзгертпей қалдыру керек, яғни M = <Q, T, I, F, ⊢,⊣, δ> деп аламыз.
БИЛЕТ -7
- Фундаменталды деректер типі.
C++
| Спецификатор типа | Эквивалентный тип | Ширина в битах согласно модели данных | ||||
| Стандарт C++ | LP32 | ILP32 | LLP64 | LP64 | ||
| Short | short int | не меньше чем | 16 | 16 | 16 | 16 |
| short int | ||||||
| signed short | ||||||
| signed short int | ||||||
| unsigned short | unsigned short int | |||||
| unsigned short int | ||||||
| Int | Int | не меньше чем | 16 | 32 | 32 | 32 |
| Signed | ||||||
| signed int | ||||||
| Unsigned | unsigned int | |||||
| unsigned int | ||||||
| Long | long int | не меньше чем | 32 | 32 | 32 | 64 |
| long int | ||||||
| signed long | ||||||
| signed long int | ||||||
| unsigned long | unsigned long int | |||||
| unsigned long int | ||||||
| long long | long long int | не меньше чем | 64 | 64 | 64 | 64 |
| long long int | ||||||
| signed long long | ||||||
| signed long long int | ||||||
| unsigned long long | unsigned long long int | |||||
| unsigned long long int | ||||||
Язык С++
Дата добавления: 2018-08-06; просмотров: 275; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!