КОНСПЕКТ
по дискретна математика
за II курс приложна математика, II поток
2001/2002 уч. година

  1. Множества и действия с тях. Крайни множества.
  2. Функции. Равномощност на множества. Изброими множества.
  3. Наредени n-ки. Релации. Релации на еквивалентност. Факторизация.
  4. Двоични функции.
  5. Изразимост на функция чрез дадени функции.
  6. Теореми на Бул и Жегалкин.
  7. Пълни множества и базиси от двоични функции. Класове на Пост.
  8. Критерий на Пост за пълнота - доказателство на необходимостта.
  9. Критерий на Пост за пълнота - доказателство на достатъчността.
  10. Графи и дървета.
  11. Думи и езици над дадена азбука. Регулярни езици над дадена азбука.
  12. Крайни автомати. Граф и език на краен автомат. Достижимост на едно състояние от друго чрез дадена дума.
  13. Детерминирани крайни автомати. Тотални детерминирани крайни автомати. Функция на преходите на детерминиран краен автомат. Премахване на недостижимите състояния на тотален детерминиран автомат.
  14. Детерминизация на краен автомат.
  15. Автоматни езици. Затвореност на класа на автоматните езици относно допълнение, обединение и сечение.
  16. Затвореност на класа на автоматните езици относно конкатенация.
  17. Затвореност на класа на автоматните езици относно итерация.
  18. Отъждествяване на еквивалентни състояния на тотален детерминиран краен автомат.
  19. Намиране на минимален автомат, еквивалентен на даден тотален детерминиран автомат.
  20. Единственост с точност до изоморфизъм на минималния автомат, еквивалентен на даден тотален детерминиран автомат.
  21. Лема за разрастване за автоматните езици.
  22. Формални граматики и техните езици. Нескъсяващи граматики.
  23. Безконтекстни граматики и безконтекстни езици.
  24. Затвореност на класа на безконтекстните езици относно обединение, конкатенация и итерация.
  25. Лема за разрастване за безконтекстните езици.