Анотация

---

Дисциплината „Дискретни структури“ е предназначена за студентите от специалност КСТ. Учебният материал разглежда средства за моделиране на поведението на дискретни системи. Обясняват се теоретични постановки и практически примери, които дават на студентите подходяща основа за представяне и моделиране на дискретни обекти в областта на програмното осигуряване.
В програмата са застъпени различни средства за разпознаване на езици като крайни автомати, мрежи на Петри, машина на Тюринг. По време на семинарните упражнения се решават базови задачи, които демонстрират изложените концепции.
Дисциплината разчита на познанията на студентите от предходни дисциплини:

• Основи на компютърните системи
• Базово програмиране
• Синтез и анализ на алгоритми
• Математика за компютърни науки

Придобитите знания и умения са необходими на студентите в дисциплините „Обектно-ориентирано програмиране“, „Операционни системи“, „Компилатори и интерпретатори“ както и в практическата работа на всеки студент.

Съдържание

---

Тема 1. Основни понятия. Множества. Отношения и функции в множествата
1.1. Теория на множествата
1.2. Операции над множествата
1.3. Свойства на операциите над множества
1.4. Отношения в множествата
1.5. Функции в множествата
Тема 2. Подредени множества и низове. Операции с низове, Регулярни множества и изрази
2.1. Подредени множества
2.2. Операции с низове
2.3. Регулярни множества
2.4. Регулярни изрази
Тема 3. Формални граматики и езици
3.1. Основни понятия
3.2. Формална граматика
3.3. Класификация и йерархия на граматики по Хомски
3.4. Видове продукции
3.5. Бакус-Наур форма за представяне на граматики
3.6. Синтактични графи
Тема 4. Абстрактни автомати
4.1. Изчислимост и разрешимост
4.2. Разпознаване на езици чрез крайни автомати
4.3. Анализ на крайни автомати
4.4. Синтез на крайни автомати
Тема 5. Същност и действие на машината на Тюринг
5.1. Същност на машината на Тюринг
5.2. Съставни части на машината на Тюринг
5.3. Действие на машината на Тюринг
5.4. Изчисляване с машина на Тюринг
5.5. Класификация и йерархия на абстрактните автомати
5.6. Еквивалентност между абстрактни автомати и граматики
Тема 6. Абстрактни автомати и формални граматики
6.1. Класификация и йерархия на абстрактните автомати
6.2. Еквивалентност между абстрактни автомати и граматики
Тема 7. Рекурсивни функции
7.1. Базови функции
7.2. Частично рекурсивни функции
Тема 8. Паралелни системи и процеси
8.1. Паралелизъм – същност
8.2. Теория на мрежите на Петри
8.3. Мрежови езици
8.4. Моделиране на паралелни процеси с мрежи на Петри
Тема 9. Абстрактни информационни структури
9.1. Йерархия на информационните структури
9.2. Представяне на моделите в паметта
Тема 10.Математическа логика
10.1. Предмет на математическата логика
10.2. Препозиционна логика (съждително смятане)
10.3. Предикатна логика
10.4. Метод на резолюцията
10.5. Общ метод на резолюцията