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.