Перечень вопросов, вносимых в экзаменационные билеты
Дисциплина «Структуры и алгоритмы обработки данных»
1. спецификация, представление, реализация абстрактных типов данных
2. линейные структуры данных: стек, очередь, дек
3. нелинейные структуры данных: иерархические списки, деревья и леса, бинарные деревья
4. нелинейные структуры данных: обходы деревьев;
5. поиск и кодирование (сжатие) данных, кодовые деревья, оптимальные префиксные коды
6. исчерпывающий поиск: перебор с возвратом, метод ветвей и границ, динамическое программирование
7. бинарный поиск, хеширование;
8. использование деревьев в задачах поиска: бинарные деревья поиска, случайные, оптимальные, сбалансированные по высоте и рандомизированные деревья поиска;
9. задачи сортировки; внутренняя и внешняя сортировки;
10. алгоритмы сортировки;
11. оптимальная сортировка;
12. порядковые статистики;
13. анализ сложности и эффективности алгоритмов поиска и сортировки;
14. файлы: организация и обработка, представление деревьями: B-деревья;
15. алгоритмы на графах: представления графов, схемы поиска в глубину и ширину, минимальное остовное дерево, кратчайшие пути;
16. теория сложности алгоритмов: NP-сложные и труднорешаемые задачи.
Дисциплина «Функциональное и логическое программирование»
1. Математические основы функционального программирования: лямбда-исчисление А.Черча и теория рекурсивных функций: основные понятия и положения. Программирование в функциональных обозначениях. Строго функциональный язык. Соответствие между функциональными и императивными программами.
2. Функциональные языки программирования. Представление и интерпретация функциональных программ. Отладка функциональных программ: функции трассировки, организация процесса отладки. Рекурсивные функции. Основы теории рекурсивных функций, виды рекурсии, рекурсия и итерации.
3. Конкретные реализации языков функционального программирования: язык программирования Лисп, основные объекты, примитивы, списки, правила составления программ.
4. Основные конструкции логической программы: факты, правила, запросы, логические переменные. Операционная и декларативная семантика логических программ,
5. Интерпретация и корректность логических программ. Абстрактный интерпретатор, значение логической программы, вычислительная модель.
6. Программирование баз данных. Динамическая база данных. Добавление и удаление фактов в процессе работы программы.
7. Рекурсивное программирование на логическом языке. Рекурсивные структуры данных – списки. Объявление списков. Составные списки. Голова и хвост списка. Примеры работы со списками.
8. Вычислительная модель программы на логическом языке. Согласование целевых утверждений. Сопоставление и унификация. Детерминизм.
9. Множественные выражения. Программирование второго порядка. Недетерминированное программирование. Метод «образовать и проверить».
10. Внелогические предикаты. Ввод-вывод. Доступ к программам и обработка программ. Металогические предикаты. Сравнение не основных термов.
11. Обработка нечетких данных на Прологе. Реализация на Прологе нечетких логических выводов. Применение логического и функционального программирования в задачах искусственного интеллекта.
12. Constraint–Пролог: операционная семантика обобщение механизма унификации, понятие constraint'а. Операционная модель Constraint-ПРОЛОГа.
Дисциплина «Теория вычислительных процессов»
1. Семантическая теория программ. Вычислимость и разрешимость.
2. Стандартные схемы программ. Методы формальной спецификации и верификации.
3. Определение асинхронного процесса как описания модели вычислительного процесса. Глобальные свойства – асинхронность, недетерминированность, параллельность.
4. Подклассы асинхронного процесса. Эффективный асинхронный процесс.
5. Конвейерный процесс. Автономный процесс. Асинхронный процесс как метамодель.
6. Определение, способы задания сетей Петри. Синтаксис и семантика сетей Петри.
7. Понятие выполнения сети. Свойства сети (устойчивость, безопасность, консервативность).
8. Классификация сетей (ординарные, автоматные, маркированный граф).
9. Сетевое представление параллельных процессов. Области применения сетей Петри.
10. Протоколы взаимодействия объектов вычислительных структур. Понятие протокола.
11. Интерфейсы. Способы согласования аппаратных структур. Организация асинхронных интерфейсов.
Дисциплина «Теория языков программирования и методы трансляции»
1. Основы теории формальных языков и грамматик. Основные понятия и определения. Операции над языками. Классификация формальных языков и грамматик по порождающей способности.
2. Вывод контекстно-свободных (КС) – грамматик и правила построения дерева вывода. Синтаксический разбор. Способы задания схем грамматик. Форма Бэкуса-Наура.
3. Недетерминированные конечные автоматы. Конечные преобразователи и переводы. Преобразование некоторых грамматик к автоматному виду.
4. Детерминированные конечные автоматы. Эквивалентные состояния и автоматы.
5. Автоматы с магазинной памятью. Язык, допускаемый магазинным автоматом. Построение автомата с магазинной памятью. Функции перехода. Способы задания функций перехода автомата с магазинной памятью.
6. Нисходящие распознаватели. LL(k)- грамматики. Построение детерминированного нисходящего распознавателя.
7. Восходящие распознаватели. LR(k) – грамматики. Построение и работа распознавателя.
8. Магазинные преобразователи. Определение магазинного преобразователя. Перевод, определяемый преобразователем.
9. Описание перевода или трансляции. Синтаксически – управляемые (СУ) – схемы. Перевод, определяемый СУ – схемой. Построение простой СУ – схемы.
10. Транслирующие грамматики. Построение транслирующей грамматики по СУ- схеме. (2 часа).Атрибутные транслирующие (АТ) грамматики. Определение АТ – грамматик.
11. Трансляторы, интерпретаторы и компиляторы. Стадии работы компилятора. Лексический анализ.
12. Синтаксический анализ. Метод оперативного предшествования. Восходящие и нисходящие методы синтаксического анализа.