Въведение в дискретната математика

Увод

1. Теория на множествата, графи, релации и функции
1.1. Основи на теорията на множествата
1.2. Графи и дървета
1.3. Релации и функции
1.4. Множества от числа и мощност на множества
1.5. Техники на дефиниране и доказване
1.6. Упражнения и решения

2. Булеви функции
2.1. Основни понятия
2.2. Затворени множества от булеви функции
2.3. Критерий за пълнота на Пост (Post)
2.4. Предпълни множества
2.5. Комбинационни схеми
2.6. Минимизация на дизюнктивни нормални форми
2.7. Упражнения и решения

3. Формални езици и пораждащи граматики
3.1. Формални езици
3.2. Пораждащи граматики
3.3. Йерархия на Чомски (Chomsky)
3.4. Регулярни езици
3.5. Регулярни изрази
3.6. Безконтекстни езици
3.7. Контекстни езици
3.8. Езици от общ тип
3.9. Упражнения и решения

4. Абстрактни машини без външна памет
4.1. Основни концепции - разпознаватели и преобразуватели
4.2. Детерминирани крайни автомати
4.3. Недетерминирани крайни автомати
4.4. Крайни автомати, регулярни изрази и регулярни езици
4.5. Преобразуватели (трансдуктори)
4.6. Упражнения и решения

5. Абстрактни машини с външна памет
5.1. Крайни автомати с един стек
5.2. Крайни автомати с два или повече стека
5.3. Представяне с блок схеми
5.4. Машини на Тюринг (Turing)
5.5. Формални езици и абстрактни разпознаватели
5.6. Упражнения и решения

6. Машините на Тюринг и Пост като изчислители и алгоритми
6.1. Машината на Тюринг като изчислител
6.2. Машина на Пост (Post)
6.3. Универсална машина на Тюринг
6.4. Тезис на Чърч (Church)
6.5. Разрешимост на някои класове от да/не проблеми
6.6. Сложност (комплексност) на алгоритми
6.7. Упражнения и решения

Литература