CSTB547 Дискретни структури
Анотация:
Този едносеместриален курс е въведение в общите дискретни структури, използвани като математически модел в различни области на приложната математика и компютърните науки: операции и релации в крайни множества и представянето им като структури данни, графи и връзки между графи, бинарни релации и булеви матриици, сложност на алгоритмите, комбинаторен анализ (генериране на комбинаторни конфигурации, рекурентни уравнения, аналитични и логически методи и пр.). Включени са и някои "класически раздели" като крайни автомати, многозначна логика, булеви функции.
Преподавател(и):
доц. Георги Бижев д-р
Описание на курса:
Компетенции:
След завършване на курса студентите трябва да знаят основни понятия от някои важни области, даващи фундамента на компютърните науки и да могат да прилагат методи и ефективни алгоритми при решаване на комбинаторни проблеми.
В края на обучението си студентът ще:
- определя основните понятия, величини, показатели в теорията и ще може да - избира адекватен дискретен модел;
- познава методите и средствата на апарата и може да го използва.
Предварителни изисквания:
Форми на провеждане:
Редовен
Учебни форми:
Лекция
Език, на който се води курса:
Български
Теми, които се разглеждат в курса:
Логика. Твърдения. Квантори.
Множества. Релации и функции. Графи.
Крайни булеви алгебри и булеви пръстени.
Връзки между булеви матрици и графи.
Релации на наредба и еквивалентност.
Алгоритми. Сложност на алгоритмите.
Комбинаторен анализ.
Пермутации и комбинации. Пораждащи функции.
Рекурентни уравнения.
Принцип на включването и изключването.
Крайни автомати Автоматите като динамични системи.
Езици и граматики. Връзка между езици и автомати.
Комбинационни схеми и k-значна логика.
Основни понятия.функционално пълни системи.
Минимизация на булеви функции.Синтез на комбинационни схееми.
Литература по темите:
1. К. Манев, Увод в дискретната математика, КЛМН, четвърто издание, София, 2005.
2. Денев, Й. Д. ,Щраков, С. В., Дискретна математика. Югозападен университет, Благоевград, 1995.
3. Денев Й., Павлов, Р., Дерметрович Я., Дискретна математика, "Наука и изкуство", С., 1984.
4. Манна 3., Математическа теория на информатиката, "Наука и изкуство", С.,1983.
5. Rosen, K.H.,DISCRETE MATHEMATICS AND ITS APPLICATIONS, SIXTH EDITION,
McGraw-Hill,New York,2007.
Средства за оценяване:
Провеждат се 2 контролни работи.
Използва се и продуктът на компютърната алгебра Maple.