А. Ж. Асамбаев информатиканың теориялық негіздері. Практикум
жүктеу/скачать 1,43 Mb. Pdf көрінісі
|
М 3.6. ¬(¬A B) өрнекке қандай логикалық өрнек сәйкес болады? Шешім. Өрнекті түрлендіру үшін (17), (21) заңдарды пайдаланамыз: (17) (21)
¬(¬A B) = ¬(¬A) ¬B = A ¬B.
Логикалық өрнектің есептеуі көбінесе ақиқаттық кестелер түрінде орындалады — осындай кестелерде әр түрлі айнымалылар жиынтығы болғанда алынатын логикалық өрнектің мәндері көрсетіледі. Кестені құрастыру үшін қажет: 1) кестедегі жолдар санын анықтау (2 n деп есептеледі, мұндағы n – айнымалылар саны); 2) бағандар санын анықтау (айнымалылар саны плюс логикалық операциялар саны ретінде есептеледі); 3) логикалық операциялардың орындау ретін орнату; 4) бағандар атын және бастапқы айнымалылардың мүмкін болатын мәндер жиынтығын белгілеп кестені құру; 5) бағандар бойынша ақиқат кестені толтыру.
F = (A B) (
A
2 (2 айнымалы) + 1 (бағандар аты) = 5. 26
2) Бағандар саны = 2 логикалық айнымалылар (А, В) + 5 логикалық операциялар ( ,
, , , ) = 7. 3) Операцияларды орындау ретін қоямыз: 1 5 2 4 3 (A B) ( A
4) Ақиқаттық кестені құрамыз (3.3-кесте).
3.3-кесте A B A
0 0
1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 0 0 0 0
3.3 Логикалық сұлбаны құрастыру Конъюнктор, дизъюнктор және инвертор элементтер (3.4-кесте) арқылы орындалатын сәйкес үш логикалық (конъюнкция, дизъюнкция және инверсия (терістеу)) операциялардан кез келген логикалық өрнектерді жүзеге асыруға болады. 3.4-кесте
1 1
1 1 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 0 0 0 0 0 Конъюнктор Дизъюнктор Инвертор
Логикалық сұлбаны құрастыру ережесі: 1) логикалық айнымалылар санын анықтау; 2) логикалық операциялар санын және олардың ретін анықтау; 3) әрбір логикалық операция үшін оған сәйкес вентильді бейнелеу; 4) логикалық операцияларды орындау реті бойынша вентильдерді қосу.
.
А
В А +
А А
В А
27
Шешім. 1) Айнымалылар екеу: X және Y . 2) Логикалық операциялар төртеу: конъюнкция, терістеу және екі дизъюнкция. Реті: 1 4 3
3) Логикалық операциялардың ретіне сәйкес сұлбаны сол жақтан оңға қарай саламыз:
4) Өрнек мәнін есептейміз: .
28
ӨЗІНДІК ЖҰМЫС ТАПСЫРМАЛАРЫ
Логикалық өрнекті оңайлатыңыз. 3.1. .
3.2. .
3.3. .
3.4. .
3.5. .
3.6. .
3.7. .
3.8. .
3.9. .
3.10. .
Логикалық формула үшін ақиқаттық кестені құрастырыңыз. 3.11. X
3.12. X (X Y). 3.13. (X Y) ( X
3.14. X (Y Z). 3.15. X (Y Z).
Y) Z. 3.17. ((X Y) X)
Y) X) Y. 3.19. ((X Y) X) Y. 3.20. (X Y) (Y Z). 29
Логикалық сұлба бойынша логикалық өрнекті құрастырыңыз. 3.21.
3.22.
3.23.
3.24.
Логикалық өрнекке сәйкес логикалық сұлбаны салыңыз және логикалық өрнектің мәнін табыңыз. 3.25. , егер А = 1, В = 1, С = 1. 3.26. , егер А = 0, В = 1, С = 1. 3.27. , егер А = 1, В = 0, С = 1. 3.28. , егер А = 0, В = 1, С = 0. 3.29. , егер А = 0, В = 0, С = 1. 3.30. , егер А = 0, В = 0.
30
3.4 Бақылау тест тапсырмалары Т 3.1. Себетте 32 шумақ жүн жатыр. Олардың ішінде – 4 қызыл. Қызыл шумақ жүн алынды деген хабарда қанша ақпарат бар: а) 1 бит; б) 2 бит; в) 3 бит; г) 4 бит?
15 қызыл шар. Себеттен жасыл шар алғаны деген хабарда 2 бит ақпарат бар. Себетте барлығы қанша шар жатыр: а) 18; б) 20; в) 22; г) 24?
қар
= 10 қара, К ақ
= 5 ақ, К сар = 4 сары және К қыз = 1 қызыл шар. Жәшіктен кездейсоқ жолмен қара шар Н қар
, ақ шар Н ақ , сары шар Н сар , қызыл шар Н қыз алғаны хабарларда қанша ақпарат саны бар? а) Н қар = 1 бит, Н ақ = 2 бит, Н сар = 2,236 бит, Н қыз = 4,47 бит. б) Н қар
= 2 бит, Н ақ = 4 бит, Н сар = 2,6 бит, Н қыз = 4,47 бит. в) Н қар
= 1 бит, Н ақ = 2 бит, Н сар = 3 бит, Н қыз = 4 бит. г) Н қар
= 3 бит, Н ақ = 2 бит, Н сар = 2,236 бит, Н қыз = 4,47 бит. Т 3.4. Себетте барлығы 128 қызыл, көк және ақ шар жатыр, қызыл шарлардың саны көк шарлардан үш есе артық. Ақ шар алынған хабарда 3 бит ақпарат бар. Себетте қанша көк шар бар: а) 24; б) 28; в) 32; г) 36?
шортан балық саны 6250-ден. Қандай болмасын балықты ұстап алғанда біз қанша ақпарат аламыз: а) 1,5 бит; б) 1,75 бит; в) 2 бита; г) 2,25 бит?
бар. Бұл хабардың ақпарат көлемі қандай: а) 100 бит; б) 110 бит; в) 120 бит; г) 130 бит?
хабарды жазу үшін пайдаланған алфавитте қанша символ бар: а) 8; б) 16; в) 24; г) 32?
Т 3.8. Кейбір тілдің сөздік қорында 256 сөз бар, олардың әрбіреуі дәл 4 әріптен тұрады. Тіл алфавитінде қанша әріп бар: а) 8; б) 4; в) 64; г) 1024; д) 256?
q жеміс ағашы бар, олардың ішінде 33 таңқурай бұтасы, 22 қызыл қарақат бұтасы, 16 қара қарақат бұтасы және 17 қарлыған бұтасы. Ағаштар қандай санау жүйесінде есептелген: а) 7; б) 9; в) 11; г) 13?
7 ; б) 152 10 ; в) 152 12 ; г) 152
16 ?
T 3.11. Екілік сандарды сегіздік және он алтылық санау жүйесіне ауыстырыңыз: 31
а) 110000110101,1010101; б) 11100001011001,1000010101.
жүйесіне ауыстырыңыз: а) 18,34 10
А 2 , б) 71,5 10
A 8 ; в) 124,26 10
А 16 . Т 3.13. Он алтылық сандарды екілік санау жүйесіне ауыстырыңыз: а) 1АС7; б) FACC.
ауыстырыңыз: а) 774; б) 665.
саны қажет болады: а) 5 бит; б) 6 бит; в) 7 бит; г) 8 бит?
«9 а», «10 а» жазылады, егер оларды азаю ретімен реттейтін болсақ? а) байт, excel, 9 а, 8 в, 10 г, 10 а; б) байт, excel, 8 в, 9 а, 10 а, 10 г; в) 10а, 10г, 9 а, 8 в, байт, excel; г) байт, excel, 10 г, 10 а, 9 а, 8 в; д) excel, байт, 10 г, 10 а, 9 а, 8 в.
Unicode (кодтау кестесінде 65536 символ бар) кодировкасына өзгерткен кезде мәтін парағының ақпараттық көлемі неше есе артады: а) 2; б) 4; в) 6; г) 8?
сақталыну мүмкін. Егер 512-түсті палитраны пайдалансақ, осы видеожад көлемінде қандай мөлшерді бейнені сақтауға болады: а) 151245; б) 182434; в) 253624; г) 273066?
65536-ға дейін көбейді. Орын алатын жад көлемі неше есе артты: а) 3,5; б) 2,5; в) 1,5; г) 0,5?
жасау үшін; в) диаграммаларды құру үшін; б) графиктерді құру үшін; г) суреттерді жасап редакциялау үшін.
3) MPI; 4) JPG; 5) BMP.
Дұрыс жауаптардың нұсқалары: а) 2, 3, 5; б) 1, 4, 5; в) 4, 5; г) 1, 2. 32
Т3.22. Информатикадағы энтропия – бұл ненің қасиеті: а) мәліметтердің; б) білімнің; в) ақпараттың; г) іздеу жағдайлардың.
в) графикалық файлдардың форматы; г) монитор типі.
10
= 23 x , онда санау жүйесінің негізі х тең: а) 4; б) 8; в) 10; г) 16,82.
Жауаптар және шешімдер
Т 3.2. б. Т 3.3. а. Шешім. 1) Р қар
= K қар
/N = 10/20 = 1/2 — қара шарды алу ықтималдығы; 2) Р ақ = K ақ /N = 5/20 = 1/4 — ақ шарды алу ықтималдығы; 3) Р сар
= K сар
/N = 4/20 = 1/5 — сары шарды алу ықтималдығы; 4) Р қыз = K қыз /N = 1/20 — қызыл шарды алу ықтималдығы; 5) Н қар
= log 2 (l/(l/2)) = 1 бит; 6) Н ақ = log 2 (l/(l /4)) = 2 бит; 7) Н сар
= log 2 (l/(l/5)) = 2,236 бит; 8) Н қыз
= log 2 (l/(l/20)) = 4,47213 бит. Т 3.4. б. Т 3.5. б. Шешім. 1) Көлдегі жалпы балықтар саны: К = 12500 + 25000 + 2•6250 = 50000;
2) әрбір балықтың қармаққа түсу ықтималдығы: Р а = 12500/50000 = 0,25; Р т = 25000/50000 = 0,5; Р м = 6250/50000 = 0,125; Р ш = 6250/50000 = 0,125;
3) ақпарат көлемі: Н = -(0,25•log 2 0,25 + 0,5•log 2 0,5 + 0,125•log 2 0,125 + 0,125•log 2 0,125) = 1,75 бит. T 3.6. в. Т 3.7. б. Т 3.8. б. Т 3.9. б. 33
Т 3.10. г. T 3.11. а) 6065,524 8 , С35,АА 16 ; б) 34131,4124 8 , 3859,854 16 .
Т 3.12. а) 10010,0101 2 ; б) 107,4 8 ; в) 7С,4 16 .
2 ; б) 1111101011001100 2 .
ауыстырыңыз, сосын он алтылық санау жүйесіне. Т 3.15. б. Т 3.16. а. Түсініктеме: осы есепті шешкен кезде тізбектік (жүйелі) кодтау принципін пайдалану керек. Т 3.17. а. Т 3.18. г. Шешім. 1) N = 2 i , 256 = 2 i , i = 8 бит — бірінші бейненің түс тереңдігі; 2) 640•480•8 = 2 457 600 бит — видеожад көлемі; 3) 512 = 2 i , i = 9 бит — екінші бейненің түс тереңдігі; 4) 2 457 600 : 9 = 273 066 нүкте — екінші бейненің мөлшері. Т 3.19. г. Шешім. 1) N 1 = 2 i , 256 = 2 i , i 1 = 8;
2) N 2 = 2 i , 65536 = 2 i , i 2 = 16;
3) i 1 /i 2 = 8/16 = 0,5 есе. Т 3.20. г. Т 3.21. б. Т 3.22. в. Т 3.23. б. Т 3.24. а.
34
4 АҚПАРАТТЫҚ ҮДЕРІСТЕРДІ АВТОМАТТАНДЫРУ. АБСТРАКТІЛІ АВТОМАТТАР Абстрактілі (яғни тек адам қиялында ғана болатын) Пост және Тьюринг машиналары бағдарламалардың қасиеттері туралы әр түрлі тұжырымдарды дәлелдеу үшін ойлап шығарылды. Бұл бір-біріне тәуелсіз екі есептеу машиналарының моделін (практикада бір уақытта) 1937 жылы Алан Тьюринг ұсынды. Бұл машиналар толық детерминделген әмбебап орындаушылар болып табылады. Олар алғашқы деректерді енгізіп, бағдарлама орындалғаннан кейін нәтижені оқуға мүмкіндік береді. Тьюринг машинасына қарағанда Пост машинасы қарапайым болғанымен кең таралмаған.
Бұл елестегі машина - яғни ― «қағаз бетіндегі» машина немесе машинаның математикалық моделі. Тьюринг машинасы - таза абстракция және ешқашан жасалмаған. Оның пайдасы түрлі есептер шешімінің алгоритмі бар немесе жоқ екендігін дәлелдеуге болады. Машина белгілі бір алгоритмді орындайтын болғандықтан, бұл машинаға алгоритмнің қасиеттерінен талаптар қойылады. Біріншіден, машина толықтай детерминенделген (есептеулер нақты және жалпы түсінікті) болуы қажет және тапсырылған ережелер жүйесі негізінде әрекет етуі керек. Екіншіден, - бастапқы мәліметтерді енгізуге мүмкіндік беруі қажет. Үшіншіден, берілген машинаның жұмыс жасау ережелерінің жүйесі және шешілетін есептердің класы машина жұмысы нәтижесін оқи алатындай болып келістірілуі керек.
Тьюринг тезисі кез келген алгоритмді Тьюринг машинасына салып шешуге болатынға негізделген. Тьюринг машинасының жұмыс істеу принципі, сипаттамасы. Бір ленталы Тьюринг машинасын кибернетикалық құрылғы ретінде қарастырады және ол келесі элементтерден тұрады: – ұяшықтарға бөлінген шексіз лента; – лента ұяшықтарында болатын символдарды оқи алатын басқарушы головка; – Тьюринг машинасының жағдайын көрсететін ішкі алфавит символы бар жадының ұяшығы. – лента бойымен головканың қозғалысын қамтамасыз ететін басқарудың механикалық құрылғысы – тек оқуға болатын Тьюринг машинасының бұйрықтарынан тұратын функционалды схема - жады аймағы. Әдетте, Тьюринг машинасы схемалық түрде мынадай түрде көрсетіледі:
35
Лентаны магниттік жол немесе баспаның қағаз лентасы деп қарастырайық, ол бірнеше ұяшыққа бөлінген. Жұмыс барысында машина бар ұяшықтарға жаңа ұяшықтарды қоса алады, сондықтан лента екі жағынан да шексіз деп айтуға болады. Лентаның әрбір ұяшығы көп жағдайдың бірінде болуы мүмкін. Бұл жағдайларды біз а 0 , а 1 ,...,а m символдарымен немесе басқа символдармен белгілейміз. Осы символдар лента ұяшықтарында жазылған. Мұндай символдардың жиынтығы машинаның сыртқы алфавиті деп, ал лентаның өзі машинаның сыртқы жадысы деп аталады. Егер ұяшық бос болса, ол жерде шарты символы орналасқан деп есептейміз. Машинаның жұмысы кезінде лентаның ұяшықтары өздерінің жағдайын өзгертуі де, өзгертпеуі де мүмкін. Жаңа қосылатын барлық ұяшықтар бос болады. Сонымен, егер қандай да бір уақытта лентаның r ұяшығы болса және машинаның сыртқы алфавиті мынадай символдардан тұрса а 0 , а 1 ,...,а m , онда лентаның жағдайы былай жазылады: а i0 , а i1 ,...,а im .
а i1
- солдан бастап орналасқан бірінші ұяшықтың жағдайы, а i2
- екіншісінің жағдайы, т.с.с. Басқару головкасы. Бұл лентаның бетімен қозғалатын және белгілі бір уақытта лентаның белгілі бір ұяшығында тұрады. Кейде керісінше басқару головкасы қозғалмайды, оған сәйкес лента қозғалады деп есептеледі. Ондай кезде головкаға лентаның ұяшығының біреуі әлде келесісі кіреді деп есептеледі. Егер лентаның ұяшығы головкада болса, машина бұл ұяшықты оқып немесе қабылдап жатыр деп есептеледі. Машинаның ішкі жадысы - әрбір қараған уақытта белгілі бір жағдайда болатын құрылғы. Ішкі жадының жағдайының саны машинамен есептеліп отырады. Ішкі жадының жағдайын мынадай символдармен көрсетеміз S 0 , S 1 ,…,
S n , олар машинаның сыртқы алфавитіне кірмейді. Ішкі жадының жағдайының символдарының жиынтығы машинаның ішкі алфавиті деп аталады. Ішкі жадының жағдайын көбінесе машинаның ішкі жағдайлары деп атайды. Бұл жағдайлардың біреуі бастапқы деп аталады, бұл жағдайдан машина өз жұмысын бастайды, ол S 0 жағдайы болсын. Тағы да бір арнайы жағдай - аяқтаушы соңғы жағдай. Соңғы жағдайды көрсететін символ стоп-символ деп аталады. Стоп-символ өрнектеледі. Егер қандай да бір уақытта машинаның ішкі жадысы келсе, ол жұмысын тоқтатқан болып есептеледі. Машинаның S і
қандай да бір ішкі жағдайында ешқандай өзгеріс болмауы мүмкін, олай болса, машина шексіз жасайды деп есептеледі. Машина ерекше механизммен жабдықталған деп есептеледі. Ол қабылданатын ұяшық пен ішкі жады жағдайына қарай ішкі жады жағдайын, ұяшық орнын өзгерте алады деп есептеледі. Машинаның (Тьюринг) ағымдағы жағдайы немесе оның конфигурациясы деп ағымдағы ұяшық а j және ішкі жады S 1 жағдайларының жиынтығын айтамыз. Тьюринг машинасының командасы, яғни машина жұмысы бір жағдайдан белгілі бір уақытта механикалық құрылғының бір такті жұмысынан соң жаңа 36
бір жағдайға өтуіне негізделген, содан соң тағы бір такті жұмысынан жаңа бір жағдайға өтуі т.с.с. Егер машина S і ішкі жағдайында а і символды лентаның ұяшығын қабылдап, ішкі жады жағдайын келесіге S b аударып сонымен бірге қабылданған ұяшықтың мазмұнын а r символына аударып, ал басқару головкасы (H) орнында тұрып, бір ұяшыққа оңға қарай (R), солға қарай (L) қозғалса, онда машина мынадай команда орындап жатыр деп айтады:
S
а і
а s S
H S і а і
а s S
R S і а і
а s S
L
Машина орындай алатын барлық командалардың жиынтығы бағдарлама деп аталады. Машина жұмысы шарт бойынша толықтай оның ішкі жадысының S және қабылданатын ұяшықтың a j жағдайымен анықталатын болғандықтан, барлық S і a j (і=1,…, n; j=0, 1,…, m) үшін машина бағдарламасы тек қана бір a і
j
сөзінен басталатын командадан тұруы қажет. Сонымен {a 0 , a 1 ,…, a n } символды және {S 0 , S 1 ,…, S
m } жағдайдағы машина бағдарламасы максимум (n+1)(m+1) командаларынан тұрады. Бағдарламада мынадай жолдардың өңделуі мүмкін емес, бірақ формалды түрде олардың болуы қате болып саналмайды. Тьюринг машинасының қарапайым түрінде кейбір алгоритмдерді құру қиындық туғызады. Мысалы, аралық мәліметтерді бір жерде сақтау немесе бірнеше элемент топтарының символын салыстыру және т.б. Кей жағдайда қосымша лентаның болуы немесе сөздерді бірнеше лентаға орналастыру дұрыс шешім қабылдауға көмектеседі. Көпленталы машина әрбір лентаға арналған алфавитке ие. Машинадағы ленталар бір-бірінен тәуелсіз қозғалады. Алайда машина лентасының жағдайы бірдей, ол жағдай басқару механизмі болып табылады. Бір ленталы машинаны қарастырғанда лента қозғалмайды, ал головка берілген бағытта қозғалады деп есептелді. Бірақ көп ленталы машинаны қарастырғанда бұл жағдай ыңғайлы емес. Себебі ленталар бір-бірінен тәуелсіз, ал бір басқару механизмінде түрлі бағыттағы қозғалысты көрсету қиын. Сонымен басқару механизмі қозғалмайды, ал ленталар оңға, солға бір-бірінен тәуелсіз қозғалады деп есептеледі. Көп ленталы машинаның бағдарламасы - шешімге қарай келесі жазба тәртібі қолданылады: S і {a,b,c}→{a',b',c'}{R,L,H}S j
Тьюринг белгілі бір U есептеу машинасының құрылысының мүмкіндігін көрсетті, U машинасы универсалды деп аталу себебі онда түрлі есептеулерді жасауға болады. Тьюринг машинасының ерекшелігі сәйкес келетін кодтау жолымен кез келген есептеуді берілген Тьюринг машинасында орындай алуында. Кодтау жеңіл болуы керек.
Тьюрингтің универсалды машинасы (ТУМ) лентасында берілген Тьюринг машинасының (ТМ) код номері жазылады. ТУМ осы код номерін оқып, оның лентасында бағдарламасы жазылған машинаның барлық жұмысын атқаруы қажет. Осыған сәйкес мұндай машиналарға белгілі бір әдіспен жазылған кіріспе
37
сөз қажет. Мүмкін белгілердің саны көп болғандықтан, барлық символдар басқа белгілердің ретімен кодталады. Егер А машинасы m символға ие A і және n ішкі жағдайға S j ие болса, кодты былай көрсету керек: A і = 1…1 (A 1 =1, A
2 =11, A
3 =111 және т.б.) S j
1 =2, S
2 =22, S
3 =222 және т.б.) R = 3 L = 33
H = 333 Мұндай жағдайда машина жұмысының бағдарламасын белгілі бір санмен жазуға болады. Жазбаның екі нұсқасы бар: 1. Команданың бөлу белгісі болмайды. Мұндай жағдайда командаларды мынадай форматта жазу қажет A old
S old
A new
R S new
сонда бірінен соң бірі орналасқан екі командалар элементар анализатормен бөлінеді. 2. Команда бөлгіші бар. Мысалы Х саны оны 4 саны кодтаймыз.
жүктеу/скачать 1,43 Mb. Достарыңызбен бөлісу:
|