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

Елецкий государственный университет им. И.А. Бунина
       Алгоритмы оптимизации на сетях и графах. Понятие жадного алгоритма. Матроиды.
Теорема Радо-Эдмондса. Приближенные комбинаторные алгоритмы, оценка их точности.
Апроксимируемость трудных задач.

         Содержание ответов на экзаменационные вопросы по дисциплине
                     «Теоретические основы информатики»

1. Понятие алгоритма. Необходимость уточнения понятия алгоритма. Алгоритми-
ческая машина Поста.

Содержание ответа: Общие подходы к алгоритму как абстрактной машине. Уточнение по-
нятия «алгоритм». Алгоритмическая машина Поста: из чего состоит, система команд маши-
ны, дополнительные условия, накладываемые на команды, используемая система счисления
для записи информации в машине Поста.
(см. [5, с. 53-60, 2, с. 42-44], [6, c. 167-173, c. 179-184])

2.    Машина Тьюринга. Устройство. Состояние машины. Конфигурация.

Содержание ответа: Составные части машины Тьюринга, внешний и внутренний алфавит
машины, система команд, выполняемых считывающее-записывающей головкой, логическое
устройство машины. Схема функционирования машины. Общее правило, по которому рабо-
тает машина. Функциональная схема машины. Конфигурация машины, начальная конфигу-
рация машины. Тезис Тьюринга.
(см. [5, с. 60-63, 2, с. 44-48], [6, c. 184-192])

3. Нормальные алгоритмы Маркова. Сравнение алгоритмических схем Маркова и
Тьюринга.

Содержание ответа: Понятие нормального алгоритма, основные определения: слово, его
длина, пустое слово, подслово.
Понятие алгоритма применительно к данному подходу. Подстановка, система подстановок.
Сопоставление алгоритмических моделей: Тьюринга и Маркова. Теорема о сводимости од-
ной алгоритмической модели к другой.
(см. [5, с. 63-66], [6, c. 192-196])

4. Основные понятия теории графов. Степень вершины графа. Ориентированные
графы, связные графы и компоненты связности. Понятие взвешенного графа. Спосо-
бы задания графа.

Содержание ответа: Понятие графа, ориентированный и неориентированный граф, ребро
графа, дуга графа, изолированная вершина графа, концевое ребро, петля, смежные и кратные
ребра. Степень вершины графа. Связные графы и компоненты связности. Способы задания
графа: перечисление ребер графа, матрица смежности вершин графа, матрица достижимости
вершин графа, матрица инциденций графа, представление графа в виде геометрического объ-
екта. (cм. [2, с. 5-8], [3, c. 57-61])

5.   Деревья. Эйлеровы графы. Полный граф, двудольный граф.


                                                 24