Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowania
Strona główna

Algorytmy II

Informacje ogólne

Kod przedmiotu: 1000-I1ASD2
Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
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 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
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
- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące:

- ćwiczeniowa
- laboratoryjna
- projektu
- referatu

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
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 32 miejsc więcej informacji
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
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 32 miejsc więcej informacji
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.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.
ul. Jurija Gagarina 11, 87-100 Toruń tel: +48 56 611-40-10 https://usosweb.umk.pl/ kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)