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