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