Algorytmy II 1000-I1ASD2

Zajęcia obejmują następująca tematykę:
1. Przepływy w sieciach i algorytmy znajdowania maksymalnego i najtańszego przepływu;
a) algorytm Forda-Fulkersona
b) algorytm Edmondsa-Karpa
c) przepływ z minimalnym kosztem
2. Skojarzenia w grafach dwudzielnych
a) metoda wykorzystująca maksymalny przepływ
b) metoda ścieżek powiększających;
4. Pokrycia wierzchołkowe w grafach dwudzielnych
5. Skojarzenia w dowolnych grafach i algorytm Edmondsa
6. Algorytm A* (znajdowanie najkrótszej ścieżki)
7. Algorytmy geometryczne
a) przynależność punktu do wielokąta
b) otoczka wypukła - algorytm Jarvisa
8. Algorytmy aproksymacyjne
a) pokrycie wierzchołkowe
b) pokrycie zbioru
c) problem sumy podzbioru

Całkowity nakład pracy studenta

30 godz. – wykład 30 godz. - laboratorium 50 godz. - praca własna - bieżące przygotowanie do zajęć, przygotowanie referatów, przygotowanie programów komputerowych, studiowanie literatury, konsultacje z prowadzącymi zajęcia 35 godz. praca własna - przygotowanie do egzaminu. 5 godz. - zaliczenie laboratorium, ćwiczeń i egzamin RAZEM: 150 godz. 6 pkt. ECTS

Efekty uczenia się - wiedza

W1: zna podstawowe pojęcia teorii grafów i sieci, m.in. pojęcia najkrótszej drogi w grafie, minimalnego drzewa rozpinającego, maksymalnego przepływu w sieci, pokrycia wierzchołkowego grafu, skojarzenia w grafie, grafu dwudzielnego W2: zna podstawowe algorytmy optymalizacyjne: m.in. wyznaczający maksymalny przepływ w sieci, znajdujący maksymalne skojarzenie w grafach, minimalne pokrycie wierzchołkowe w grafach dwudzielnych, A*-algorytm W3: zna następujące algorytmy geometryczne: przynależność punktu do wielokąta; znajdowanie otoczki wypuklej otoczka wypukła metodą Jarvisa W4: zna algorytmy aproksymacyjne wyznaczające: pokrycie wierzchołkowe, pokrycie zbioru, rozwiązujący problem sumy podzbioru. Powyższe efekty realizują efekty kierunkowe: K_W02, K_W05

Efekty uczenia się - umiejętności

U1: umie podać przykłady grafów, grafów dwudzielnych, skojarzenia w grafie, pokrycia wierzchołkowego grafu U2: umie zaimplementować omawiane algorytmy U3: umie stworzyć projekt w zespole wykorzystując GIT Powyższe efekty realizują efekty kierunkowe: K_U03, K_U05, K_U07, K_U27

Efekty uczenia się - kompetencje społeczne

K1: przekazuje innym swoją wiedzę i przemyślenia w zrozumiały sposób; właściwie rozumie sformułowania pytań i problemów, poprawnie posługuje się terminologią fachową K2: rozumie potrzebę ciągłego doskonalenia się K3: umie pracować w zespole Powyższe efekty realizują efekty kierunkowe: K_K02, K_K03, K_K04

Metody dydaktyczne

Wykład, dyskusja podczas wykładów, ćwiczenia i laboratorium programowania

Metody dydaktyczne podające

- opis
- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące

- laboratoryjna
- ćwiczeniowa
- projektu
- referatu

Rodzaj przedmiotu

przedmiot fakultatywny

Wymagania wstępne

Wiadomości z zakresu przedmiotów: Programowanie w wybranym języku programowania Algorytmy i struktury danych

Koordynatorzy przedmiotu

Justyna Kosakowska

Kryteria oceniania

Zaliczenie laboratorium na podstawie przygotowanych projektów (indywidualnych oraz zespołowych z wykorzystaniem GIT) w postaci programów komputerowych będących implementacja poznanych algorytmów. Weryfikacja efektów: U1, U2, K1, K2, K3

Egzamin pisemny lub ustny z tematyki zajęć - wykazanie się znajomością poznanego materiału. Dopuszcza się połączenie egzaminu z prezentacją projektów przygotowanych w ramach laboratorium. Weryfikacja efektów: W1, W2, W3

Kryteria oceny:

- bardzo dobra – student bardzo dobrze przedstawia, omawia oraz implementuje algorytmy prezentowane na zajęciach; potrafi zastosować algorytmy do przykładów, które nie były omawiane na zajęciach; potrafi zmodyfikować znane algorytmy i uzasadnić poprawność swojego rozumowania

- dobra – student prawidłowo przestawia, omawia oraz implementuje algorytmy prezentowane na zajęciach; potrafi zastosować algorytmy do przykładów, które nie były omawiane na zajęciach;

- dostateczna – student prawidłowo przestawia, omawia oraz implementuje proste algorytmy prezentowane na zajęciach; potrafi zastosować algorytmy do przykładów, które były omawiane na zajęciach;

- niedostateczna – student nie potrafi w dostatecznym stopniu przedstawić ani zaimplementować algorytmów prezentowanych na zajęciach, nie potrafi zastosować ich do prostych przykładów omawianych na zajęciach

Praktyki zawodowe

Nie przewiduje się.

Literatura

Literatura podstawowa

M. S. Bazaraa, C. M. Shetty, Nonlinear Programming Theory and Algorithms , New York 1979.
T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów , WN-T, Warszawa 2001.
J. Kosakowska, P. Malicki, Badania operacyjne - programowanie liniowe , skrypt, WMiI 2009.
M. M. Sysło, Algorytmy, WSiP, Warszawa 1997.
M. M. Sysło, N. Deo, J. S. Kowalik, Algorytmy optymalizacji dyskretnej, PWN, Warszawa 1995.

Literatura uzupełniająca

N. Deo, Teoria grafów i jej zastosowania w technice i informatyce, PWN 1980.
R. Faure, J.-P. Boss, A. Le Garff, Badania operacyjne, PWN, Warszawa 1982.
S. I. Gass, Programowanie liniowe, PWN, Warszawa 1980.
B. Korzan, Elementy teorii grafów i sieci (metody i zastosowania), WN-T, Warszawa 1978.
K. Manteuffel, E. Seiffart, Wstęp do algebry liniowej i programowania liniowego, PWN, Warszawa 1975.

Uwagi

W cyklu 2021/22L:

Zaliczenie przedmiotu:
1) Zaliczenie na podstawie projektu
2) Studenci zostaną podzieleni na grupy i w grupach będą tworzyć wspólny projekt
3) Wyniki pracy (dokumentacja, pliki programów, opis poprawności rozwiązania i raporty przeprowadzonych testów) będą zapisywane z wykorzystaniem systemu Git
4) Oceniane będzie: poprawność rozwiązania, systematyczność pracy, sposób prezentacji, kompletność i przejrzystość dokumentacji
5) Oceniane będzie również indywidualne zaangażowanie studenta w realizację projektu
6) Zaliczenie laboratorium (ocena): oceniane będą programy komputerowe i ich poprawność
7) Zaliczenie wykładu (ocena/egzamin): obecność na wykładzie; prezentacja projektów (oceniana będzie dokumentacja oraz opis poprawności rozwiązania); dodatkowo oceniana będzie znajomość algorytmów prezentowanych na wykładzie.

W cyklu 2022/23L:

Więcej informacji

Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb:

Strona przedmiotu 1000-I1ASD2 w USOSweb