Теория алгоритмов и программ (190,00 руб.)

Стр.2

Стр.115

УДК 004.021(075) ББК 22я7 Я31 Печатается по решению редакционно-издательского совета Казанского национального исследовательского технологического университета Рецензенты: генеральный директор НПП «ГКС» И. А. Юманкин главный метролог НИЦ «Инкомсистем» Р. Р. Замалетдинов Я31 Ягьяева Л. Т. Теория алгоритмов и программ : учебное пособие / Л. Т. Ягьяева, М. Ю. Валеев; Минобрнауки России, Казан. нац. исслед. технол. ун-т. – Казань : Изд-во КНИТУ, 2019. – 116 с. ISBN 978-5-7882-2737-5 Рассмотрены основные положения теории информации и теории алгоритмов и программ, а также основы кодирования символьной информации. Представлены задания по методам сортировки и поиска. Предназначено для студентов института управления, автоматизации и информационных технологий, изучающих дисциплину «Теория алгоритмов и программ» для направления подготовки 09.03.01 «Информатика и вычислительная техника». Подготовлено на кафедре автоматизированных систем сбора и обработки информации. УДК 004.021(075) ББК 22я7 ISBN 978-5-7882-2737-5 © Ягьяева Л. Т., Валеев М. Ю., 2019 © Казанский национальный исследовательский технологический университет, 2019 2

Стр.2

СОДЕРЖАНИЕ ВВЕДЕНИЕ ...................................................................................................................................... 3 Глава 1. ТЕОРИЯ ИНФОРМАЦИИ. ............................................................................................. 4 1.1. Основные положения. .............................................................................................................. 4 1.2. Исходные понятия информатики. ........................................................................................... 7 1.3. Формы представления информации ..................................................................................... 11 1.4. Понятие информации в теории шеннона. понятие энтропии ............................................ 18 1.4.1. Условная энтропия. ........................................................................................................... 22 1.4.2. Энтропия и информация. ................................................................................................. 26 1.5. Информация и алфавит. ......................................................................................................... 32 Контрольные вопросы к главе 1 .................................................................................................. 37 Глава 2. ТЕОРИЯ АЛГОРИТМОВ И ПРОГРАММ ................................................................... 38 2.1. Основные понятия алгоритма. Правила построения и разбиение программы ................ 38 2.2. Алгоритм как абстрактная машина ...................................................................................... 45 2.2.1. Общие подходы ................................................................................................................. 45 2.2.2. Алгоритмическая машина Поста ..................................................................................... 47 2.2.3. Алгоритмическая машина Тьюринга .............................................................................. 50 2.2.4. Нормальные алгоритмы Маркова ................................................................................... 57 2.3. Основные понятия сортировки и поиска ............................................................................. 59 2.3.1. Сортировка ........................................................................................................................ 60 2.3.1.1. Сортировка методом попарной перестановки (метод пузырька) ........................ 64 2.3.1.2. Сортировка информационных массивов методом подсчета ................................ 67 2.3.1.3. Сортировка информационных массивов методом вставки ................................... 69 2.3.1.4. Сортировка информационных массивов методом Шелла ..................................... 71 2.3.2. Поиск. ................................................................................................................................. 76 2.3.2.1. Последовательный поиск в информационном массиве ........................................... 77 2.3.2.2. Бинарный поиск в информационном массиве ........................................................... 80 Контрольные вопросы к главе 2 .................................................................................................. 83 Глава 3. КОДИРОВАНИЕ СИМВОЛЬНОЙ ИНФОРМАЦИИ ................................................. 84 3.1. Первая теорема шеннона. Основные понятия ..................................................................... 84 3.2. Способы построения двоичных кодов ................................................................................. 89 3.2.1. Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды ................................................................................... 89 3.2.2. Равномерное алфавитное двоичное кодирование. Байтовый код ................................ 96 3.2.3. Алфавитное кодирование с неравной длительностью элементарных сигналов. Код Морзе .......................................................................................................................... 98 3.2.4. Блочное двоичное кодирование ..................................................................................... 101 Задачи для самостоятельного решения ..................................................................................... 103 Контрольные вопросы к главе 3 ................................................................................................ 104 ГЛОССАРИЙ ............................................................................................................................... 105 СПИСОК ЛИТЕРАТУРЫ ........................................................................................................... 108 ПРИЛОЖЕНИЕ ........................................................................................................................... 109 115

Стр.115