КОНСПЕКТ
по Дискретна математика
за специалността математика

(1999/2000 уч. година)

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