Subject » BMEVISZMA02
Advanced Mathematics for Informatics - System Optimisation
Felsőbb matematika informatikusoknak - Rendszeroptimalizálás
A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
| Subject name (Hungarian, English) |
Felsőbb matematika informatikusoknak - Rendszeroptimalizálás
Advanced Mathematics for Informatics - System Optimisation
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVISZMA02 | ||||||||||||
| Subject type | — | ||||||||||||
| Training Level | — | ||||||||||||
| Course types and hours (weekly/semester) |
|
||||||||||||
| Assessment type | vizsga | ||||||||||||
| Credits | 4 | ||||||||||||
| Subject coordinator |
DR. Szeszlér Dávid
position: egyetemi docens
contact:
szeszler.david@vik.bme.hu
|
||||||||||||
| Responsible department |
Számítástudományi és Információelméleti Tanszék
|
||||||||||||
| Faculty | Villamosmérnöki és Informatikai Kar | ||||||||||||
| Subject website | http://cs.bme.hu/rendszeropt | ||||||||||||
| Primary curriculum type | — | ||||||||||||
| Direct prerequisites – Strong prerequisite | none | ||||||||||||
| Direct prerequisites – Weak prerequisite | none | ||||||||||||
| Direct prerequisites – Parallel prerequisite | none | ||||||||||||
| Direct prerequisites – Milestone prerequisite | none | ||||||||||||
| Direct prerequisites – Exclusion | none |
Objectives
Programme
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.
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.
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.
Learning outcomes
Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:
Knowledge
No learning outcomes recorded.
Skills
No learning outcomes recorded.
Attitudes
No learning outcomes recorded.
Autonomy and responsibility
No learning outcomes recorded.
Oktatási módszertan
4 hours of lecture per week
Tanulástámogató anyagok
Online források
Foulds, L. R. (2012). Combinatorial optimization for undergraduates. Springer Science & Business Media.
Recommended preliminary knowledge for completing the subject
Knowledge type competencies
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Skill type competencies
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Recommended (non-compulsory) preliminary competencies
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
nincs
General rules
Requirements:
Signature:
1 midterm during the semester the result of which has to be at least 40%.
Final:
Oral exam.
Additional possibilities:
2 occasions for retaking the midterm will be provided (the second one in the week preceding the exam period).
Assessment methods
In-term assessments
No detailed assessments provided.
Weight of in-term assessments
No weights provided.
Exam-period assessments
No detailed assessments provided.
Weight of exam elements
No weights provided.
Grade calculation
No grade thresholds provided.
Attendance requirements
No attendance requirements provided.
Rules for retake and resubmission
Not provided.
Short description
Not provided.
Detailed description
Not provided.
Recommended courses
Not provided.
Workload to complete the subject
No workload breakdown provided.
Validity of subject requirements
Requirements valid from:
—
Requirements valid until:
—
Curriculum placement
No curriculum placements recorded for this subject version.