Cel kształcenia i wykaz literatury

Główny cel kształcenia: Zasadniczym celem kształcenia w ramach tego przedmiotu jest zapoznanie studentów z wybranymi algorytmami optymalizacji dyskretnej w grafach i sieciach.

Ogólne informacje o zajęciach: Sieci są to grafy ważone, zazwyczaj skierowane, używane do modelowania różnych procesów w technice, zjawisk w przyrodzie itp. Algorytmy optymalizacyjne na takich sieciach pozwalają rozwiązywać problemy minimalizacji strat albo maksymalizacji zysków, wydajności itp. Wśród problemów praktycznych, rozwiązywanych tymi algorytmami, ważne miejsce zajmują: zagadnienie najkrótszych dróg między wierzchołkami sieci, zagadnienie najtańszego cyklu odwiedzającego wszystkie wierzchołki, problem maksymalnego przepływu jakiegoś medium (np. danych, energii, ale także pojazdów, towarów) od źródła do ujścia, problem przepływu o minimalnym koszcie itp. W przypadku pojazdu elektrycznego kluczowe znaczenie ma maksymalny zasięg, czyli odległość, jaką może on pokonać na jednym ładowaniu. Algorytmy optymalizacji dyskretnej pozwalają maksymalizować ten zasięg, wybierając optymalną, np. ze względu na zużycie paliwa, trasę. Pomagają również zminimalizować koszt przesłania pewnej ilości towarów z punktu A do punktu B w sieci, której łuki są obciążone kosztami.

Materiały dydaktyczne: Biblioteka kombinatoryczno-grafowa, dostępna po zalogowaniu

Inne: https://networkx.org .... https://www.sagemath.org .... https://www.mathworks.com....https://maxima.sourceforge.io

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	Maciej M. Sysło, Narshing Deo, Janusz S. Kowalik	Algorytmy optymalizacji dyskretnej	Wydawnictwo Naukowe PWN.	1999
2	T.H.Cormen, Ch. E. Leiserson, Ronald L. Rivest	Wprowadzenie do Algorytmw	WNT.	1997
3	Jacek Wojciechowski, Krzysztof Pieńkosz,	Grafy i Sieci	Wydawnictwo Naukowe PWN.	2013

Literatura wykorzystywana podczas zajęć ćwiczeniowych/laboratoryjnych/innych

1

Kenneth A. Ross, Charles R.B. Wright

Matematyka Dyskretna

Wydawnictwo naukowe PWN, Warszawa.

2005

Literatura do samodzielnego studiowania

1

Marek Libura, Jarosław Sikorski

Wykłady z matematyki dyskretnej, cz. II: Teoria grafów

Skrypt Wyższej Szkoły Informatyki i Zarządzania, Warszawa.

2003

Wymagania wstępne w kategorii wiedzy/umiejętności/kompetencji społecznych

Wymagania formalne: Student powinien znać podstawowe zagadnienia z zakresu teorii grafów, systemów informatycznych oraz być zarejestrowany na dany semestr studiów.

Wymagania wstępne w kategorii Wiedzy: Student powinien mieć wiedzę z zakresu matematyki i systemów informatycznych, wykorzystywaną do formułowania i rozwiązywania prostych zadań inżynierskich związanych z informatyką.

Wymagania wstępne w kategorii Umiejętności: Student powinien umieć stosować wiedzę matematyczną do sformułowania i rozwiązywania prostych zadań informatycznych.

Wymagania wstępne w kategorii Kompetencji społecznych: Student powinien umieć pracować indywidualnie i w zespole, prezentować wyniki pracy na forum grupy i w formie pisemnej.

Efekty kształcenia dla zajęć

MEK	Student, który zaliczył zajęcia	Formy zajęć/metody dydaktyczne prowadzące do osiągnięcia danego efektu kształcenia	Metody weryfikacji każdego z wymienionych efektów kształcenia	Związki z KEK	Związki z PRK
01	zna podstawowe algorytmy znajdowania najkrótszych ścieżek w grafie skierowanym	wykład, laboratorium	kolokwium, raport pisemny	K_W01++ K_W09++ K_U01+ K_U12+	P6S_UU P6S_UW P6S_WG
02	zna podstawowe algorytmy wyznaczania najtańszego cyklu Hamiltona w grafie skierowanym	wykład, laboratorium	kolokwium, raport pisemny	K_W01++ K_W09+++ K_U01+ K_U12+	P6S_UU P6S_UW P6S_WG
03	potrafi rozwiązać problem maksymalnego przepływu w sieci przepływowej	wykład, laboratorium	kolokwium, raport pisemny	K_W01++ K_W09++ K_U01+ K_U12+	P6S_UU P6S_UW P6S_WG
04	potrafi rozwiązać problem najtańszego przepływu w sieci przepływowej	wykład, laboratorium	kolokwium, raport pisemny	K_W01++ K_W09++ K_U01+ K_U12+	P6S_UU P6S_UW P6S_WG

Uwaga: W zależności od sytuacji epidemicznej, jeżeli nie będzie możliwości weryfikacji osiągniętych efektów uczenia się określonych w programie studiów w sposób stacjonarny w szczególności zaliczenia i egzaminy kończące określone zajęcia będą mogły się odbywać przy użyciu środków komunikacji elektronicznej (w sposób zdalny).

Treści kształcenia dla zajęć

Sem.	TK	Treści kształcenia	Realizowane na	MEK
4	TK01	Zapoznanie z kartą modułu. Podanie zasad zaliczenia przedmiotu. Podstawowe definicje i pojęcia teorii grafów: wierzchołki, krawędzie, łuki. Podział grafów: grafy nieskierowane i skierowane, nieważone i ważone. Macierzowy opisów grafów: macierz sąsiedztw, incydencji, wag itp. Listy sąsiedztw. Drogi (ścieżki) oraz cykle w grafach.	W1, L1	MEK01
4	TK02	Algorytm Dijkstry wyznaczania najkrótszych dróg z wybranego wierzchołka grafu skierowanego z wagami do wszystkich jego pozostałych wierzchołków. Przedstawienie problemu szukania najkrótszej ścieżki w grafie ważonym między wybraną parą wierzchołków jako problemu programowania liniowego.	W2, L2	MEK01
4	TK03	Algorytm Warshalla wyznaczania najkrótszych ścieżek między wszystkimi parami wierzchołków w grafie skierowanym z wagami.	W3, L3	MEK01
4	TK04	Szukanie najtańszego cyklu Hamiltona w grafie skierowanym za pomocą metody transwersal, czyli jednocyklowych permutacji oraz za pomocą zmodyfikowanego algorytmu węgierskiego (www.hungarianalgorithm.com).	W4, L4	MEK02
4	TK05	Zastosowanie algorytmu podziału i ograniczeń (ang. branch and bound) do wyznaczania najtańszego cyklu Hamiltona lub kilku najtańszych cykli Hamiltona w grafie skierowanym. Wyjaśnienie zasad konstruowania drzewa poszukiwań dla tego algorytmu i obliczania dolnego ograniczenia dla wierzchołków tego drzewa.	W5, L5	MEK02
4	TK06	Definicja sieci przepływowej, źródła, ujścia, przepustowości łuków, funkcji przepływu. Praktyczne przykłady takich sieci: sieć dróg, sieć internetowa, sieć elektryczna, wodociągowa itp. Problem maksymalnego przepływu w sieci. Pojęcie przekroju. Twierdzenie i algorytm Forda-Fulkersona o maksymalnym przepływie i minimalnym przekroju. Zasady formułowania programu liniowego w celu znalezienia maksymalnego przepływu w sieci.	W6, L6	MEK03
4	TK07	Problem najtańszego przepływu w sieci. Przepustowość łuku i koszt przesyłu jednostki medium przez łuk. Algorytm Busackera-Gowena wyznaczania najtańszego przepływu w sieci. Zasady formułowania programu liniowego w celu wyznaczenia najmniejszego kosztu przesłania zadanego przepływu.	W7, L7	MEK04

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 4)	Przygotowanie do kolokwium: 3.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.	Uzupełnienie/studiowanie notatek: 5.00 godz./sem. Studiowanie zalecanej literatury: 7.00 godz./sem.
Laboratorium (sem. 4)		Godziny kontaktowe: 15.00 godz./sem.	Dokończenia/wykonanie sprawozdania: 10.00 godz./sem.
Konsultacje (sem. 4)
Zaliczenie (sem. 4)

Sposób wystawiania ocen składowych zajęć i oceny końcowej

Forma zajęć	Sposób wystawiania oceny podsumowującej
Wykład	Na podstawie kolokwium zaliczeniowego na wykładzie.
Laboratorium	Na podstawie opracowanych sprawozdań, zawierających wyniki symulacji komputerowych oraz obliczenia "ręczne", a także na podstawie co najmniej jednego kolokwium.
Ocena końcowa	Na podstawie ocen z wykładu i z laboratorium, wstępnie jako średnia arytmetyczna obu tych ocen. Obie te części przedmiotu muszą być zaliczone na minimum 3,0.

Przykładowe zadania

Wymagane podczas egzaminu/zaliczenia
(-)

Realizowane podczas zajęć ćwiczeniowych/laboratoryjnych/projektowych
(-)

Inne
(-)

Czy podczas egzaminu/zaliczenia student ma możliwość korzystania z materiałów pomocniczych : tak

Dostępne materiały : Z notatek sporządzonych na wykładach i laboratoriach, również z wydruków komputerowych. Nie może korzystać ze smartfona ani innego komputera, chyba że będzie to konieczne i zarządzi tak nauczyciel.

Treści zajęć powiazane są z prowadzonymi badaniami naukowymi: nie