Електротехника и електроника



Дата31.12.2017
Размер83.18 Kb.
МИНИСТЕРСТВО НА ОБРАЗОВАНИЕТО И НАУКАТА

ТЕХНИЧЕСКИ УНИВЕРСИТЕТ – ГАБРОВО

ФАКУЛТЕТ “ЕЛЕКТРОТЕХНИКА И ЕЛЕКТРОНИКА”

УТВЪРЖДАВАМ!


Декан:...............................

/доц. д-р Д. Петров/



У Ч Е Б Н А П Р О Г Р А М А

По факултативната дисциплината


ДИСКРЕТНИ СТРУКТУРИ


Включена в учебния план на специалността

КОМПЮТЪРНИ СИСТЕМИ И ТЕХНОЛОГИИ


Образователно-квалификационна степен: БАКАЛАВЪР

Професионална квалификация: КОМПЮТЪРЕН ИНЖЕНЕР

Професионално направление: КОМУНИКАЦИОННА И КОМПЮТЪРНА ТЕХНИКА

Катедра: МАТЕМАТИКА

Габрово

2003 г.


I. ИЗВАДКА ОТ УЧЕБНИЯ ПЛАН




Вид на занятието

Семестър

Хорариум



А. Лекции

IV

30



Б. Семинарни упр.

IV

15



Б. Лабораторни упр.

IV

15



Изпит

IV






II. А Н О Т А Ц И Я

Предмет на дисциплината са моделирането на компютърни системи и мрежи с ориентирани и неориентирани графи и дървета.

Целта е студентите да придобият знания и умения по едни от най-важните раздели на дискретните структури и алгоритмите за изследването им.

Включването в учебната програма на лабораторни упражнения осигурява възможност студентите да повишат владеенето на език за програмиране и да довеждат разглежданите на лекции дискретни структури и алгоритми до практически програмни реализации.




III. СЪДЪРЖАНИЕ НА УЧЕБНАТА ПРОГРАМА





Теми на лекциите и упражненията

А. Лекции






Тема

Л

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



IV. ЛИТЕРАТУРА

А. Основна

1. Л. Амерал, “Алгоритми и структури от данни в С++”, ИК СОФТЕХ, София, 2001.
2. С. Н. Капралов, “Основни алгоритми върху графи”, учебно пособие, 2002.
Б. Допълнителна
3. Ф.А. Новиков, “Дискретная математика для программистов”, Питер, С. Петербург, 2001.

СЪСТАВИЛИ: 1...........................

/ доц. д-р Стоян Капралов/
2...........................

/ гл. ас. Петър Петров/


3...........................

/ гл.ас. Елена Методиева/


Учебната програма е обсъдена на заседание на КС на катедра “Математика” и е приета с протокол № 8 / 10.04.2003 г.
Р-Л КАТЕДРА МАТЕМАТИКА:....................................

/ доц. д-р Стоян Н. Капралов /


Учебната програма е обсъдена на заседание на КС на катедра “Компютърни системи и технологии” и е приета с протокол № / 2003 г.
Р-Л КАТЕДРА КСТ:....................................

/ доц. д-р инж. Любен Иванов Цеков /


Учебната програма е обсъдена на заседание на ФС на ф-т “ЕЕ” и е приета с протокол №..../.................2003 г.


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница