Module also offered within study programmes:
General information:
Name:
Combinatorial algorithms 1
Course of study:
2019/2020
Code:
AMAT-2-108-MZ-s
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Mathematics in Management
Field of study:
Mathematics
Semester:
1
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

Wprowadzenie i przykłady algorytmów kombinatorycznych.

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 Rozumie i docenia znaczenie uczciwości intelektualnej w działaniach własnych i innych osób. MAT2A_K04 Activity during classes
Skills: he can
M_U001 Potrafi samodzielnie przeprowadzić ścisłe rozumowanie z wykorzystaniem zdobytej wiedzy MAT2A_U03, MAT2A_U01 Scientific paper
M_U002 Potrafi ocenić trudność problemów pod kątem wykorzystania algorytmów MAT2A_U21, MAT2A_W07 Scientific paper
M_U003 Potrafi ze zrozumieniem przedstawić poznane zagadnienia MAT2A_U19, MAT2A_U01, MAT2A_K07, MAT2A_K02, MAT2A_U15, MAT2A_U02, MAT2A_K05 Scientific paper
Knowledge: he knows and understands
M_W001 Zna podstawowe modele algorytmiczne oraz typy zagadnień praktycznych wykorzystujących wybrane modele MAT2A_W11, MAT2A_W02, MAT2A_W04 Scientific paper
M_W002 Zna i rozumie podstawowe techniki projektowania algorytmów MAT2A_W11, MAT2A_W02 Scientific paper
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
30 0 0 0 0 0 30 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 Rozumie i docenia znaczenie uczciwości intelektualnej w działaniach własnych i innych osób. - - - - - + - - - - -
Skills
M_U001 Potrafi samodzielnie przeprowadzić ścisłe rozumowanie z wykorzystaniem zdobytej wiedzy - - - - - + - - - - -
M_U002 Potrafi ocenić trudność problemów pod kątem wykorzystania algorytmów - - - - - + - - - - -
M_U003 Potrafi ze zrozumieniem przedstawić poznane zagadnienia - - - - - + - - - - -
Knowledge
M_W001 Zna podstawowe modele algorytmiczne oraz typy zagadnień praktycznych wykorzystujących wybrane modele - - - - - + - - - - -
M_W002 Zna i rozumie podstawowe techniki projektowania algorytmów - - - - - + - - - - -
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 50 h
Module ECTS credits 2 ECTS
Udział w zajęciach dydaktycznych/praktyka 30 h
przygotowanie projektu, prezentacji, pracy pisemnej, sprawozdania 20 h
Module content
Seminar classes (30h):

1. Podstawowe techniki projektowania algorytmów.
2. Generowanie zbiorów i podzbiorów.
3. Generowanie permutacji i ciągów.
4. Generowanie podziałów zbiorów.
5. Generowanie podziałów liczb.
6. Funkcje tworzące.
7. Metody przeszukiwania heurystycznego.
8. Podstawowe algorytmy teorii grafów.
9. Problem plecakowy.
10. Problem komiwojażera.

Additional information
Teaching methods and techniques:
  • Seminar classes: Na zajęciach seminaryjnych podstawą jest prezentacja multimedialna oraz ustna prowadzona przez studentów. Kolejnym ważnym elementem kształcenia są odpowiedzi na powstałe pytania, a także dyskusja studentów nad prezentowanymi treściami.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Participation rules in classes:
  • Seminar classes:
    – Attendance is mandatory: Yes
    – Participation rules in classes: Studenci prezentują na forum grupy temat wskazany przez prowadzącego oraz uczestniczą w dyskusji nad tym tematem. Ocenie podlega zarówno wartość merytoryczna prezentacji, jak i tzw. kompetencje miękkie.
Method of calculating the final grade:

Przygotowanie oraz wygłoszenie referatów na seminarium.

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.

Prerequisites and additional requirements:

Wprowadzenie do matematyki dyskretnej
Teoria algorytmów

Recommended literature and teaching resources:

D.L. Kreher, D.L. Stinson, Combinatorial algorithms, CRC Press, 1999.

Scientific publications of module course instructors related to the topic of the module:

1.
A possible analogue of ρ-labellings for 3-uniform hypergraphs / Mariusz MESZKA, Alexander Rosa // Electronic Notes in Discrete Mathematics ; ISSN 1571-0653. — 2017 vol. 60, s. 33–37. — Bibliogr. s. 37, Abstr.. — Publikacja dostępna online od: 2017-06-29. — IWOGL 2016 : 9th International Workshop on Graph Labelings : Krakow, Poland, July 7–9, 2016. — tekst: https://goo.gl/tf4GpN

2.
Kite systems of order 8; embedding of kite systems into bowtie systems / Mariusz MESZKA, Alexander Rosa, Beatrice Ruini // Australasian Journal of Combinatorics ; ISSN 1034-4942. — 2017 vol. 67 pt. 2, s. 378–393. — Bibliogr. s. 393, Abstr.. — tekst: http://ajc.maths.uq.edu.au.df3pc3jl127a.wbg2.bg.agh.edu.pl/pdf/67/ajc_v67_p378.pdf

3.
Maximal edge-colorings of graphs / Mariusz MESZKA, Magdalena TYNIEC // Graphs and Combinatorics ; ISSN 0911-0119. — 2017 vol. 33 iss. 6, s. 1451–1458. — Bibliogr. s. 1458, Abstr.. — Publikacja dostępna online od: 2017-05-26. — tekst: https://goo.gl/MQWfoQ

4.
Revisiting the intersection problem for minimum coverings of complete graphs with triples / C. C. Lindner, C. A. Rodger, M. MESZKA // Australasian Journal of Combinatorics ; ISSN 1034-4942. — 2017 vol. 68 pt. 2, s. 276–284. — Bibliogr. s. 284, Abstr.. — tekst: http://ajc.maths.uq.edu.au.df3pc3jl1257.wbg2.bg.agh.edu.pl/pdf/68/ajc_v68_p276.pdf

Additional information:

Seminarium dostępne od roku ak. 2018/19