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:
Asymptotyka. Klasy złożoności obliczeniowej algorytmów.
Algorytmy przeszukiwania grafów i digrafów (BFS, DFS) i ich zastosowania.
Digrafy spójne i silnie spójne. Algorytm wyznaczania komponent silnie spójnych w digrafach.
Sortowanie topologiczne.
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.
Minimalne drzewa rozpinające. Twierdzenia charakteryzujące. Algorytmy (Prim, Kruskal).
Drzewa rozpinające spełniające dodatkowe warunki (np. ograniczona średnica, ograniczony stopień).
Analiza działania i badanie poprawności wybranych algorytmów grafowych.
Rozwiązywanie podanych zagadnień (praktycznych) poprzez wybór (lub zaprojektowanie) odpowiedniego algorytmu i dobór odpowiedniej struktury danych.
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
W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.
Ta strona używa ciasteczek (cookies), dzięki którym nasz serwis może działać lepiej. Korzystając z niniejszej strony, wyrażasz zgodę na ich używanie. Dowiedz się więcej.