Дискретна математика

Въведение

Първа глава. ЕЛЕМЕНТИ ОТ ТЕОРИЯТА НА МНОЖЕСТВАТА, КОМБИНАТОРИКАТА И ТЕОРИЯТА НА ГРАФИТЕ
1.1. Множества
1.2. Декартово произведение на множества. Вариации, пермутации, комбинации
1.3. Релации
1.4. Функции
1.5. Графи. Основни понятия
1.6. Матрица на съседство. Оптимални пътища
1.7. Дървета

Втора глава. ДВОИЧНИ ФУНКЦИИ
2.1. Основни понятия
2.2. Формули и суперпозиции
2.3. Пълни множества от двоични функции
2.4. Затворени класове
2.5. Двойственост. Самодвойствени функции. Затворен клас S
2.6. Монотонност на двоични функции. Затворен клас М
2.7. Линейни функции. Затворен клас L
2.8. Критерий за пълнота
2.9. Дизюнктивни нормални форми
2.10. Алгоритми за намиране на СДНФ
2.11. Комбинационни схеми

Трета глава. ФОРМАЛНИ ЕЗИЦИ И АВТОМАТИ. КРАЙНИ АВТОМАТИ РАЗПОЗНАВАТЕЛИ И ПРЕОБРАЗУВАТЕЛИ
3.1. Азбуки, думи, формални езици и операции с тях
3.2. Пораждащи граматики
3.3. Свойства на автоматните езици
3.4. Детерминирани крайни автомати. uvw-теорема за крайните автомати
3.5. Недетерминирани крайни автомати. Еквивалентност с детерминираните крайни автомати и с автоматните граматики
3.6. Регулярни изрази. Теорема на Клини
3.7. Минимизация на крайните автомати
3.8. Крайните автомати като преобразуватели. Автомат на Мили и автомат на Мур
3.9. Общи задачи върху крайни автомати и автоматни граматики

Четвърта глава. БЕЗКОНТЕКСТНИ ЕЗИЦИ. НЕДЕТЕРМИНИРАНИ МАГАЗИННИ АВТОМАТИ
4.1. Безконтекстни езици. Синтаксис на езиците за програмиране
4.2. Недетерминирани магазинни автомати
4.3. Синтактичен анализ и синтактични анализатори на безконтекстните езици
4.4. Общи задачи върху безконтекстни езици

Пета глава. МАШИНИ НА ТЮРИНГ
5.1. Машините на Тюринг като разпознаватели и преобразуватели
5.2. Универсална машина на Тюринг
5.3. Неразрешими алгоритмични проблеми
5.4. Изчислителна и описателна сложност на машините на Тюринг

Използвана литература