SylabUZ

Wygeneruj PDF dla tej strony

Algorytmy grafowe - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Algorytmy grafowe
Kod przedmiotu 11.0-WK-IDP-AG-W-S14_pNadGenBY6PH
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Inżynieria danych
Profil ogólnoakademicki
Rodzaj studiów pierwszego stopnia z tyt. inżyniera
Semestr rozpoczęcia semestr zimowy 2017/2018
Informacje o przedmiocie
Semestr 4
Liczba punktów ECTS do zdobycia 6
Typ przedmiotu obieralny
Język nauczania polski
Sylabus opracował
  • dr hab. Ewa Drgas-Burchardt, prof. UZ
  • dr Anna Fiedorowicz
Formy zajęć
Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia
Wykład 30 2 - - Egzamin
Laboratorium 30 2 - - Zaliczenie na ocenę

Cel przedmiotu

Zapoznanie studentów z podstawowymi algorytmami grafowymi i sieciowymi, ze szczególnym uwzględnieniem możliwości wykorzystania tych algorytmów do rozwiązywania zagadnień praktycznych. Zajęcia na laboratorium będą polegały na analizie, badaniu poprawności i implementacji poznanych algorytmów oraz ich zastosowaniu w problemach praktycznych.

Wymagania wstępne

Podstawy programowania. Wprowadzenie do teorii grafów.

Zakres tematyczny

Wykład:

  1. Asymptotyka. Klasy złożoności obliczeniowej algorytmów.
  2. Algorytmy przeszukiwania grafów i digrafów (BFS, DFS) i ich zastosowania.
  3. Digrafy spójne i silnie spójne. Algorytm wyznaczania komponent silnie spójnych w digrafach.
  4. Sortowanie topologiczne.
  5. Zagadnienie najkrótszych ścieżek. Najkrótsze ścieżki w sieciach (sieci o nieujemnych wagach, bez cykli o ujemnej wadze). Algorytmy (Dijkstra, Bellman – Ford).  Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków. Algorytm Floyd-Warshall.
  6. Minimalne drzewa rozpinające. Twierdzenia charakteryzujące. Algorytmy (Prim, Kruskal).
  7. Drzewa rozpinające spełniające dodatkowe warunki (np. ograniczona średnica, ograniczony stopień).
  8. Przepływy w sieciach.
  9. Grafy Eulera i Hamiltona.
  10. Problem komiwojażera (TSP), wybrane heurystyki.
  11. Kolorowanie grafów. Wybrane algorytmy kolorowania.

Laboratorium:

  1. Analiza działania i badanie poprawności wybranych algorytmów grafowych.
  2. Rozwiązywanie podanych zagadnień (praktycznych) poprzez wybór (lub zaprojektowanie) odpowiedniego algorytmu i dobór odpowiedniej struktury danych.
  3. Implementacja kilku wybranych algorytmów grafowych w języku programowania. Napisanie i przetestowanie odpowiednich programów oraz przygotowanie dokumentacji.

Metody kształcenia

Wykład konwersatoryjny. Ćwiczenia laboratoryjne w pracowni komputerowej.

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu Symbole efektów Metody weryfikacji Forma zajęć

Warunki zaliczenia

Wykład: egzamin pisemny.

Laboratorium: na ocenę składają się wyniki osiągnięte na kolokwiach (z zadaniami o zróżnicowanym stopniu trudności) oraz ocena projektu polegającego na implementacji wybranego algorytmu (grafowego lub sieciowego) i przygotowaniu dokumentacji (w formie sprawozdania).

Na ocenę z przedmiotu składa się ocena z laboratorium (50%) oraz ocena z egzaminu pisemnego (50%). Warunkiem zaliczenia przedmiotu jest pozytywna ocena z laboratorium i egzaminu.

Literatura podstawowa

  1. W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.
  2. K.A. Ross, Ch.R.B. Wright, Matematyka dyskretna, PWN, Warszawa, 1996.
  3. D. Jungnickel, Graphs, Networks and Algorithms, Springer-Verlag, Berlin Heidelberg, 2008
  4. E. M. Reingold, J. Deo, N. Nievergelt, Algorytmy kombinatoryczne, PWN, Warszawa, 1985.
  5. M. Sysło, N. Deo, J. Kowalik, Algorytmy optymalizacji dyskretnej z programami w języku Pascal, PWN, Warszawa, 1993.
  6. J. Błażewicz, Złożoność obliczeniowa problemów kombinatorycznych, WNT, Warszawa, 1988.

Literatura uzupełniająca

  1. M. Kubale (Redaktor): Optymalizacja dyskretna – modele i metody kolorowania grafów, WNT, 2002.
  2. A.V. Aho, J.E. Hopcroft, J.D. Ullman, Projektowanie i analiza algorytmów komputerowych, Helion, 2003.
  3. B. Jankowski, Grafy – Algorytmy w Pascalu, MIKOM, 2003.
  4. P. Wróblewski, Algorytmy, struktury danych i techniki programowania, Helion, 2003.

Uwagi


Zmodyfikowane przez dr Robert Dylewski, prof. UZ (ostatnia modyfikacja: 09-04-2017 16:27)