КОНСПЕКТ ПО ДИСКРЕТНА МАТЕМАТИКА
за студентите от II курс приложна математика, I поток,
които ще имат изпит през 2000 г.

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