Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Teoria Algorytmów
Tok studiów:
2019/2020
Kod:
AMAT-2-301-MI-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka w informatyce
Kierunek:
Matematyka
Semestr:
3
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
dr hab. Meszka Mariusz (meszka@agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Podstawowe modele algorytmiczne oraz typy zagadnień praktycznych wykorzystujących wybrane modele. Metody oceny efektywności czasowej oraz pamięciowej. Złożoność obliczeniowa.

Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
M_W001 Zna i rozumie podstawowe pojęcia dotyczące analizy algorytmów oraz technik projektowania algorytmów MAT2A_W11 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_W002 Potrafi ocenić trudność problemów pod kątem wykorzystania algorytmów MAT2A_W11, MAT2A_W02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_W003 Zna podstawowe modele algorytmiczne oraz typy zagadnień praktycznych wykorzystujących wybrane modele MAT2A_W11, MAT2A_W02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Umiejętności: potrafi
M_U001 Potrafi ze zrozumieniem przedstawić poznane zagadnienia MAT2A_U19, MAT2A_U02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_U002 Potrafi samodzielnie przeprowadzić ścisłe rozumowanie z wykorzystaniem zdobytej wiedzy MAT2A_U03, MAT2A_U01 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_U003 Potrafi wykorzystać elementy wiedzy z teorii algorytmów w rozwiązywaniu zagadnień praktycznych MAT2A_U20, MAT2A_U19, MAT2A_U16 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Kompetencje społeczne: jest gotów do
M_K001 Potrafi krytycznie ocenić stopień zrozumienia przez siebie postawionego problemu i braki elementów rozumowania MAT2A_K01, MAT2A_K02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
M_W001 Zna i rozumie podstawowe pojęcia dotyczące analizy algorytmów oraz technik projektowania algorytmów + + - - - - - - - - -
M_W002 Potrafi ocenić trudność problemów pod kątem wykorzystania algorytmów + + - - - - - - - - -
M_W003 Zna podstawowe modele algorytmiczne oraz typy zagadnień praktycznych wykorzystujących wybrane modele + + - - - - - - - - -
Umiejętności
M_U001 Potrafi ze zrozumieniem przedstawić poznane zagadnienia + + - - - - - - - - -
M_U002 Potrafi samodzielnie przeprowadzić ścisłe rozumowanie z wykorzystaniem zdobytej wiedzy + + - - - - - - - - -
M_U003 Potrafi wykorzystać elementy wiedzy z teorii algorytmów w rozwiązywaniu zagadnień praktycznych + + - - - - - - - - -
Kompetencje społeczne
M_K001 Potrafi krytycznie ocenić stopień zrozumienia przez siebie postawionego problemu i braki elementów rozumowania + + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 150 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 42 godz
Samodzielne studiowanie tematyki zajęć 41 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Dodatkowe godziny kontaktowe 5 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (30h):

1. Przypomnienie podstawowych pojęć. Przypomnienie metod zapisu algorytmów (metajęzyk, schemat blokowy) na przykładach poznanych wcześniej prostych algorytmów (wyszukiwanie, sortowanie).
2. Metody oceny efektywności czasowej oraz pamięciowej. Klasyfikacja problemów algorytmicznych pod kątem klas złożoności obliczeniowej. Metody oceny poprawności obliczeniowej (proste przykłady).
3. Przypomnienie definicji struktur grafowych oraz metod ich implementacji. Algorytmy przeszukiwania grafu w głąb – omówienie techniki z nawrotami. Algorytm przeszukiwania wszerz – implementacja operacji kolejkowych.
4. Znajdowanie minimalnego drzewa spinającego w grafie (algorytmy Kruskala oraz Prima) – szczegółowa analiza techniki zachłannego wyboru.
5. Znajdowanie ścieżek o minimalnych długościach w grafach skierowanych (algorytmy: Bellmana-Forda oraz Dijkstry). Znajdowanie najkrótszych ścieżek pomiędzy wszystkim parami wierzchołków (algorytm Floyda-Warshalla) – analiza techniki programowania dynamicznego.
6. Przepływy w sieciach (metoda Forda-Fulkersona).
7. Inne zagadnienia przepływowe (przepływy w sieciach z dolną i górną przepustowością, przepływy o minimalnym koszcie).
8. Znajdowanie maksymalnego skojarzenia w grafach (algorytm Edmondsa) oraz grafach dwudzielnych. Znajdowanie skojarzenia o minimalnym koszcie.
9. Zagadnienia transportowe: droga Eulera, problem chińskiego listonosza.
10. Zagadnienia transportowe cd.: problem komiwojażera – algorytmy aproksymacyjne na przykładzie TSP z nierównością trójkąta (algorytmy: drzewowy, Christofidesa).
11. Algorytmy testowania planarności grafu (metoda dodawania wierzchołków oraz dodawania krawędzi).
12. Algorytmy kolorowania wierzchołków w grafie.
13. Algorytmy kolorowania krawędzi w grafie.
14. Podsumowanie.

Ćwiczenia audytoryjne (30h):
Program ćwiczeń pokrywa się z programem wykładu

Rozwiązywanie problemów ilustrujące treści przekazywanych na kolejnych wykładach.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Ćwiczenia audytoryjne: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej problemy. Prowadzący na bieżąco dokonuje stosowanych wyjaśnień i moderuje dyskusję z grupą nad danym problemem.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Warunkiem koniecznym dopuszczenia do egzaminu jest posiadanie oceny pozytywnej z ćwiczeń.
Dwa terminy zaliczeń poprawkowych są skorelowane czasowo z egzaminami poprawkowymi.

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Ćwiczenia audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci przystępując do ćwiczeń są zobowiązani do przygotowania się w zakresie wskazanym każdorazowo przez prowadzącego (np. w formie zestawów zadań). Ocena pracy studenta może bazować na wypowiedziach ustnych lub pisemnych w formie kolokwium, co zgodnie z regulaminem studiów AGH przekłada się na ocenę końcową z tej formy zajęć.
Sposób obliczania oceny końcowej:
  1. Warunkiem koniecznym dopuszczenia do egzaminu jest posiadanie oceny pozytywnej z ćwiczeń.
  2. Ocenę końcową OK wyznacza się na podstawie średniej ważonej SW obliczonej według wzoru
    SW = 0,2 OC + 0,8 OE,
    gdzie OC jest oceną uzyskaną z ćwiczeń,
    a OE jest oceną uzyskaną z egzaminu.
  3. Ocena końcowa OK. jest obliczana według algorytmu:
    Jeżeli SW ≥ 4.75, to OK = 5.0 (bdb),
    jeżeli 4.75 > SW ≥ 4.25, to OK = 4.5 (db),
    jeżeli 4.25 > SW ≥ 3.75, to OK = 4.0 (db),
    jeżeli 3.75 > SW ≥ 3.25, to OK = 3.5 (dst),
    jeżeli 3.25 > SW ≥ 3.00, to OK = 3.0 (dst).
Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Student powinien zgłosić się do prowadzącego w celu ustalenia indywidualnego sposobu nadrobienia zaległości.

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

znajomość języka C/C++
podstawowe pojęcia z teorii grafów

Zalecana literatura i pomoce naukowe:
  1. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT 2007.
  2. A.V. Aho, J.E. Hopcroft, J.D. Ullman, Projektowanie i analiza algorytmów, Helion 2003.
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. Meszka, Mariusz; Rosa, Alexander; Cubic leaves, Australas. J. Comb. 61, 114-129, electronic only (2015).

2. Lindner, Charles C.; Meszka, Mariusz; Rosa, Alexander ; From squashed 6-cycles to Steiner triple systems, J. Comb. Des. 22, No. 5, 189-195 (2014).

3. Horňák, Mirko; Kalinowski, Rafał; Meszka, Mariusz; Woźniak, Mariusz;
Minimum number of palettes in edge colorings.
Graphs Comb. 30, No. 3, 619-626 (2014).

4. Meszka, Mariusz, The chromatic index of projective triple systems; J. Comb. Des. 21, No. 11, 531-540 (2013).

5. Cichacz, Sylwia; Froncek, Dalibor; Meszka, Mariusz; Decomposition of complete graphs into small generalized prisms; AKCE Int. J. Graphs Comb. 10, No. 3, 285-293 (2013).

6. Lindner, C.C.; Meszka, M.; Rosa, A.; Triple metamorphosis of twofold triple systems; Discrete Math. 313, No. 19, 1872-1883 (2013).

7. Kovář, Petr; Kubesa, Michael; Meszka, Mariusz; Factorizations of complete graphs into brooms;
Discrete Math. 312, No. 6, 1084-1093 (2012).

8. Billington, Elizabeth J.; Hoffman, D.G.; Lindner, C.C.; Meszka, Mariusz;
Almost resolvable minimum coverings of complete graphs with 4-cycles.
Australas. J. Comb. 50, 73-85 (2011).

9. Billington, Elizabeth J.; Lindner, C.C.; Meszka, Mariusz
Twofold 2-perfect bowtie systems with an extra property;
Aequationes Math. 82, No. 1-2, 143-153 (2011).

10. Almost 2-perfect minimum coverings of\emph{Kn} with 6-cycles / Charles C. Lindner, Mariusz MESZKA // Bulletin of the ICA [Institute of Combinatorics and its Applications] vol. 75, s. 64–78 (2015).

11. Cubic leaves / Mariusz MESZKA, Alexander Rosa // Australasian Journal of Combinatoricsvol. 61 pt. 1–2, s. 114–129 (2015).

12. Squashing minimum coverings of 6-cycles into minimum coverings of triples / Elizabeth J. Billington, Selda Küçükçifçi, C. C. Lindner, Mariusz MESZKA // Aequationes Mathematicae ;vol. 89 iss. 4, s. 1223–1239 (2015).

13. Decompositions of complete graphs into circulants / Mariusz MESZKA, Roman Nedela, Alexander Rosa, Martin Škoviera // Discrete Mathematics vol. 339 iss. 10, s. 2471–2480 (2016).

Informacje dodatkowe:

Brak