Wierk - Wydział Informatyki, Elektroniczne Ramy Kwalifikacji

Wydział Informatyki
Kierunek studiów	Informatyka							Poziom i forma studiów	drugiego stopnia niestacjonarne
Specjalność / Ścieżka dyplomowania	Systemy Inteligentne							Profil kształcenia	ogólnoakademicki
Nazwa przedmiotu	Algorytmika - wybrane zagadnienia							Kod przedmiotu	INZ2AWZ
								Rodzaj przedmiotu	obieralny
Forma zajęć i liczba godzin	W	Ć	L	P	Ps	T	S	Semestr	2/3
	10				20			Punkty ECTS	3
Przedmioty wprowadzające
Cele przedmiotu	Celem przedmiotu jest wykształcenie umiejetności konstruowania modelu grafowego lub sieciowego dla rzeczywistych problemów. Student zostanie wyposażony w wiedzę na temat: metod wyznaczania najkrótszych ścieżek w grafach, metod projektowania efektywnych rozwiązań dla problemów przepływowych w sieciach , metod konstrouwania efektywnych heurystyk dla problemów grafowych trudnych obliczeniowo. Student wykształci umiejętności: projektowania efektywnych obliczeniowo algorytmów i struktur danych dla problemów grafowych, oceny efektywności zastosowanych rozwiązań, identyfikacji problemów trudnych obliczeniowo i stosowania rozwiązań przybliżonych dla tych problemów. Celem przedmiotu jest również wykształcenie umiejętności skutecznego komunikowania się w zakresie problemów inżynierskich i naukowych z przedstawicielami innych dziedzin.
Treści programowe	Wykład: Algorytmy przeglądania grafów. Metody BFS i DFS oraz ich zastosowania. Efektywne algorytmy ścieżowkowe dla grafów z wagami. Strategie: label-setting oraz label-corecting. Problem maksymalnego przepływu w sieci oraz efektywne metody jego wyznaczania. Problem najtańszego przepływu w sieci - efektywne algorytmy oraz przykłady zastosowania. Problemy grafowe i sieciowe trudno rozwiązalne. Przykłady rozwiązań przybliżonych dla problemów grafowych klasy NPC. Problem komiwojażera oraz jego odmiany. Przykłady zastosowań różnych odmian problemy komiwojażera w systemach informatycznych z zakresu logistyki oraz systemów klasy e-tourism. Efektywne algorytmy aprokysmacyjne dla różnych odmian problemu komiwojażera. Problem routing w sieciach transportowych. Pracownia specjalistyczna: Zadanie problemowe wymagające opracowania algorytmu opartego o metody BFS i DFS przeszukiwania grafu Zadanie problemowe wymagające opracowania algorytmu opartego na zastosowaniu algorytmów ściezkowych Zadanie problemowe wymagające opracowania algorytmu opartego na zastosowaniu algorytmów przepływowych Zadanie problemowe wymagajace opracowania algorytmu opartego na zostosowaniu algorytmów aproksymacyjnych.
Metody dydaktyczne	wykład problemowy, programowanie z użyciem komputera,
Forma zaliczenia	Wykład - zaliczenie pisemne. Pracownia specjalistyczna - ocena cząstkowych zadań problemowych.
Symbol efektu uczenia się	Zakładane efekty uczenia się								Odniesienie do kierunkowych efektów uczenia się
EU1	zna i rozumie pojęcia związane z algorytmiką w zakresie zagadnień grafowych i sieciowych								INF2_W01
EU2	zna i rozumie sposób działania standardowych metod projektownia efektywnych algorytmów grafowych i sieciowych								INF2_W03
EU3	potrafi zbudować model grafowy lub sieciowy dla problemu sformułowanego językiem praktyki								INF2_W03 INF2_U01 INF2_U06
EU4	potrafi projektować efektywne rozwiązania dla zidentyfikowanego problemu grafowego lub sieciowego i opisywać je stosując nomenklaturę i pojęcia występujące w stworzonym modelu								INF2_U03 INF2_U11 INF2_K02
EU5	potrafi ocenić jakość zaproponowanych rozwiązań, przeprowadzić ich testy poprawności i złożoności obliczeniowej								INF2_U04 INF2_U07 INF2_K03 INF2_K05
Symbol efektu uczenia się	Sposób weryfikacji efektu uczenia się								Forma zajęć na której zachodzi weryfikacja
EU1	zaliczenie pisemne								W
EU2	zaliczenie pisemne								W
EU3	zaliczenie pisemne, zaliczenie zadań z pracowni specjalistycznej								W, Ps
EU4	zaliczenie zadań z pracowni specjalistycznej, dyskusja w trakcie zajęć								Ps
EU5	zaliczenie zadań z pracowni specjalistycznej, dyskusja w trakcie zajęć								Ps
Bilans nakładu pracy studenta (w godzinach)									Liczba godz.
Wyliczenie
	1 - Udział w wykładach - 10x1h								10
	2 - Udział w pracowni specjalistycznej - 10x2h								20
	3 - Przygotowanie do pracowni specjalistycznej								15
	4 - Realizacja zadań problemowych pracowni specjalistycznej								20
	5 - Udział w konsultacjach								2
	6 - Przygotowanie do zaliczenia								8
RAZEM:									75
Wskaźniki ilościowe									GODZINY	ECTS
Nakład pracy studenta związany z zajęciami wymagającymi bezpośredniego udziału nauczyciela									32 (2)+(1)+(5)	1.3
Nakład pracy studenta związany z zajęciami o charakterze praktycznym									57 (2)+(4)+(3)+(5)	2.3
Literatura podstawowa	1. Ravindra H, Ahuja Tomas L., Magnati James B. Orlin, Przepływy sieciowe: Teoria, Algorytmy i Zastosowania, (ang. Network flows : theory, algorithms, and applications), Prentice Hall, 1993. 2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa, 2004. 3. A. V. Aho, J. E. Hopcroft, J. D. Ullman, Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa, 2007.
Literatura uzupełniająca	1. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, Warszawa, 2006 2. A. Drozdek, D. L. Simon Struktury danych w jezyku C, WNT, Warszawa, 2003 3. N. Wirth, Algorytmy + struktury danych = programy, WNT, Warszawa, 2004
Jednostka realizująca	Katedra Informatyki Teoretycznej								Data opracowania programu
Program opracował(a)	dr inż. Krzysztof Ostrowski								2020.05.22