ФАКУЛТЕТ ПО МАТЕМАТИКА И ИНФОРМАТИКА
Пловдивски университет "Паисий Хилендарски"
начало / обучение / специалности / математика и информатика / уч. план (бакалавър) / дискретна математика
текуща информация 
документи 
обучение 
учебен график 
прием 
студенти 
структура 
научна дейност 
за факултета 

Учебна програма
Дискретна математика
 Специалност  Mатематика и информатика (бакалавър)
 Форма на оценяване   Изпит
 Дисциплината се води от  Катедра Реален анaлиз
 Анотация 
     Материалът е подреден в пет раздела. В раздел “Булеви функции” се доказват свойства, които не се разглеждат в други информационни дисциплини. Основен аспект е доказване на критерия за пълнота на Е.Пост. В раздел “Формални езици и пораждащи граматики” се въвеждат основни понятия от математическата лингвистика. Основна тежест на целия материал пада върху раздела “Автоматични езици”. Доказват се повечето техни свойства. Показва се еквивалентност между тях и езиците, разпознавани от детерминанти, съответно недетерминирани крайни автомати. Доказват се теоремата на С.Клини и теоремата за минимизация. Подробно се разглеждат и преобразувателите на Мили и Мур. В раздел “Безконтекстни езици” се разглежда тяхната еквивалентност с езиците, разпознавани от недетерминираните магазинни автомати. Доказани са повечето техни свойства. В последния раздел се разглеждат машини на Тюринг и неразрешими алгоритмични проблеми.
 Съдържание  

1. Множества. Комбинаторика. Релации и функции. Графи – основни понятия, матрици на свързаност. Дървета. Двоични функции – основни понятия. Формули и суперпозиции. Пълни множества от двоични функции. Теорема на Бул. Затворени класове. Класове Т0 и Т1. Двойнственост. Самодвойнствени функции. Затворен клас S. Монотонност на двоични функции. Затворен клас М. Линейни функции. Затворен клас L. Критерий за пълнота на Пост. Минимизация на двоични функции. Алгоритми за минимизация.
2. Азбуки, думи, формални езици и операции с тях. Пораждащи граматики. Йерархия на Чомски. Свойства на автоматичните езици. Детерминирани крайни автомати (ДКА). UVW-теорема за крайните автомати. Недетерминирани крайни автомати. Еквивалентност с ДКА и автоматните граматики. Регулярни изрази. Теорема на Клини. Минимизация на крайните автомати. Крайните автомати като преобразуватели. Автомат на Мили и автомат на Мур.
3. Безконтекстни езици. Синтаксис на езиците за програмиране. Недетерминирани магазинни автомати. Синтактичен анализ и синтактични анализатори за програмиране. Машини на Тюринг.