МИНИСТЕРСТВО НА ОБРАЗОВАНИЕТО И НАУКАТА
ТЕХНИЧЕСКИ УНИВЕРСИТЕТ – ГАБРОВО
ФАКУЛТЕТ “ЕЛЕКТРОТЕХНИКА И ЕЛЕКТРОНИКА”
УТВЪРЖДАВАМ!
Декан:...............................
/доц. д-р Д. Петров/
У Ч Е Б Н А П Р О Г Р А М А
По факултативната дисциплината
ДИСКРЕТНИ СТРУКТУРИ
Включена в учебния план на специалността
КОМПЮТЪРНИ СИСТЕМИ И ТЕХНОЛОГИИ
Образователно-квалификационна степен: БАКАЛАВЪР
Професионална квалификация: КОМПЮТЪРЕН ИНЖЕНЕР
Професионално направление: КОМУНИКАЦИОННА И КОМПЮТЪРНА ТЕХНИКА
Катедра: МАТЕМАТИКА
Габрово
2003 г.
I. ИЗВАДКА ОТ УЧЕБНИЯ ПЛАН
-
|
Вид на занятието
|
Семестър
|
Хорариум
| -
|
А. Лекции
|
IV
|
30
| -
|
Б. Семинарни упр.
|
IV
|
15
| -
|
Б. Лабораторни упр.
|
IV
|
15
| -
|
Изпит
|
IV
|
|
II. А Н О Т А Ц И Я
Предмет на дисциплината са моделирането на компютърни системи и мрежи с ориентирани и неориентирани графи и дървета.
Целта е студентите да придобият знания и умения по едни от най-важните раздели на дискретните структури и алгоритмите за изследването им.
Включването в учебната програма на лабораторни упражнения осигурява възможност студентите да повишат владеенето на език за програмиране и да довеждат разглежданите на лекции дискретни структури и алгоритми до практически програмни реализации.
Теми на лекциите и упражненията
|
А. Лекции
|
№
|
Тема
|
Л
|
1.
|
Моделиране с графи.
Класически примери на моделиране с графи. Основни дефиниции. Представяне на графи.
|
2
|
2.
| Обхождане на графи.
Търсене в дълбочина в ориентирани графи. Базов алгоритъм. Програмна реализация. Приложения. Откриване на цикли.
|
3
|
3.
| Мрежа на дейностите.
Топологично сортиране. Постановка на задачата.
Условия за съществуване на решение.
|
3
|
4.
| Метод на критичния път.
Най-ранно и най-късно време на започване и завършване на дейност. Критичен път.
|
3
|
5.
| Силно свързани компоненти.
Постановка на задачата. Моделиране на реална система.
Приложение на търсене в дълбочина за намиране на силно свързаните компоненти.
|
2
|
6.
| Търсене в ширина.
Алгоритъм. Структури от данни. Програмна реализация.
|
2
|
7.
| Приоритетни опашки.
Пирамиди.
Реализация на приоритетна опашка посредством пирамида.
|
3
|
8.
| Най-къси пътища в графи.
Алгоритъм на Дейкстра за най-къси пътища в графи с неотрицателни дължини на ребрата.
Ефективна реализация с приоритетна опашка.
|
3
|
9.
| Най-къси пътища в графи с отрицателни ребра. Алгоритъм на Форд-Белман. Алгоритъм на Флойд.
Откриване на цикли с отрицателна дължина.
|
3
|
10.
| Минимални покриващи дървета. Алгоритъм на Прим. Алгоритъм на Крускал. |
3
|
11.
| Структури от данни за представяне на множества.
Ефективна реализация на Алгоритъма на Крускал.
|
3
|
| ОБЩО |
30
|
№
|
Тема
|
СУ
|
1.
|
Моделиране с графи.
Класически примери на моделиране с графи. Основни дефиниции. Представяне на графи.
|
1
|
2.
| Обхождане на графи.
Търсене в дълбочина в ориентирани графи. Базов алгоритъм. Програмна реализация. Приложения. Откриване на цикли.
|
1
|
3.
| Мрежа на дейностите.
Топологично сортиране. Постановка на задачата.
Условия за съществуване на решение.
|
1
|
4.
| Метод на критичния път.
Най-ранно и най-късно време на започване и завършване на дейност. Критичен път.
|
1
|
5.
| Силно свързани компоненти.
Постановка на задачата. Моделиране на реална система.
Приложение на търсене в дълбочина за намиране на силно свързаните компоненти.
|
1
|
6.
| Търсене в ширина.
Алгоритъм. Структури от данни. Програмна реализация.
|
1
|
7.
| Приоритетни опашки.
Пирамиди.
Реализация на приоритетна опашка посредством пирамида.
|
2
|
8.
| Най-къси пътища в графи.
Алгоритъм на Дейкстра за най-къси пътища в графи с неотрицателни дължини на ребрата.
Ефективна реализация с приоритетна опашка.
|
2
|
9.
| Най-къси пътища в графи с отрицателни ребра. Алгоритъм на Форд-Белман. Алгоритъм на Флойд.
Откриване на цикли с отрицателна дължина.
|
2
|
10.
| Минимални покриващи дървета. Алгоритъм на Прим. Алгоритъм на Крускал. |
2
|
11.
| Структури от данни за представяне на множества.
Ефективна реализация на Алгоритъма на Крускал.
|
1
|
| ОБЩО |
15
|
В. Лабораторни упражнения
|
№
|
Тема
|
ЛУ
|
1.
|
Моделиране с графи.
Класически примери на моделиране с графи. Основни дефиниции. Представяне на графи.
|
1
|
2.
| Обхождане на графи.
Търсене в дълбочина в ориентирани графи. Базов алгоритъм. Програмна реализация. Приложения. Откриване на цикли.
|
2
|
3.
| Мрежа на дейностите.
Топологично сортиране. Постановка на задачата.
Условия за съществуване на решение.
|
1
|
4.
| Метод на критичния път.
Най-ранно и най-късно време на започване и завършване на дейност. Критичен път.
|
1
|
5.
| Силно свързани компоненти.
Постановка на задачата. Моделиране на реална система.
Приложение на търсене в дълбочина за намиране на силно свързаните компоненти.
|
1
|
6.
| Търсене в ширина.
Алгоритъм. Структури от данни. Програмна реализация.
|
2
|
7.
| Приоритетни опашки.
Пирамиди.
Реализация на приоритетна опашка посредством пирамида.
|
2
|
8.
| Най-къси пътища в графи.
Алгоритъм на Дейкстра за най-къси пътища в графи с неотрицателни дължини на ребрата.
Ефективна реализация с приоритетна опашка.
|
2
|
9.
| Най-къси пътища в графи с отрицателни ребра. Алгоритъм на Форд-Белман. Алгоритъм на Флойд.
Откриване на цикли с отрицателна дължина.
|
1
|
10.
| Минимални покриващи дървета. Алгоритъм на Прим. Алгоритъм на Крускал. |
1
|
11.
| Структури от данни за представяне на множества.
Ефективна реализация на Алгоритъма на Крускал.
|
1
|
| ОБЩО |
15
|
А. Основна
1. Л. Амерал, “Алгоритми и структури от данни в С++”, ИК СОФТЕХ, София, 2001.
2. С. Н. Капралов, “Основни алгоритми върху графи”, учебно пособие, 2002.
Б. Допълнителна
3. Ф.А. Новиков, “Дискретная математика для программистов”, Питер, С. Петербург, 2001.
СЪСТАВИЛИ: 1...........................
/ доц. д-р Стоян Капралов/
2...........................
/ гл. ас. Петър Петров/
3...........................
/ гл.ас. Елена Методиева/
Учебната програма е обсъдена на заседание на КС на катедра “Математика” и е приета с протокол № 8 / 10.04.2003 г.
Р-Л КАТЕДРА МАТЕМАТИКА:....................................
/ доц. д-р Стоян Н. Капралов /
Учебната програма е обсъдена на заседание на КС на катедра “Компютърни системи и технологии” и е приета с протокол № / 2003 г.
Р-Л КАТЕДРА КСТ:....................................
/ доц. д-р инж. Любен Иванов Цеков /
Учебната програма е обсъдена на заседание на ФС на ф-т “ЕЕ” и е приета с протокол №..../.................2003 г.
Сподели с приятели: |