|
|
|
|
Новости
|
|
|
|
Билеты по дискретной математике.
(новость от 6 июня 2007г.)
Всем привет. Позади первый экзамен – программирование. Но расслабляться не стоит, т.к. совсем скоро, а если точнее 10 июня, состоится экзамен по Дискретной математике. И специально для людей, у которых до сих пор нет билетов, я публикую их на этом сайте:
Вопросы по курсу "Дискретная математика".
I. Элементы комбинаторики.
1. Понятие r-выборки. Выборки упорядоченные и неупорядоченные, с повторением и без повторения. Число упорядоченных выборок с повторением и без повторения.
2. Типы выборок. Число неупорядоченных выборок с повторением и без повторения.
3. Разбиение множества на "к" подмножеств. Перестановки с повторением.
4. Полиномиальная формула.
5. Формула бинома и свойства биномиальных коэффициентов.
6. Метод включения и исключения.
7. Задача о беспорядках.
8. Задача о распределении. Распределение неразличимых шаров.
9. Задача о распределении. Распределение различимых шаров.
10. Метод рекуррентных соотношений. Общий подход.
11. Формула обобщенного арифметического треугольника. Пример использования.
II. Булевы функции.
1. Понятие булевой функции. Простейшие свойства булевых функций.
2. Булевы функции одного и двух аргументов (названия, обозначения, таблицы истинности).
3. Булевы функции двух аргументов. Основные свойства.
4. Разложение булевых функций по переменным (теорема о разложении, два следствия). Совершенная ДНФ.
5. Разложение булевых функций по переменным. Совершенная КНФ.
6. Представления булевых функций полиномами (теорема Жегалкина, лемма о единственности полинома).
7. Замкнутые классы булевых функций (определение, свойства, замыкания, примеры).
8. Классы булевых функций Т0, Т1. Их функциональная замкнутость.
9. Класс самодвойственных функций. Его функциональная замкнутость.
10. Лемма о несамодвойственной функции.
11. Класс монотонных функций. Его функциональная замкнутость.
12. Лемма о немонотонной функции.
13. Класс линейных функций. Лемма о нелинейной функции.
14. Полные системы булевых функций. Примеры. Теорема о полноте системы булевых функций. Теорема Поста. Классы булевых функций полные в слабом смысле, предполные классы.
15. Задачи минимизации булевых функций в классах ДНФ и КНФ (основные определения).
16. Минимизация нормальных форм картами Карнау. Карты для 2, 3, 4-х переменных.
17. Метод Квайна минимизации булевых функций.
18. Дискретные устройства без памяти. Задачи анализа и синтеза схем. Примеры.
III. Автоматы.
1. Алфавитные и автоматные отображения. Основные понятия и определения.
2. Реализация автоматных отображений автоматами. Способы задания автоматов. Автоматы Мили и Мура.
3. Минимизация полных автоматов методом Мили. Метод Шоломова.
4. Методы минимизации частичных автоматов. Метод Шоломова, Т- алгоритм.
5. Кодирование сигналов. Схема автомата. Элемент единичной задержки. Пример.
6. Синтез конечных автоматов. Пример.
7. Задача о дешифрирующем устройстве.
8. Представление событий в автоматах. Алгебра регулярных событий.
9. Детерминизация источников и синтез автоматов.
IV. Теория графов.
1. Основные определения теории графов. Теорема о степенях. Частные виды графов.
2. Построение графа с заданным набором степеней вершин (теорема, алгоритм).
3. Связность, сильная связность. Лемма о связности. Теорема о связном графе.
4. Расстояния в графе. Волновой метод для определения расстояния.
5. Метод редукции индексов для определения кратчайших расстояний в графе.
6. Эйлеровы цепи и циклы. Теоремы существования. Алгоритм Флери.
7. Двойной Эйлеров цикл. Теорема существования. Правило Терри.
8. Гамильтоновы цепи и циклы. Теорема Дирака.
9. Теорема о гамильтоновом пути в полном орграфе. Алгоритм построения.
10. Деревья. Теорема об эквивалентных определениях дерева. Задача построения дерева наименьшего веса.
11. Ориентированные деревья. Бинарные деревья. Алгоритм обхода деревьев.
12. Основные числа теории графов. Число внутренней и внешней устойчивости. Ядро графа.
13. Цикломатическое число графа. Лемма об этом числе.
14. Хроматическое число графа. Теорема Кенинга. Теорема Брукса.
15. Транспортные сети, потоки, разрезы. Теорема Форда-Фалкерсона.
16. Алгоритм построения максимального потока и критического разреза в транспортной сети.
17. Графы плоские и планарные. Две леммы о неплоских графах. Теорема Понтрягина-Куратовского о плоских графах.
18. Формула Эйлера для связного планарного графа. Следствие.
19. Теорема о пяти красках для связного планарного графа. Лемма.
Скачать>>>
|
|
|
|