A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
| Subject name (Hungarian, English) |
Algoritmuselmélet
Theory of Algorithms
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVISZAA08 | ||||||||||||
| Subject type | — | ||||||||||||
| Training Level | — | ||||||||||||
| Course types and hours (weekly/semester) |
|
||||||||||||
| Assessment type | félévközi érdemjegy | ||||||||||||
| Credits | 5 | ||||||||||||
| Subject coordinator |
DR. Katona Gyula
position: egyetemi tanár
contact:
katona.gyula@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/thalg/ | ||||||||||||
| 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
1. Minimum and maximum search in n-1 steps, selection sort, order of magnitude of functions, Ordo notation, solving simple recursion equations, merge sort.
2. Comparison based sorting and their analysis (bubble, insertion, merge, quick sort). Lower bounds for the number of comparisons needed. Non-comparison-based sorts and their analysis: bin sort, radix sort.
3. Representation of graphs with a matrix or edge list, the number of steps of basic operations in graphs, depth-first search, directed-acyclic graphs (DAG), their recognition.
4. Finding a topological order, shortest and longest path in DAG
5. Dynamic programming, knapsack problem, maximum sum interval
6. The Dijkstra algorithm and proof of its correctness
7. Data structures: binary tree and its traversals, heap, Dijsktra algorithm with heap
8. Binary search tree, red-black tree, 2-3-tree, B-tree
9. Bucket hashing, hash with open addressing
10. Kruskal implementation details, number of steps, Prim algorithm
11. Decision problems, efficient witness, definitions of problem classes P, NP, coNP and their relationship
12. The Karp reduction and its properties, NP-completeness, examples of NP-complete problems
13. Approximation algorithms, epsilon approximation, bin packing, FirstFit algorithm, FirstFitDecreasing algorithm, traveling salesman problem: in general and the Euclidean version, branch-and-bound
(K1) Knowledge level:
recalling, listing and superficially presenting the concepts of the topic.
(K2) Level of understanding:
knowledge of explanations, connections, recognition and classification of cases.
(K3) Application level:
applying knowledge of problem solving, solving examples and tasks independently.
(K4) Construction level:
problem analysis, setting up alternative solutions, comparison, choice, justification.
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
2 hours lecture, 2 hours problem solving
Tanulástámogató anyagok
Online források
By appointment.
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)
graph theory, high school mathematics
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)
graph theory, high school mathematics
General rules
Requirements:
During the semester, we have 2 midterms. For completing the semester: at least 40% performance in both midterms. The final grade (if completed) is determined by the average of the mindterm results.
Additional possibilities:
During the semester, there will be a possibility to retake both midterms.
During the make-up week, there will be only one time when one of the midterms can retaken again.
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.