|
|
ВОПРОСЫ
| учебный год |
1.Элементы графа, способы задания графов. Цепи и циклы в графах. Верхняя и нижняя оценки числа ребер в графе с данным числом компонент связности.
2. Плоские графы. Теорема Эйлера. Теорема Жордана о кривых (без док-ва). Теорема Понтрягина-Куратовского (без док-ва). Реализация графов в трехмерном пространстве. Метрическое пространство, связанное с графом.
3. Эйлеровы и гамильтоновы цепи и циклы. Критерий эйлеровости графа. Покрытие графа минимальным числом цепей без общих ребер. Признак Дирака гамильтоновости графа.
4. Орграфы и мультиграфы. Верхняя оценка числа неизоморфных мультиграфов с p ребрами.
5. Деревья и их характеристические свойства. Теорема Жордана о центрах дерева.
6. Кодирование плоских корневых деревьев. Бинарные деревья и алгоритм поиска парных скобок. Верхняя оценка числа неизоморфных деревьев с p ребрами.
7. Коды Прюфера и теорема Кэли о числе деревьев с занумерованными вершинами.
8. Двудольние графы. Теорема Кенига о характеристике двудольных графов. Паросочетания и системы различных представителей. Теорема Холла.
9. Потоки в сетях. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе. Алгоритм нахождения максимального потока в сетях с целочисленными пропускными способностями дуг.
10. Теорема Кенига-Эгервари и реберная форма теоремы Менгера как следствия теоремы о максимальном потоке и минимальном разрезе.
11. Булевы функции. Формулы. Дизъюнктивные и конъюнктивные нормальные формы. Полиномы Жегалкина. Разложение булевых функций по переменным. Тождества и возможность их вывода из конечной системы тождеств.
12. Замкнутые классы булевых функций. Базисы и полные системы. Проблема полноты. Предполные классы. Представление о результатах Поста.
13. Схемы из функциональных элементов и их связь с формулами и неветвящимися программами. Асимтотически оптимальная реализация системы всех обобщенных конъюнкций от n переменных. Асимтотически оптимальная реализация системы всех функций от n переменных.
14. Метод Шеннона синтеза схем для булевых функций.
15. Функционал Шеннона и его нижняя оценка.
16. Метод Лупанова и асимптотически точная верхняя оценка функционала Шеннона.
17. Метод Лупанова и сложность умножения булевой матрицы на вектор. Быстрое умножение булевых матриц и матриц над конечными полями.
18. Ограниченно-детерминированные функции и автоматы. Способы задания автоматов. Автоматные схемы из функциональных элементов и задержек. Операции суперопозиции и обратной связи. Существование конечного полного базиса относительно этих операций для функциональной системы ограниченно-детерминированныых функций.
19. Эксперименты с автоматами. Отличимость состояний. Теорема Мура. Минимизация числа состояний автомата.
20. Алфавитное кодирование. Разделимые коды. Префиксные коды и их представление деревьями. Неравенство Крафта-Макмиллана. Существование префиксного кода с заданными длинами слов.
21. Графовый алгоритм распознавания разделимости кода. Сведение проверки разделимости кода к проверке однозначности кодирования множества слов ограниченной длины.
22. Коды с минимальной избыточностью и их построение алгоритмом Хаффмана. Неравенство Шеннона для величины избыточности кода.
23. Самокорректирующиеся двоичные коды. Минимальное расстояние кода. Неравенства Хемминга для мощности максимального кода с заданным расстоянием. Линейные коды. Двойственные коды. Порождающие и проверочные матрицы линейного
кода.
24. Коды Хемминга и их порождающие и проверочные матрицы. Коды Хемминга как совершенные (плотно упакованные) коды. Задача поиска фальшивой моненты.
25. Конечные поля и примитивные элементы в них. Циклические коды и их представление полиномиальными идеалами. Проверочная матрица циклического кода.
26. Коды БЧХ с исправлением заданного количества ошибок.
27. Детерминированные и недетерминированные машины Тьюринга. Пространственная и временная сложность вычисления на машинах Тьюринга. Классы P и NP. Полиномиальная сводимость. NP-полные задачи.
28. NP-полнота задачи выполнимости КНФ и ее интерпретация в виде <<карточного пасьянса>>.
29. NP-полнота задач о тавтологичности ДНФ и эквивалентности схем. NP-полнота общей задачи о покрытии и задачи о покрытии матриц.
30. NP-полнота задач о вершинном покрытии ребер графа, клике, независимом множестве и изоморфизме подграфу.
31. NP-полнота задачи
о 3-выполнимости.
|
|