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