Методические рекомендации по подготовке к государственному итоговому экзамену "Информатика" выпускников физико-математического факультета. Губина Т.Н - 25 стр.

                                               Кафедра Вычислительной математики и информатики
Содержание ответа: Понятие циклического и ациклического ребра, понятие «дерево», его
характеристические свойства, ориентированное дерево и его свойства, корень и вершины i-
того яруса дерева, остов графа.
Понятие четного графа, эйлеров граф, теорема Эйлера, равновесный эйлеров граф.
Понятие полного графа, полного ориентированного и неориентированного графа. Двудоль-
ный граф, полный двудольный граф. (cм. [2, с. 8-18])

6. Основные методы разработки эффективных алгоритмов: динамическое програм-
мирование, алгоритмы с возвратом, жадные алгоритмы.

Содержание ответа: Суть динамического программирования, его применение к решению
задач оптимизации. Структура алгоритма, на котором базируется данный метод.
Сущность алгоритма с возвратом и примеры его применения к решению задач.
Сущность жадного алгоритма. Сравнение методов разработки алгоритмов. (cм. [2, с. 35-41])

7.   Понятие сложности алгоритма. Оценка сложности алгоритма.

Содержание ответа: Понятие труднорешаемой задачи. Полиномиальные и экспоненциаль-
ные алгоритмы. Понятие самого эффективного алгоритма. Алгоритмически неразрешимые
задачи. Временная сложность алгоритма. Вычисление времени работы алгоритма. Формулы
для нахождения функции временной сложности алгоритма. Понятие верхней и нижней оцен-
ки времени работы алгоритма. (см. [2, с. 41-42], [6, c. 196-203])

8. Кодирование. Алфавитное неравномерное двоичное кодирование. Префиксные
коды.

Содержание ответа: Понятия «код», «кодирование», «декодирование», «кодер», «декодер»,
обратимость операций кодирования и декодирования. Необходимое условие применения ко-
да. Длина кода. Оптимальный код. Равномерный и неравномерный код. Понятие избыточно-
сти кода. Первая теорема Шеннона.
Способы построения двоичных кодов: алфавитное неравномерное двоичное кодирование.
Постановка задачи оптимизации неравномерного кодирования. Подходы к обеспечению раз-
личимости кодов при использовании неравномерного кодирования (использовании специ-
альной комбинации элементарных сигналов, применение префиксных кодов). Условие Фано
для префиксных кодов. Префиксный код Шеннона-Фано, Хаффмана. (cм. [6, c. 58-71])

9.   Алфавитное кодирование с неравной длительностью сигналов. Код Морзе.

Содержание ответа: Телеграфный код Морзе: Что понимают под знаками кода Морзе,
принцип кодирования. (cм. [6, c. 74-76])

10. Блочное двоичное кодирование. Равномерное двоичное кодирование. Байтовый
код.

Содержание ответа: Блочное двоичное кодирование: понижение избыточности.
Алфавитное равномерное кодирование: построение двоичного кода первичного алфавита.
Примеры равномерного алфавитного двоичного кодирования: телеграфный код Бодо, пред-


                                          25