The aim of studying and bibliography

The main aim of study: The aim of the course is to introduce students with the methods of discrete optimization and their applications in data analysis.

The general information about the module: The module contains overview of exact and approximate algorithms used in discrete optimization.

Bibliography required to complete the module

Bibliography used during lectures

1	M.Kubale (red)	Optymalizacja dyskretna. Modele i metody kolorowania grafów	PWN Warszawa.	2002
2	M. Sysło, N. Deo, J. Kowalik	Algorytmy optymalizacji dyskretnej	PWN, Warszawa.	1999
3	A. Włoch, I. Włoch	Matematyka dyskretna- podstawowe metody i algorytmy teorii grafów	Oficyna Wydawnicza Politechniki Rzeszowskiej, Rzeszów.	2004
4	N. Deo	Teoria grafów i jej zastosowania w technice i informatyce	PWN, Warszawa.	1980

Bibliography used during classes/laboratories/others

1	K. Ross, Ch. Wright	Matematyka dyskretna	PWN, Warszawa.	2012
2	R. J. Wilson	Wprowadzenie do teorii grafów	PWN, Warszawa.	2012

Bibliography to self-study

1

R. Diestel

Graph Theory

Springer-Verlag, Heidelberg New York.

2005

Basic requirements in category knowledge/skills/social competences

Formal requirements: The student satisfies the formal requirements set out in the study regulations.

Basic requirements in category knowledge: Student is familiar with the basics of graph theory and discrete mathematics.

Basic requirements in category skills: The student can implement algorithms in chosen programming language.

Basic requirements in category social competences: A student can work in group.

Module outcomes

MEK	The student who completed the module	Types of classes / teaching methods leading to achieving a given outcome of teaching	Methods of verifying every mentioned outcome of teaching	Relationships with KEK	Relationships with PRK
01	The student knows the basic methods of discrete optimization.	lecture, project	group project, practical test on the computer	K_W01+ K_W02+ K_W03+ K_U02+ K_U03+ K_K01+ K_K02+ K_K05+	P6S_KK P6S_KO P6S_UW P6S_WG
02	The student can formulate an engineering problem as a problem of discrete mathematics.	lecture, project	group project, practical test on the computer	K_W01+ K_W02+ K_W03+ K_U02+ K_U03+ K_K01+ K_K02+ K_K05+	P6S_KK P6S_KO P6S_UW P6S_WG
03	The student can create the model of the problem and solve it using discrete optimization.	lecture, project	group project, practical test on the computer	K_W01+ K_W02+ K_W03+ K_U02+ K_U03+ K_K01+ K_K02+ K_K05+	P6S_KK P6S_KO P6S_UW P6S_WG
04	The student can apply exact and approximate algorithms to do calculations, generate combinatorial objects or create the model.	lecture, project	group project, practical test on the computer	K_W01+ K_W02+ K_W03+ K_U02+ K_U03+ K_K01+ K_K02+ K_K05+	P6S_KK P6S_KO P6S_UW P6S_WG

Attention: Depending on the epidemic situation, verification of the achieved learning outcomes specified in the study program, in particular credits and examinations at the end of specific classes, can be implemented remotely (real-time meetings).

The syllabus of the module

Sem.	TK	The content	realized in	MEK
4	TK01	Knapsack problem. Exact and approximate algorithms. Applications.	W1-W2,	MEK01 MEK02 MEK03 MEK04
4	TK02	Set covering problem. Exact and approximate algorithms. Applications.	W3-W4,	MEK01 MEK02 MEK03 MEK04
4	TK03	Optimization on networks. The problems of the shortest paths and the minimum spanning tree. Application.	W5-W6,	MEK01 MEK02 MEK03 MEK04
4	TK04	The maximum flow problem. The Ford-Fulkerson algorithm. Minimum cost flows. The Busacker-Gowen algorithm. Application of flows.	W7-W8,	MEK01 MEK02 MEK03 MEK04
4	TK05	Maximum matching. Applications.	W9-W10,	MEK01 MEK02 MEK03 MEK04
4	TK06	Travelling salesman problem. Branch and bound method. Approximate algorithms. Applications.	W11-W12,	MEK01 MEK02 MEK03 MEK04
4	TK07	Colouring and tasks scheduling. Applications.	W13-W15,	MEK01 MEK02 MEK03 MEK04
4	TK08	Creating a group project on the subject chosen by the students. The project should contain the description of the problem and an algorithm and executable file.	P1-P15	MEK01 MEK02 MEK03 MEK04

The student's effort

The type of classes	The work before classes	The participation in classes	The work after classes
Lecture (sem. 4)	The preparation for a test: 5.00 hours/sem.	contact hours: 15.00 hours/sem.
Project/Seminar (sem. 4)	The preparation for projects/seminars: 10.00 hours/sem.	contact hours: 15.00 hours/sem..
Advice (sem. 4)		The participation in Advice: 2.00 hours/sem.
Credit (sem. 4)	The preparation for a Credit: 5.00 hours/sem.	The written credit: 2.00 hours/sem. Others: 3.00 hours/sem.

The way of giving the component module grades and the final grade

The type of classes	The way of giving the final grade
Lecture	A credit of the lecture is based on attendance at the lectures.
Project/Seminar	The grade is the weighted average of grades for the group project (0,7) and the test (0,3).
The final grade	The final grade is the grade obtained during the project classes.

Sample problems

Required during the exam/when receiving the credit
(-)

Realized during classes/laboratories/projects
(-)

Others
(-)

Can a student use any teaching aids during the exam/when receiving the credit : no

The contents of the module are associated with the research profile: no