Понятие графа. Способы представления графа.

ВОПРОСЫ

Государственного экзамена по информатике

(очное отделение)

2011-2012 учебный год

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ДИСКРЕТНАЯ МАТЕМАТИКА

Понятие высказывания. Операции. Таблица истинности.

2. Законы логики высказываний. Формулы.

Понятия предиката. Логические и кванторные операции над предикатами.

Понятие графа. Способы представления графа.

5. Степень (валентность) вершины графа. Теорема о сумме степеней вершин графа. Виды графов.

6. Связные графы. Компоненты связности графа. Планарные графы.

7. Эйлеровы графы. Критерий эйлеровости. Гамильтоновы графы.

ТЕОРИЯ АЛГОРИТМОВ

1. Понятие об алгоритме и его свойствах. Способы представления алгоритмов. Поня­тие исполнителя алгоритмов и его система команд. Необходимость формализации понятия алгоритма.

2. Машина Тьюринга: алфавит, множество состояний, программа. Функционирова­ние MT. МТ, вычисляющие функции. Тезис Тыоринга. MT, как абстрактная мо­дель современного компьютера.

3. Примитивно-рекурсивные функции. Операция суперпозиции. Операция примитивной рекурсии. Частично-рекурсивные функции. Операция минимизации. Тезисы Черча и Тьюринга, их эквивалентность.

4. Функции и алгоритмы. Вычислимые функции. Примеры вычислимых функций. Суще­ствование невычислимых функций.

5. Разрешимые множества и их свойства. Примеры разрешимых множеств. Существование неразрешимых множеств.

6. Перечислимые множества и их свойства. Примеры перечислимых множеств. Теорема Поста. Пример перечислимого, но неразрешимого множества.

7. Эффективно счетные множества. Геделевская нумерация алгоритмов. Построение не­вычислимой функции (диагональная конструкция). Построение неразрешимого, но пе­речислимого множества.

8. Неразрешимые алгоритмические проблемы. Проблема самоприменимости. Проблема остановки. Проблема всюду определенности. Проблема эквивалентности алгоритмов.

9. Теория сложности алгоритмов. Сложность пространственная и временная. Классы Р и NP. NP- полные задачи. Примеры.

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ

1. Понятие информации. Носители информации. Формы представления информации. Преобразование сообщений.
2. Энтропия. Условная энтропия. Энтропия и информация. Формулы Хартли и Шеннона. Информация и алфавит. Избыточность языка.
3. Задача кодирования. Теорема Шеннона о кодировании при отсутствии помех. Алфавитное кодирование. Равномерные коды. Разделимые коды.
4. Префиксные коды. Разделимость префиксного кода. Неравенство Макмиллана.
5. Оптимальное кодирование. Код Шеннона-Фано. Код Хаффмана.
6. Блочное кодирование. Алгоритм Лемпела-Знва для сжатия данных.
7. Функциональные и автоматные преобразователи информации. Определение автомата Мили. Функция переходов и функция выходов. Представление автомата в виде графа. Автоматы Мура.

ЧИСЛЕННЫЕ МЕТОДЫ

1. Методы численного решения уравнении. Отделение корней. Метод деления пополам.
2. Методы численного решения уравнений. Метод итераций. Метод касательных. Метод хорд.
3. Интерполяция функций многочленами. Построение интерполяционного многочлена с помощью системы линейных уравнений. Интерполяционный многочлен Лагранжа.
4. Метод наименьших квадратов. Приближение функций по методу наименьших квадратов.
5. Численное интегрирование. Квадратурные формулы. Формула прямоугольников. Формула трапеций. Формула Симпсона.
6. Численное дифференцирование. Формулы нахождения производной. Вычисление второй производной.

ПРОГРАММИРОВАНИЕ

1. Технология проектирования программ: структурное, модульное и объектно-ориентированное программирование. Классификация и сравнительный анализ языков программирования. Основные этапы разработки программы.

2. Основные конструкции алгоритмических языков программирования: алфавит, данные, величины, имена, выражения, функции, операторы. Базовые алгоритмические конструкции (последовательность, ветвление, цикл) и нх реализация в конкретных языках программирования.