Ответы на госэкзамен. 10 разделов. Информатика + Програмирование. 2015 год.

1. Дискретная математика
1. Множества и операции над ними. Алгебра множеств. Диаграммы Эй-лера-Венна.
2. Соответствия, отношения, функции. Отношения эквивалентности.
3. Отношения порядка. Частично упорядоченные множества. Диа-граммы Хассе. Решетки.
4. Конечные и бесконечные множества. Мощность множеств. Сравнение мощностей. Мощность множества действительных чисел. Кардиналь-ные числа.
5. Понятие высказывания. Булевы алгебры. Булевы функции. Основные равносильности алгебры множеств.
6. Формы представления высказываний (ДНФ, СДНФ, КНФ, СКНФ).
7. Минимизация высказываний (метод Квайна, метод карт Вейча)
8. Графы. Типы графов. Операции над графами. Способы задания гра-фа.
9. Графы. Маршруты, цепи, циклы. Эйлеров цикл. Гамильтонов цикл.
10. Определение кратчайшего пути в графе (алгоритмы Дейкстры, Шимбелла).
11.  Планарные графы. Алгоритм укладки графа на плоскости.
12. Деревья. Остовной подграф. Остов наименьшего веса (алгоритмы Краскала, Прима).
13.  Алгоритмы Магу для нахождения ядра и клики графа.
14. Раскраски графа. Теорема о 4 красках. Теорема о 5 красках. Хроматическое число графа.

2. Математическая логика и теория алгоритмов
1. Булевы функции. формулы, равносильные формулы, подстановка и замена. Замкнутые классы булевых функций. Полные системы функций.
2. Формальные теории. Исчисление высказываний. Теорема дедукции.
3. Формальные теории. Исчисление предикатов.
4. Основные равносильности для предикатов. Предваренная нормаль-ная форма.
5. Автоматическое доказательство теорем. Правило резолюции для ис-числения высказываний. Правило резолюции для исчисления предикатов.
6. Интуитивное понятие алгоритма. Уточнения понятие алгоритма (ма-шина Тьюринга, нормальные алгорифмы Маркова, рекурсивные функции).Тезис Черча.
7. Алгоритмически неразрешимые проблемы.
8. Характеристики сложности вычислений. Классы сложности задач.

3. Исследование операций и методы оптимизации систем
9. Классы задач принятия решений, типовые задачи исследования операций.
10. Принятие решений в условиях риска, неопределенности и конфликта.
11. Графы и показатели эффективности СМО с простейшими потоками.
12. Основы линейного программирования: постановка, геометрия, свой-ства, идеи методов.
13. Транспортные задачи: модели и методы.
14. Задачи на транспортной сети.
15. Методы управления проектом, СПУ.
16. Двойственность задач оптимизации: модели, интерпретация, методы.
17. Методы определения целочисленных решений.
18. Основы динамического программирования. Достоинства и недостатки метода.
19. Оптимизация надежности технических систем, систем распределения ресурсов методом ДП.
20. Классы задач нелинейного программирования и методы их решения.
21. Задачи нелинейного программирования, сводящиеся к линейным.
22. Методы случайного поиска и генетические алгоритмы.

4. Объектно-ориентированное программирование
1. Основные принципы объектно-ориентированного программирова-ния. Способы описания классов. Поля, методы и свойства. Статические члены и члены экземпляров. Создание и уничтожение объектов.
2. Наследование классов. Создание и уничтожение объектов производных классов. Наследование интерфейсов. Реализация интерфейсов. Клонирование объектов.
3. Полиморфизм. Виртуальные методы. Абстрактный класс.
4. Механизмы событий в объектно-ориентированном программировании. События и делегаты. Обработка событий.
5. Хранение данных в файлах. Потоковый ввод-вывод. Форматирование. Обработка ошибок. Сериализация объектов.
6. Перегрузка операций.
7. Обобщения (шаблоны). Шаблоны функций. Шаблоны классов.
8. Механизм обработки исключительных ситуаций в объектно-ориентированном программировании. Контролируемый блок. Генерация исключений. Обработка исключений.
9. Механизм динамической идентификации типов.
10. Хранение данных в коллекциях. Основные типы коллекций: массивы, списки, словари. Шаблонные и не шаблонные коллекции.
11. Типовые алгоритмы в библиотеках классов. Их использование в программирование. Основные алгоритмы.

5. Алгоритмы и структуры данных
1. Абстрактный тип данных список. Реализация с помощью массива. Особенности выполнения операций включения и удаления из списка.
2. Абстрактный тип данных список. Реализация с помощью курсора. Особенности выполнения операций включения и удаления из списка.
3. Абстрактный тип данных список. Реализация с помощью указателей. Особенности выполнения операций включения и удаления из списка.
4. Абстрактный тип данных стек. Реализация с помощью массива. Проверка правильности расстановки нескольких пар скобок в выражении.
5. Абстрактный тип данных стек. Реализация с помощью указателей. Перевод выражения в Польскую инверсную запись.
6. Абстрактный тип данных стек. Реализация с помощью курсора. Вычисление значения выражения по его Польской инверсной записи.
7. Деревья. Создание и обход деревьев (рекурсивный и не рекурсив-ный).
8. Двоичные деревья поиска и сортировки.
9. Хэширование. Методы разрешения коллизий.
10. Сортировки выбором, обменом и вставками.
11. Метод Шелла, быстрая сортировка Хоара.
12. Внешняя сортировка.
13. Б – деревья. Особенности представления Б – деревьев. Операции вставки и удаления.
14. Графы. Обход графов в ширину и глубину.
15. Тип данных «куча». Сортировка с помощью «кучи».
16. Алгоритмы Прима и Крускала.
17. Алгоритм Дейкстры.

6. Базы данных
1. Основные понятия СУБД. Архитектура ANSI/SPARC. Функции администратора баз данных. Архитектура клиент-сервер. Соотношение си-стем БД (СУБД, хранилища данных, пользовательские интерфейсы, мониторы транзакций).
2. Реляционная модель данных основные понятия. Три аспекта модели данных: структура, целостность и операции обработки данных. Реляционная алгебра. Реляционное исчисление. Оптимизация запросов.
3. Основные возможности языка SQL. Описание таблиц. Ограничения целостности.
4. Язык SQL. Манипулирование данными.
5. Язык SQL. Оператор select.
6. Проектирование БД. Нормальные формы. Функциональные зависимости. Декомпозиция без потерь в нормальную форму Бойса-Кодда (НФБЛ).
7. Многозначные зависимости их свойства. Понятие четвертой и пятой нормальных форм. Понятие не нормализованных отношений.
8. Описание схемы БД на языке стандарта IDEF1X.
9. Специальные вопросы проектирования БД. Домены и их использование. Целостность, аспекты целостности, методы обеспечения целостности в современных СУБД. Представления особенности их применения.
10. Поддержка параллелизма в СУБД. Транзакции. АСИД-свойства транзакций.
11. Администрирование СУБД. Особенности реализации. Инсталляция на различные платформы. Доступ к системным таблицам. Задачи администратора СУБД. Утилиты администрирования.
12. Физическая организация СУБД. Структуры хранения данных и методы доступа. Способы ускорения доступа к данным (индексы).
13. OLAP системы. Архитектура. Интеллектуальная обработка данных.

7. Операционные системы и сети
1. Понятие операционной системы (ОС). Функции ОС. Виды ОС: дисковые ОС, универсальные ОС, системы реального времени, микроядерные и с монолитным ядром, средства кросс-разработки, системы виртуальных машин.
2. Архитектура операционной системы. Ее связь с системным, прикладным программным обеспечением и аппаратными средствами.
3. Файловые системы. tar, fat, fat32, s5fs, ext2, vfs. Журналируемые файловые системы.
4. Понятие процесса в операционной системе. Состояния процессов. Диаграмма переходов. Диспетчеризация процессов.
5. Управление памятью операционной системой. Своппинг. Подкачка по запросу.
6. Драйверы. Алгоритмы управления устройствами ввода-вывода. Опрос. Прерывания. Прямой доступ к памяти.
7. Взаимодействие процессов. Сигналы. Именованные и неименованные каналы. Пакет IPC. Сокеты.

8. Сети ЭВМ и телекоммуникации
1. Основные понятия OSI RM. Система, прикладной процесс, приклад-ной объект, соединение, физические средства соединения, область взаимо-действия открытых систем. Уровень, объект, протокол, интерфейс, транс-портная сеть, сеть передачи данных, абонентские службы. Сервис, услуга, функция, сервисная точка доступа (SAP), конечная точка соединения.
2. Механизмы управления потоком и исправления ошибок на ка-нальном уровне: управление потоком (Stop-and-Wait, Sliding-Window), обнаружение ошибок (Parity Check, CRC), исправление ошибок (Stop-and-Wait ARQ, Go-Back-N ARQ, Selective-Reject ARQ).
3. Форматы Ethernet-кадров и назначение полей заголовка. Поясните и проиллюстрируйте назначение и типы МAC- и SAP-адресов, понятия диаметр сети, домен коллизии и широковещательный домен.
4. Поясните смысл сегментации локальной сети. Проиллюстрируйте механизм самообучения коммутатора и процесс прохождения кадра через коммутатор;
5. Проиллюстрируйте проблемы петлевой топологии устройств L2 уровня и объясните назначение и работу протокола распределенного связующего дерева (STP).
6. Механизм образования магистралей и виртуальных локальных се-тей VLAN. Иллюстрация движения кадра между компьютерами одной VLAN, подключенных к разным коммутаторам
7. Сервис протокола IP, реализуемый полями IP- заголовка.
8. Классовая модель IP-адресации. Назначение специальных IP адре-сов. Кто распределяет IP-адресное пространство в Интернет?
9. Бесклассовая модель IP-адресации, иллюстрация VLSM-маскирования.
10. Вскройте понятия: маршрутизация, маршрутизатор, маршрутизируемый протокол, таблица маршрутизации, протоколы маршрутизации, алгоритмы маршрутизации, прямая и косвенная маршрутизация.
11. Структура таблицы маршрутизации и процесс ее формирования в классовой и бесклассовой модели маршрутизации.
12. Процесс маршрутизации IP-пакета. Проиллюстрируйте процесс формирования IP и MAC адресов при движении IP пакетов через сеть передачи данных.
13. Поясните иерархическую модель маршрутизации в Интернет и понятия: клиент-провайдер, Автономная система (AS), Core, пиринг, пиринговые войны, маршрутизация внутри (intra) и между (inter) AS, типы AS.
14. Проиллюстрируйте предоставляемый протоколам TCP сервис и назначение полей заголовков этих протоколов. Механизм установления TCP-соединения.
15. Механизм управления потоком, предотвращения перегрузки, и исправления ошибок в TCP-соединении. Проиллюстрируйте алгоритм медленного старта.
16. Назначение доменной системы имен (DNS), принципы трансляции имен и организации системы корневых серверов.

9. Функциональное и логическое программирование
1. Виды программирования. Императивное и декларативное. Функциональное и логическое.
2. Функциональное программирование. Лямбда-исчисление. Термы. Конверсии. Теорема Чёрча-Россера.
3. Функциональное программирование. Комбинаторная логика. Свободные и связанные переменные. Комбинаторы. Языки, основанные на комбинаторной логике.
4. Функциональное программирование. S-выражения. Язык Лисп.
5. Логическое программирование. Предикаты. Метод резолюций. Хорновские дизъюнкты.
6. Логическое программирование. Язык Пролог. Обработка списков.
7. Логическое программирование. Язык Пролог. Реализация баз данных и формальных грамматик.

10. Теория языков программирования
1. Транслятор. Понятие транслятора. Претранслятор. Типы трансляторов. Интерпретатор. Компилятор. Структура компилятора.
2. Этапы компиляции. Лексический анализ. Способы реализации. Автоматные грамматики. Автоматы. Регулярные выражения. Генератор lex.
3. Этапы компиляции. Синтаксический анализ. LL-грамматика. МП-автоматы. Метод рекурсивного спуска.
4. Этапы компиляции. Синтаксический анализ. LR-грамматики. Грамматика с предшествованием. Генератор yacc.
5. Этапы компиляции. Семантический анализ. Атрибутные грамматики. Использование yacc для реализации атрибутных грамматик.
6. Этапы компиляции. Промежуточное представление. Формы промежуточного представления. Ориентированный граф. Трехадресный код. Линеаризованное представление.
7. Этапы компиляции. Генерация выходного кода. Таблицы решений.

Более 200 страниц. Полные ответы. Аналогов нет.