Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowaniaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

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
Punkty ECTS i inne: 6.00
Język prowadzenia: polski
Wymagania wstępne:

Wiadomości z zakresu przedmiotów:

Wstęp do informatyki/Programowanie w wybranym języku programowania (C++ lub Python)

Matematyka dyskretna

Algorytmy i struktury danych

Rodzaj przedmiotu:

przedmiot fakultatywny

Całkowity nakład pracy studenta:

1. 30 godz. wykładu + 30 godz. ćwiczeń

2. Zadania domowe: przygotowanie się do ćwiczeń, często zaprogramowanie wybranych algorytmów w wybranym języku programowania (C++ lub Python)- 90-120 godz.

3. Egzamin - 3 godz.


Efekty uczenia się - wiedza:

Po zakończeniu tych zajęć student:

Formułuje problemy omawiane na zajęciach, ich własności, metody ich rozwiązywania i ich złożoność, wśród nich:

1. przepływy w sieciach i algorytmy znajdowania maksymalnego i najtańszego przepływu; przegląd najefektywniejszych algorytmów i technik;

2. problemy kombinatoryczne rozwiązywane technikami przepływów w sieciach: opływy, problemy transportowe, systemy różnych reprezentantów

3. zastosowania przepływów w sieciach do rozwiązywania problemów praktycznych, np. problemów szeregowania zadań

4. skojarzenia i ich algorytmy - klasyczny problem na grafach dwudzielnych i dowolnych; 1-faktory w grafach (tw. W.T. Tutte'a)

5. skojarzenia stabilne z wariantami, w tym problem współmieszkańców (room mates)

6. problemy kombinatoryczne na zbiorach częściowo uporządkowanych - podział na łańcuchy, rozszerzenia liniowe, problem skoków, zastosowania do problemów szeregowania.

7. algorytmy przybliżone dla wybranych problemów dyskretnych - ilustracja różnych technik i jakości przybliżeń

Efekty uczenia się - umiejętności:

Po zakończeniu tych zajęć student zarówno potrafi:

1. zastosować poznane fakty (definicje, twierdzenia, algorytmy) w podobnych sytuacjach, zwłaszcza praktycznych

2. zaprogramować w wybranym języku programowania (C++ lub Python) poznane algorytmy dobierając odpowiednie struktury danych

Efekty uczenia się - kompetencje społeczne:

Po zakończeniu zajęć student rozumie i posługuje się terminologia zakresu bardziej zaawansowanych algorytmów dla problemów praktycznych.

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

Skrócony opis:

Przedmiot jest poświęcony bardziej zaawansowanym problemom oraz ich algorytmom rozwiązywania. Problemy mają solidne umocowanie w zagadnieniach praktycznych, podobnie algorytmy ich rozwiązywania.

Same algorytmy są realizacją wielu nowych, w stosunku do poznanych wcześniej, technik algorytmicznych.

Kryterium wyboru algorytmów jest ich złożoność obliczeniowa i praktyczna użyteczność, co będzie weryfikowane na zajęciach podczas uruchamiania własnych implementacji algorytmów.

Pełny opis:

Zajęcia obejmują następująca tematykę:

1. Przepływy w sieciach i algorytmy znajdowania maksymalnego i najtańszego przepływu; przegląd najefektywniejszych algorytmów i technik;

2. Problemy kombinatoryczne rozwiązywane technikami przepływów w sieciach: opływy, problemy transportowe, systemy różnych reprezentantów.

3. Zastosowania przepływów w sieciach do rozwiązywania problemów praktycznych, np. problemów szeregowania zadań

4. Skojarzenia i ich algorytmy - klasyczny problem na grafach dwudzielnych i dowolnych; 1-faktory w grafach (tw. W.T. Tutte'a)

5. Skojarzenia stabilne z wariantami, w tym problem współmieszkańców (room mates).

6. Problemy kombinatoryczne na zbiorach częściowo uporządkowanych - podział na łańcuchy (tw. Dilwortha), rozszerzenia liniowe, problem skoków, zastosowania do problemów szeregowania.

7. Algorytmy przybliżone dla wybranych problemów dyskretnych - ilustracja różnych technik i jakości przybliżeń.

Przedmiot jest poświęcony bardziej zaawansowanym problemom oraz ich algorytmom rozwiązywania. Problemy mają solidne umocowanie w zagadnieniach praktycznych, podobnie algorytmy ich rozwiązywania.

Same algorytmy są realizacją wielu nowych, w stosunku do poznanych wcześniej, technik algorytmicznych.

Kryterium wyboru algorytmów jest ich złożoność obliczeniowa i praktyczna użyteczność, co będzie weryfikowane na zajęciach podczas uruchamiania własnych implementacji algorytmów w wybranym języku programowania (C++ lub Python).

Literatura:

1. Cormen T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT/PWN.

2. Ford L.R., Fulkerson D.R., Przepływy w sieciach, PWN, Warszawa 1967.

3. Sysło M.M., Deo N., Kowalik J.S., Algorytmy optymalizacji dyskretnej z programami w języku Pascal, PWN, Warszawa 1997.

Literatura będzie sukcesywnie dodawana, zwłaszcza opracowania zagadnień i algorytmów, które nie znalazły się jeszcze w żadnym podreczniku.

Metody i kryteria oceniania:

Zaliczenie ćwiczeń na podstawie aktywności i przedstawionych rozwiązań zadań, np. w postaci programów komputerowych będących implementacja poznanych algorytmów

Egzamin pisemny z tematyki zajęć - wykazanie sie umiejętnością poznanego materiału (egzamin może mieć formę open book lub take home).

Praktyki zawodowe:

Nie przewiduje się.

Zajęcia w cyklu "Semestr letni 2017/18" (zakończony)

Okres: 2018-02-26 - 2018-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 50 miejsc więcej informacji
Koordynatorzy: Maciej Sysło
Prowadzący grup: Anna Kwiatkowska, Maciej Sysło
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr letni 2021/22" (jeszcze nie rozpoczęty)

Okres: 2022-02-21 - 2022-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 30 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
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.