Практикум павлодар 2014 удк

ЛОГИКА АЛГЕБРАСЫНЫҢ НЕГІЗГІ ҰҒЫМДАРЫ 22

жүктеу/скачать 1,42 Mb.

бет	3/20
Дата	07.01.2022
өлшемі	1,42 Mb.
	#16918
түрі	Практикум

1 2 3 4 5 6 7 8 9 ... 20

3 ЛОГИКА АЛГЕБРАСЫНЫҢ НЕГІЗГІ ҰҒЫМДАРЫ 22

3.1 Логикалық өрнектерді оңайлату 23

3.2 Ақиқаттық кестелерді құрастыру 25

3.3 Логикалық сұлбаны құрастыру 26

ӨЗІНДІК ЖҰМЫС ТАПСЫРМАЛАРЫ 28

3.4 Бақылау тест тапсырмалары 30

4 АҚПАРАТТЫҚ ҮДЕРІСТЕРДІ АВТОМАТТАНДЫРУ

АБСТРАКТІЛІ АВТОМАТТАР 34

4.1 Тьюринг машинасы 34

4.2 Пост машинасы 37

4.3 Тьюринг және Пост машинасы көмегімен «алгоритм» ұғымын анықтау 38

4.4 Марковтың нормальды алгоритмдері 39

4.5 Бақылау тест тапсырмалары 41

5 АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ НЕГІЗГІ ҰҒЫМДАРЫ 45

5.1 Алгоритмнің қасиеттері 45

5.2 Алгоритмді жазу тәсілдері 45

5.3 Блок – схемалар 47

5.4 Алгоритм құрылыстары 51

ӨЗІНДІК ЖҰМЫС ТАПСЫРМАЛАРЫ 57

6 АҚПАРАТТЫҚ МОДЕЛЬДЕУ 60

6.1 Модельдерді әр түрлі белгілеріне қатысты топтастыру 60

6.2 Компьютерлік модельдеудің кезеңдері 62
ӨЗІНДІК ЖҰМЫС ТАПСЫРМАЛАРЫ 68

ПАЙДАЛАНЫЛҒАН ӘДЕБИЕТТЕР 69

КІРІСПЕ
Теориялық информатика – математикалық ғылым. Ол математиканың бірнеше бөлімдеріне негізделген: автоматтар мен алгоритмдер теориясы, математикалық логика, формалды тілдердің және грамматикалардың теориясы, ақпарат теориясы және т.б. Теориялық информатика ақпаратты сақтау және өндеу кезінде пайда болатын негізгі сұрақтарға дәл талдау әдістері арқылы жауап беруге тырысады, мысалы, кейбір ақпараттық жүйеде жинақталған ақпарат саны неге тең, сақтау немесе іздеу үшін ақпаратты тиімді ұйымдастыру, сонымен қатар ақпаратты түрлендіру алгоритмдердің бар болу және қасиеттер туралы. Ай сайын деректерді сақтауға арналған ең үлкен көлемі бар жаңа құрылғылар пайда болуда, бұл ақпарат теориясы мен кодтау теориясының дамуымен түсіндіріледі. Қолданбалы есептерді шешу үшін жақсы программалар бар, бірақ сауатты түрде қолданбалы есепті қою үшін, оны компьютерге түсінікті түрге келтіру үшін ақпараттық және математикалық модельдеу негіздерін және т.б. білу керек. Информатиканың тек осы бөлімдерін меңгере отырып, өзіңізді осы ғылымның маманы деп есептей аласыз.
Информатиканың теориялық негіздері курсы информатиканың фундаментальді ұғымдары: ақпараттар теориясының негізі, сандық автоматтар теориясы, алгоритмдер теориясы, алгоритмдер тиімділігінің анализі, ақпараттық модельдеу және информатиканың семантикалық негізі туралы түсінікті қалыптастыру және машықтандыру; логикалық айнымалылар және арифметикалық амалдардың моделі және ЭЕМ-нің элементтік базасын ықшамдау; салыстыру операцияларын және арифметикалық операцияларды танып-білу; берілген алфавиттер мен сандарды кодтау, алгоритмді іздеу және таңдау, алгоритмдердің тиімділігі мен күрделілігіне анализ жасау, сұрыптауды түсіндіру; көпіршік сұрыптауды түсіндіріп, анализ жасау және пирамидалық сұрыптаудың тиімділігі мен күрделілігіне анализ жасау мәселелерін қамтиды.

1 АҚПАРАТ ЖӘНЕ ОНЫҢ ҚАСИЕТТЕРІ
Ақпаратты алғаннан кейін жоғалатын белгісіздік дәрежесі – бұл ақпараттың сандық сипаттамасы болып табылады және оны ақпарат мөлшері деп атайды. Хабардағы ақпарат мөлшерін өлшеу және бағалау үшін әр түрлі әдістер пайдаланылады. Олардың арасында статистикалық пен алфавитті әдістерді белгілеуге болады.
Статистикалық әдістеме. Белгісіздікті немесе Н энтропияны сандық бағалау үшін американ инженеры Р.Хартли мына формуланы ұсынды, бұл формулаға N теңықтималды мүмкіндетердің логарифмы кіреді:

H = log₂N, (1.1)

оны келесі түрде жазуға болады:

2^H=N,	(1.2)
мұнда Н — ақпарат мөлшері.

Бит деп аталатын ақпарат мөлшерінің ең кіші бірлігі екі мүмкіндіктен таңдауды орындайды.
Егер теңықтималды емес таңдау мүмкіндетері орын алса, онда i нөмірі бар таңдаудын Р_i меншік ықтималдығына тәуелді h_i ақпарат мөлшері К.Шеннон формуласы арқылы есептеледі

h_i = log₂(1/P_i),	(1.3)
оны мына түрге өзгертуге болады
2^hi = (1/P_i).	(1.4)
Ақпарат мөлшерінің өлшем ретінде h_i мәнінің орнына ақпарат мөлшерінің
орта мәнің пайдалану ыңғайлы
.	(1.5)

Алфавиттық әдістеме мәтіндік ақпараттың санын анықтауға мүмкіндік береді. Әрбір символ алатын ақпарат мөлшері мына формула арқылы есептеледі

i = log₂N, (1.6)

мұнда N — алфавит қуаты, ол алфавит ішіндегі символдар санына тең.

символы бар мәтіннің ақпарат көлемі тең болады

I = Ki.	(1.7)
N қуаты бар алфавит көмегімен m әріптен тұратың максимал сөздер саның
L былайша анықтауға болады
L = N^m.	(1.8)

жүктеу/скачать 1,42 Mb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7 8 9 ... 20