Module also offered within study programmes:
General information:
Name:
Theory of Algorithms
Course of study:
2019/2020
Code:
AMAT-2-041-MU-s
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Insurance Mathematics
Field of study:
Mathematics
Semester:
0
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
dr hab. Meszka Mariusz (meszka@agh.edu.pl)
Module summary

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

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence: is able to
M_K001 Potrafi krytycznie ocenić stopień zrozumienia przez siebie postawionego problemu i braki elementów rozumowania MAT2A_K01, MAT2A_K02 Activity during classes,
Test,
Oral answer
Skills: he can
M_U001 Potrafi ze zrozumieniem przedstawić poznane zagadnienia MAT2A_U19, MAT2A_U02 Activity during classes,
Test,
Oral answer
M_U002 Potrafi samodzielnie przeprowadzić ścisłe rozumowanie z wykorzystaniem zdobytej wiedzy MAT2A_U03, MAT2A_U01 Activity during classes,
Test,
Oral answer
M_U003 Potrafi wykorzystać elementy wiedzy z teorii algorytmów w rozwiązywaniu zagadnień praktycznych MAT2A_U19, MAT2A_U16 Activity during classes,
Test,
Oral answer
Knowledge: he knows and understands
M_W001 Zna i rozumie podstawowe pojęcia dotyczące analizy algorytmów oraz technik projektowania algorytmów MAT2A_W11 Activity during classes,
Test,
Oral answer
M_W002 Potrafi ocenić trudność problemów pod kątem wykorzystania algorytmów MAT2A_W11, MAT2A_W02 Activity during classes,
Test,
Oral answer
M_W003 Zna podstawowe modele algorytmiczne oraz typy zagadnień praktycznych wykorzystujących wybrane modele MAT2A_W11, MAT2A_W02 Activity during classes,
Test,
Oral answer
Number of hours for each form of classes:
Sum (hours)
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Social competence
M_K001 Potrafi krytycznie ocenić stopień zrozumienia przez siebie postawionego problemu i braki elementów rozumowania + + - - - - - - - - -
Skills
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 + + - - - - - - - - -
Knowledge
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 + + - - - - - - - - -
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 105 h
Module ECTS credits 4 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 h
Preparation for classes 28 h
Realization of independently performed tasks 10 h
Examination or Final test 2 h
Contact hours 5 h
Module content
Lectures (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). Przepływy w sieciach z dolną i górną przepustowością.
7. Znajdowanie maksymalnego skojarzenia w grafach (algorytm Edmondsa) oraz grafach dwudzielnych. Znajdowanie skojarzenia o minimalnym koszcie.
8. Zagadnienia transportowe: droga Eulera, problem chińskiego listonosza.
9. Zagadnienia transportowe cd.: problem komiwojażera – algorytmy aproksymacyjne na przykładzie TSP z nierównością trójkąta (algorytmy: drzewowy, Christofidesa).
10. Algorytmy testowania planarności grafu (metoda dodawania wierzchołków oraz dodawania krawędzi).
11. Algorytmy znajdowania wzorca w tekście: metoda naiwna, algorytmy: Rabina-Karpa oraz Knutha-Morrisa-Pratta.
12. Algorytmy geometrii obliczeniowej: znajdowanie wypukłej otoczki, znajdowanie pary najmniej odległych punktów, testowania przecinających się odcinków.
13. Bezstratne metody kompresji danych: kodowanie Huffmana, Shannona-Fano. Kompresja stratna obrazów i dźwięku.
14. Przegląd podstawowych algorytmów kryptograficznych: RSA, EIGamal.

Auditorium classes (30h):
Program ćwiczeń pokrywa się z programem wykładu

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

Additional information
Teaching methods and techniques:
  • Lectures: 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ń.
  • Auditorium classes: 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:

dwa zaliczenia poprawkowe

Participation rules in classes:
  • Lectures:
    – Attendance is mandatory: No
    – Participation rules in classes: 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.
  • Auditorium classes:
    – Attendance is mandatory: Yes
    – Participation rules in classes: 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ęć.
Method of calculating the final grade:

zaliczenie

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 wyrównywania zaległości.

Prerequisites and additional requirements:

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

Recommended literature and teaching resources:
  1. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT 2007.
Scientific publications of module course instructors related to the topic of the module:

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).

Additional information:

None