Algorytmy II
Informacje ogólne
Kod przedmiotu: | 1000-I1ASD2 |
Kod Erasmus / ISCED: |
(brak danych)
/
(0613) Tworzenie i analiza oprogramowania i aplikacji
|
Nazwa przedmiotu: | Algorytmy II |
Jednostka: | Wydział Matematyki i Informatyki |
Grupy: |
Inf., I st., stacjonarne, 2 rok, przedmioty do wyboru Inf., I st., stacjonarne, 3 rok, przedmioty do wyboru Inf., II st, stacjonarne, przedmioty do wyboru |
Punkty ECTS i inne: |
6.00
|
Język prowadzenia: | polski |
Wymagania wstępne: | Wiadomości z zakresu przedmiotów: Programowanie w wybranym języku programowania Algorytmy i struktury danych |
Rodzaj przedmiotu: | przedmiot fakultatywny |
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 |
Metody dydaktyczne poszukujące: | - ćwiczeniowa |
Skrócony opis: |
Przedmiot jest poświęcony bardziej zaawansowanym problemom oraz algorytmom ich rozwiązywania. Problemy mają solidne umocowanie w zagadnieniach praktycznych, podobnie algorytmy ich rozwiązywania. |
Pełny opis: |
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 |
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. |
Metody i 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ę. |
Zajęcia w cyklu "Semestr letni 2021/22" (zakończony)
Okres: | 2022-02-21 - 2022-09-30 |
Przejdź do planu
PN WT ŚR WYK
CZ LAB
LAB
PT |
Typ zajęć: |
Laboratorium, 30 godzin, 16 miejsc
Wykład, 30 godzin, 32 miejsc
|
|
Koordynatorzy: | Justyna Kosakowska | |
Prowadzący grup: | Mariusz Kaniecki, Justyna Kosakowska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Laboratorium - Zaliczenie na ocenę Wykład - Egzamin |
|
Uwagi: |
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. |
Zajęcia w cyklu "Semestr letni 2022/23" (zakończony)
Okres: | 2023-02-20 - 2023-09-30 |
Przejdź do planu
PN LAB
LAB
WT ŚR CZ WYK
PT |
Typ zajęć: |
Laboratorium, 30 godzin, 16 miejsc
Wykład, 30 godzin, 32 miejsc
|
|
Koordynatorzy: | Justyna Kosakowska | |
Prowadzący grup: | Mariusz Kaniecki, Justyna Kosakowska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Laboratorium - Zaliczenie na ocenę Wykład - Egzamin |
|
Uwagi: |
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łaścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.