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



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

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

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

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


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

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



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

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


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


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

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


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

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

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

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

Габрово

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 г.
Каталог: docs -> Bachelor -> II%20Kurs -> Sem%20IV -> Fakultativni
Sem%20IV -> Лекция №2 алгоритмично-програмни конструкции видове алгоритми
Sem%20IV -> Дървета Цел
Sem%20IV -> Програма по дисциплината : "анализ и синтез на логически схеми" включена в учебния план на специалността: " Компютърни системи и технологии"
Sem%20IV -> Евристически алгоритми
Sem%20IV -> Лекция №4 с о р т и р а н е и с м е с в а н е същност на сортирането
Sem%20IV -> Цел: Запознаване с метода за създаване на ефективно по – рекурсия. Създаване и използване на рекурсивни функции при решаване на сложни задачи. Теоретична част
Sem%20IV -> Лекция №3 Сложност на алгоритмите
Fakultativni -> Eлектротехника и електроника
Sem%20IV -> Задача за "Ход на коня". Задача 1: Ход на коня


Сподели с приятели:




©obuch.info 2024
отнасят до администрацията

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