А. Ж. Асамбаев информатиканың теориялық негіздері. Практикум
жүктеу/скачать 1,43 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- А.Ж. Асамбаев
- Пікір жазғандар
- 1 АҚПАРАТ ЖӘНЕ ОНЫҢ ҚАСИЕТТЕРІ
- 2 САНДЫҚ АҚПАРАТТЫ БЕЙНЕЛЕУ
- 3 ЛОГИКА АЛГЕБРАСЫНЫҢ НЕГІЗГІ ҰҒЫМДАРЫ
- 4 АҚПАРАТТЫҚ ҮДЕРІСТЕРДІ АВТОМАТТАНДЫРУ АБСТРАКТІЛІ АВТОМАТТАР
- 5 АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ НЕГІЗГІ ҰҒЫМДАРЫ
- 1.2 Теңықтималды емес мүмкіндіктері бар есептерді шешу М 1.6.
- 1.3 Алфавит көлемін өлшеу туралы есептерді шешу М 1.9.
- ӨЗІНДІК ЖҰМЫС ТАПСЫРМАЛАРЫ
| ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ ПАВЛОДАР МЕМЛЕКЕТТІК ПЕДАГОГИКАЛЫҚ ИНСТИТУТЫ
А.Ж. Асамбаев
ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ. ПРАКТИКУМ
Павлодар 2014
2 А 87 УДК 519.862.5 (075) ББК 32.973 А 87
Баспаға Павлодар мемлекеттік педагогикалық институтының Ғылыми кеңесі шешімімен ұсынылған
Пікір жазғандар: техника ғылымының кандидаты, профессор – А.Д. Тастенов физика-математика ғылымының кандидаты, профессор – А.Т. Тоқметов
А.Ж. Асамбаев Информатиканың теориялық негіздері. Практикум. Оқу құралы. – Павлодар, 2014. – 70 б.
ISBN 978-601-267-295-4
тәжірибелік курсы ұсынылған. Оқу құралы 5В011100 Информатика мамандығына арналған және Қазақстан Республикасының мемлекеттік білім беру стандартының негізінде құрастырылды. Оқу құралы «Информатика» мамандығының күндізгі және сыртқы оқу бөлімінің студенттері үшін арналған.
ISBN 978-601-267-295-4
© А.Ж. Асамбаев, 2014. © Павлодар мемлекеттік педагогикалық институты, 2014. 3
КІРІСПЕ ......................................................................................................................................... 4
1.1 Теңықтималды мүмкіндіктері бар есептерді шешу ............................................................. 5 1.2 Теңықтималды емес мүмкіндіктері бар есептерді шешу .................................................... 6
1.3 Алфавит көлемін өлшеу туралы есептерді шешу ................................................................ 6 ӨЗІНДІК ЖҰМЫС ТАПСЫРМАЛАРЫ .................................................................................... 8
2.1 Санау жүйелері ........................................................................................................................ 9
2.2 Бүтін ондық сандарды басқа санау жүйелеріне ауыстыру ............................................... 11 2.3 Бөлшек ондық сандарды басқа санау жүйелеріне ауыстыру ............................................ 12
2.4 Екілік сандарды 2 n негізі бар санау жүйелеріне ауыстыру ............................................... 13
2.5 Сандарды қосу ....................................................................................................................... 14 ӨЗІНДІК ЖҰМЫС ТАПСЫРМАЛАРЫ .................................................................................. 16
2.6 Символдық ақпаратты ұсыну ............................................................................................... 16 ӨЗІНДІК ЖҰМЫС ТАПСЫРМАЛАРЫ .................................................................................. 19
2.7 Графикалық ақпаратты ұсыну ............................................................................................. 20 ӨЗІНДІК ЖҰМЫС ТАПСЫРМАЛАРЫ .................................................................................. 21
3.1 Логикалық өрнектерді оңайлату .......................................................................................... 23
3.2 Ақиқаттық кестелерді құрастыру ........................................................................................ 25 3.3 Логикалық сұлбаны құрастыру ........................................................................................... 26
ӨЗІНДІК ЖҰМЫС ТАПСЫРМАЛАРЫ .................................................................................. 28 3.4 Бақылау тест тапсырмалары ................................................................................................ 30
АБСТРАКТІЛІ АВТОМАТТАР ............................................................................................. 34
4.1 Тьюринг машинасы ............................................................................................................... 34 4.2 Пост машинасы ..................................................................................................................... 37
4.3 Тьюринг және Пост машинасы көмегімен «алгоритм» ұғымын анықтау ....................... 38 4.4 Марковтың нормальды алгоритмдері ................................................................................. 39
4.5 Бақылау тест тапсырмалары ................................................................................................ 41
5.1 Алгоритмнің қасиеттері........................................................................................................ 45 5.2 Алгоритмді жазу тәсілдері ................................................................................................... 45
5.3 Блок – схемалар ..................................................................................................................... 47 5.4 Алгоритм құрылыстары ....................................................................................................... 51
ӨЗІНДІК ЖҰМЫС ТАПСЫРМАЛАРЫ .................................................................................. 57
6.1 Модельдерді әр түрлі белгілеріне қатысты топтастыру ................................................... 60 6.2 Компьютерлік модельдеудің кезеңдері............................................................................... 62
ПАЙДАЛАНЫЛҒАН ӘДЕБИЕТТЕР ....................................................................................... 69
4
Теориялық информатика – математикалық ғылым. Ол математиканың бірнеше бөлімдеріне негізделген: автоматтар мен алгоритмдер теориясы, математикалық логика, формалды тілдердің және грамматикалардың теориясы, ақпарат теориясы және т.б. Теориялық информатика ақпаратты сақтау және өндеу кезінде пайда болатын негізгі сұрақтарға дәл талдау әдістері арқылы жауап беруге тырысады, мысалы, кейбір ақпараттық жүйеде жинақталған ақпарат саны неге тең, сақтау немесе іздеу үшін ақпаратты тиімді ұйымдастыру, сонымен қатар ақпаратты түрлендіру алгоритмдердің бар болу және қасиеттер туралы. Ай сайын деректерді сақтауға арналған ең үлкен көлемі бар жаңа құрылғылар пайда болуда, бұл ақпарат теориясы мен кодтау теориясының дамуымен түсіндіріледі. Қолданбалы есептерді шешу үшін жақсы программалар бар, бірақ сауатты түрде қолданбалы есепті қою үшін, оны компьютерге түсінікті түрге келтіру үшін ақпараттық және математикалық модельдеу негіздерін және т.б. білу керек. Информатиканың тек осы бөлімдерін меңгере отырып, өзіңізді осы ғылымның маманы деп есептей аласыз. Информатиканың теориялық негіздері курсы
информатиканың фундаментальді ұғымдары: ақпараттар теориясының негізі, сандық автоматтар теориясы, алгоритмдер теориясы, алгоритмдер тиімділігінің анализі, ақпараттық модельдеу және информатиканың семантикалық негізі туралы түсінікті қалыптастыру және машықтандыру; логикалық айнымалылар және арифметикалық амалдардың моделі және ЭЕМ-нің элементтік базасын ықшамдау; салыстыру операцияларын және арифметикалық операцияларды танып-білу; берілген алфавиттер мен сандарды кодтау, алгоритмді іздеу және таңдау, алгоритмдердің тиімділігі мен күрделілігіне анализ жасау, сұрыптауды түсіндіру; көпіршік сұрыптауды түсіндіріп, анализ жасау және пирамидалық сұрыптаудың тиімділігі мен күрделілігіне анализ жасау мәселелерін қамтиды.
5
Ақпаратты алғаннан кейін жоғалатын белгісіздік дәрежесі – бұл ақпараттың сандық сипаттамасы болып табылады және оны ақпарат мөлшері деп атайды. Хабардағы ақпарат мөлшерін өлшеу және бағалау үшін әр түрлі әдістер пайдаланылады. Олардың арасында статистикалық пен алфавитті әдістерді белгілеуге болады. Статистикалық әдістеме. Белгісіздікті немесе Н энтропияны сандық бағалау үшін американ инженеры Р.Хартли мына формуланы ұсынды, бұл формулаға N теңықтималды мүмкіндетердің логарифмы кіреді:
2
оны келесі түрде жазуға болады: 2 H = N, (1.2) мұнда Н — ақпарат мөлшері. Бит деп аталатын ақпарат мөлшерінің ең кіші бірлігі екі мүмкіндіктен таңдауды орындайды. Егер теңықтималды емес таңдау мүмкіндетері орын алса, онда i нөмірі бар таңдаудын Р i меншік ықтималдығына тәуелді h i ақпарат мөлшері К.Шеннон формуласы арықылы есептеледі
i = log 2 (1/P i ), (1.3) оны мына түрге өзгертуге болады 2 hi = (1/P i ). (1.4) Ақпарат мөлшерінің өлшем ретінде h i мәнінің орнына ақпарат мөлшерінің орта мәнің пайдалану ыңғайлы . (1.5) Алфавиттық әдістеме мәтіндік ақпараттың санын анықтауға мүмкіндік береді. Әрбір символ алатын ақпарат мөлшері мына формула арқылы есептеледі
2
мұнда N — алфавит қуаты, ол алфавит ішіндегі символдар санына тең.
N қуаты бар алфавит көмегімен m әріптен тұратың максимал сөздер саның L былайша анықтауға болады L = N m . (1.8)
М 1.1. 32 әр түрлі картасы бар карт колодасы болсын. Бір картаны таңдау үшін 32 мүмкіндік бар. Колодадан қиық королі алынғаны қанша ақпарат алады? Шешім. Мүмкіндіктер саның N = 32 (1.1) формулаға қойғанда ақпарат мөлшерін береді Н = 5(2 H = 2
5 ).
6
түсуі) бір бит ақпарат алады, себебі теңықтималды мүмкіндіктер саны N = 2 (бүк немесе шік). Шік түскені деген хабарда ақпарат мөлшерін анықтаңыз. Шешім. N = 2 (1.1) формулаға қойып, аламыз Н = 1 бит. М 1.3. Белгісіздікті 4 есе азайтатын хабарда қандай ақпарат көлемі бар? Шешім. Білімнің белгісіздігі 4 есе азаяды, сондықтан ол 4-ке тең болды, яғни 4 теңықтималды оқиға болған деп айтуға болады. Осылардың біреуі орын алғаны 2 бит ақапарат әкеледі (4 = 2 2 ). М 1.4. Қорапта 16 кубик жатыр. Барлық кубиктардың түсі әр түрлі. Қораптан қызыл кубик алынды деген хабарда қанша ақпарат бар? Шешім. 16 теңықтималды оқиғалардан біреуін таңдап алу керек. Сондықтан N = 16, осыдан Н = 4 (16 = 2 4 ). М 1.5. Сіздің досыңыз 10-шы қабатта тұрады деген хабарда 4 бит ақпарат бар. Бұл үйде неше қабат бар? Шешім. N = 2 4 = 16 қабат.
М 1.6. Себетте N қ = 8 қара шар және N а = 24 ақ шар жатыр. Себеттен қара шар алынды деген хабарда қанша Н қ ақпарат бар? Шешім. 1) N = 8 + 24 = 32 шар барлығы; 2) Р қ = 8/32 = 1/4 - қара шарды алу ықтималдығы; 3) Н қ = log 2 (l/(l/4)) = 2 бит. М 1.7. Қорапта N = 64 түрлі түсті қарындаш жатыр. Ақ қарындаш алынды деген хабарда Н а = 4 бит ақпараты бар. Қорапта неше N а ақ қарындаш бар болған?
а = log 2 (l/P а ); 4 = log 2 (l/P а ); 1/Р а = 16; Р а = 1/16 - ақ қарындашты алу ықтималдығы; 2) Р а = N а /N; l/16 = N а /64; N а = 64/16 = 4 ақ қарындаш. М 1.8. Себетте ақ және қара шарлар жатыр. Олардың арасында N а = 18 қара шар. Себеттен ақ шар алынды деген хабарда Н а = 2 бит ақпарат бар. Себетте барлығы неше N шар бар? Шешім. 1) 1/Р а = 2 На , 1/Р а = 2
2 = 4, Р а = 1/4 - ақ шарды алу ықтималдығы; 2) Р а = N а /N = N а /(N а + N қ ), 1/4 = N а /(N а + 18), N а + 18 = 4N а , 18 = 3N а , N а = 6
ақ шар; 3) N = N а + N қ = 18 + 6 = 24 шар себетте болған.
М 1.9. Алфавиті N = 128 символдан тұратын тілде жазылған мәтіннің Н м
көлемін анықтаңыз. Хабарда К = 2000 символ бар. 7
2
2 128 = 7 бит — бір символдың көлемі; 2) Н м = Н К = 7 2000 = 14 000 бит — хабардың көлемі. М 1.10. Кейбір тілдің алфавитінде барлығы N = 2 әріп бар, тілдегі әрбір сөз дәл m = 7 әріптен тұрады. Тілдегі ең үлкен сөздер қоры қанша болады? Шешім. Егер алфавит қуаты N, ал осы алфавит көмегімен жазылған сөздегі максимал әріптер саны m болса, онда мүмкін болатын ең үлкен сөздер саны (1.8) формула арқылы анықталады, осыдан N = 2 7 , сондықтан, N = 128. М 1.11. Шахмат тақтасы 64 өрістен тұрады: 8 баған және 8 жол. Бір шахмат өрістің координатасын кодтау үшін қанша ең аз бит қажет болады? Шешім. Шахмат өрісінің 64 торын ажырату үшін екілік кодтың 64 мәні қажет болады. 64=2 6 болғандықтан, екілік кодта алты разряд қажетті. 8
алынған болатын. Осы диапазонда неше сан бар? 1.2. Мектеп кітапханасында 16 стеллаж кітап бар. Әрбір стеллаждың 8 сөресі бар. Қайрат өзіне қажетті кітап бесінші стеллажда үстінен санағанда үшінші сөреде жатыр деп кітапханашыдан естіді. Қайратқа кітапханашы қанша ақпарат берді? 1.3. Бүтін санды 1 ден N–ға дейін диапазонда ойлап тапқан кезде 9 бит ақпарат алынған болатын. N неге тең болады? 1.4. Топта N = 30 студент оқиды. Математикадан бақылау жұмыс бойынша мынадай бағалар алынды: N 5 = 15 бес баға, N 4 = 6 төрт баға, N 3 = 8 үш баға және N 2 = 1 екі. Мұқанов бес алды деген хабарда қанша Н 5 ақпарат мөлшері бар?
хабарда Н 5 = 2 бит ақпарат мөлшері бар. Семестр бойынша студент қанша N 5 бес баға алды? 1.6. Жәшікте қолғаптар (ақ және қара түсті) жатыр. Олардың ішінде N қ = 2 қос қара қолғап бар. Жәшіктен екі қара қолғап алынды деген хабарда Н қ = 4 бит ақпарат мөлшері бар. Жәшікте неше N а қос ақ қолғаптар болды? 1.7. Бөлмені жөндеу үшін ақ, көк және қоныр бояулар пайдаланды. Ақ пен көк бояулар банкісі бірдей жұмсалды N а = N к . Ақ бояу банкісі бітті деген хабарда Н а = 2 бит ақпарат мөлшері бар. Көк бояудың шығыны N к = 8 банкі. Бөлмені жөндеуге қоңыр бояудың N к неше банкісі жұмсалды? 1.8. Аялдамада әртүрлі нөмірлері бар трамвай тоқтайды. Аялдамаға нөмірі N l трамвай келді деген хабарда H Nl = 4 бит ақпарат мөлшері бар. Аялдамаға нөмірі N 2 трамвай келетін ықтималдығы нөмірі N l трамвай келетін ықтималдығынан екі есе аз (P N1 = 2Р N2 ). Аялдамаға нөмірі N 2 трамвай келді деген хабарда қанша H N2 ақпарат мөлшері бар? 1.9. Мәтінді жазу үшін 256-символды алфавит пайдаланды. Әрбір парақта 30 жолы және әрбір жолда 70 символы бар. Мәтіннің 5 парағында қанша ақпарат көлемі бар?
жазылған барлық сөздер 11 әріптен тұрады. Осы тілдің максимал сөздер қоры қанша болу мүмкін?
9
Сандарды бейнелеу әдісін және оған сәйкес сандарға қолданылатын ережелер жинағы санау жүйесі деп аталады. Барлық санау жүйелері позициялы және позициясыз болып екіге бөлінеді. Сандарды бейнелеуге қолданылатын таңбалар цифрлар деп аталады. Позициясыз санау жүйесінде сандардың көлемі берілген санның жазылу орнына байланыссыз. Мысалы, римдік санау жүйесінде цифрлар ретінде латын әріптері қолданылады:
I
X L
С D М 1 5 10 50 100
500 1000
М 2.1. CCXXXII саны екі жүздіктен, үш ондықтан және екі бірліктен құралады. Рим сандарында цифрлар солдан оңға қарай кему тәртібімен жазылады. Бұл жағдайда олардың мәндері қосылады. Егер де сол жақта кіші цифр жазылып, оң жақта үлкен цифр жазылса, бұлардың мәндері кемиді, мысалы:
VI = 5 + 1 = 6, IV = 5 - 1 = 4. М 2.2. Рим саның MCMXCVIII ондық жуйесінде жазыңыз. MCMXCVIII = 1000 + (-100 + 1000) + (-10 + 100) +5+1+1+1= 1998.
Позициялы санау жүйесінде бір ғана берілген цифр санның жазылуындағы орнына байланысты әр түрлі мәнді анықтайды. Қолданылатын цифрлардың саны позициялық санау жүйесінің негізі деп аталады. Қазіргі математикада ондық позиция жүйесі кең тараған. Оның негізі болып он саны алынады, себебі кез келген санды осы он цифрлар арқылы жаза аламыз: 0, 1, 2, 3,4, 5, 6, 7, 8, 9. Бұл жүйенің позициялық сипатын келесі мысал жақсы көрсетеді. 333 деген санның жазылуында сол жақтағы бірінші “3” цифры – үш жүздікті, екінші “3” цифры - үш ондықты, үшінші “3” цифры – үш бірлікті белгілейді. Позициялық жүйеде n – негізді санды жазу үшін n цифрдан тұратын алфавит керек. n – оннан кіші болған жағдайда (n<10), көбінесе, бірінші он араб цифрларын қолданады, ал n – оннан үлкен болғанда (n>10), он араб цифрларына әріптерді қосып қолданады. Кейбір жүйелердің алфавиттер мысалдары 2.1- кестеде көрсетілген. Жүйенің негізін көрсету қажет болса, онда ол берілген санның төменгі индексі ретінде жазылады. Мысалы: 101101 2 , 3671 8 , 3B8F
16 . 2.1-кесте жүктеу/скачать 1,43 Mb. Достарыңызбен бөлісу:
|