A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
| Subject name (Hungarian, English) |
Számításelmélet
Theory of Computing
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVISZA081 | ||||||||||||
| Subject type | — | ||||||||||||
| Training Level | — | ||||||||||||
| Course types and hours (weekly/semester) |
|
||||||||||||
| Assessment type | vizsga | ||||||||||||
| Credits | 4 | ||||||||||||
| 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 | www.cs.bme.hu/.... | ||||||||||||
| 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
First half-semester
- Finite automata, non-deterministic finite automata
- Regular and non-regular languages, pumping lemma.
- Pushdown automata, context-free languages,
- Turing Machines and variants, universal Turing machines.
- The existence of universal Turing machines.
- Recursive functions. Recursive, recursively enumerable languages.
Second half-semester
- Algorithmic decidability,
- Halting problem and other undecidable problems.
- Storage and time, general theorems on space and time complexity
- Non-deterministic Turing-machines. NP and co-NP.
- Cook's theorem: SAT is NP-complete.
- Other NP-complete problems.
In the first part of this course we introduce different theoretical models for computing. There are ones that are easy to describe but have limited power, and there are more complicated ones with more power. The first one is the finite automaton. On one hand it is used directly, since it is easy to build them to perform simple tasks. Many electronic devices contain basically one chip, which is really a finite automaton. On the other hand, it can be used as a programming technique, too. It helps in code optimization and verification. Unfortunately, not every problem can be solved by them, we will show their limits.
The next model is the pushdown automaton. It has more power, but still is not too hard to build one. It is used widely in compilers, for example.
The last important model is the Turing machine. It is considered to be the model of an everyday computer. It is very powerful, one can solve most of the real life problems with it, especially if there is no time limit. We will define many variants as well and see how these variations change its power.
In the second half of this course the first important question that we answer: Is there an algorithm for any problem? If there is an algorithm, can we implement it by a given computational model? It turns out that there are some interesting problems that seem to be much more difficult than others even if the computers would be extremely fast.
Another question is that what happens if we have limited resources. Time and/or space is limited for the computation, which is the case in real life.
Scientists over centuries tried to solve some difficult algorithmic problems, but failed to succeed in some cases. Is it the case that they are not clever enough? Or there is no algorithm at all? Is there something in between these two possibilities?
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
Lectures and recitations
Tanulástámogató anyagok
Online források
Michael Sipser: Introduction to the Theory of Computation, Thomson Course Technology, 2006
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:
A homework set of 4 problems will be given out on weeks 2 – 5 and on weeks 8-11.
Grading will be based on the following criteria:
- Homeworks 60 points
- Final exam 40 points
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.