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

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