Advanced Mathematics for Informatics - System Optimisation

A tantárgy neve magyarul / Name of the subject in Hungarian: Felsőbb matematika informatikusoknak - Rendszeroptimalizálás

Last updated: 2016. január 14.

Budapest University of Technology and Economics
Faculty of Electrical Engineering and Informatics 		MSc degree program in Software Engineering
Course ID Semester Assessment Credit Tantárgyfélév
VISZMA02 1 4/0/0/v 4  
3. Course coordinator and department Dr. Szeszlér Dávid,
Web page of the course http://cs.bme.hu/rendszeropt
4. Instructors

Dr. András Recski, professor, Department of Computer Science and Information Theory

Dr. Dávid Szeszlér, associate professor, Department of Computer Science and Information Theory 

Dr. Gábor Wiener, associate professor, Department of Computer Science and Information Theory 

6. Pre-requisites
Kötelező:
NEM ( TárgyEredmény( "BMEVISZM117" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZM117", "FELVETEL", AktualisFelev()) > 0
VAGY
TárgyEredmény( "BMEVISZMA10" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZMA10", "FELVETEL", AktualisFelev()) > 0)

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

7. Objectives, learning outcomes and obtained knowledge

The subject introduces some areas of operations research and combinatorial optimization. Besides covering the most relevant algorithms and methods and their limits, it also aims at giving a glimpse into some of their engineering applications. Thus the subject also covers some general algorithmic approaches like linear and integer programming and matroid theory. Furthermore, the course aims at extending and deepening the knowledge formerly provided by the Introduction to the Theory of Computing 1 and 2 and the Theory of Algorithms subjects of the BSc degree program in Software Engineering.

8. Synopsis Linear programming. Methods of solution, Farkas' lemma,
duality, integer programming, branch and bound, totally unimodular
matrices.
Matroid theory. Basic notions, greedy algorithm, duality, minors,
direct sum, algorithms, Tutte's and Seymour's theorems, rank function,
matroid matching.
Approximation algorithms. Additive and relative error, examples.
Scheduling algorithms. Types, algorithms of Hu, Coffman and Graham.
Reliable network design. Local edge connectivity, edge connectivity
number, algorithms of Nagamochi and Ibaraki, Karger, Khuller and
Vishkin, Cheriyan and Thurimella, Plesnik.
Applications in electrical networks and statics. Kichhoff's theorems,
rigidity of frameworks.
9. Method of instruction 4 hours of lecture per week
10. Assessment

Signature:

1 midterm during the semester the result of which has to be at least 40%.

Final:

Oral exam.

11. Recaps 2 occasions for retaking the midterm will be provided (the second one in the week preceding the exam period).
12. Consultations Subject to individual arrangements.
13. References, textbooks and resources Foulds, L. R. (2012). Combinatorial optimization for undergraduates. Springer Science & Business Media.
14. Required learning hours and assignment
In class56
Preparation for classes 12
Preparation for midterms 12
Homework 
Reading assignment 
Preparation for final 40
Total 120
15. Syllabus prepared by Dr. Dávid Szeszlér, associate professor, Department of Computer Science and Information Theory