Introduction to the Theory of Computing
A tantárgyleírás hatályossága
| Subject name (Hungarian, English) |
Bevezetés a számításelméletbe
Introduction to the Theory of Computing
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVIMA3242 | ||||||||||||
| Subject type | — | ||||||||||||
| Training Level | — | ||||||||||||
| Course types and hours (weekly/semester) |
|
||||||||||||
| Assessment type | vizsga | ||||||||||||
| Credits | 5 | ||||||||||||
| Subject coordinator |
DR. Katona Gyula
position: egyetemi tanár
contact:
katona.gyula@vik.bme.hu
|
||||||||||||
| Responsible department |
—
|
||||||||||||
| Faculty | |||||||||||||
| Subject website | — | ||||||||||||
| 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
Komplex számok, kanonikus és trigonometrikus alak, műveletek, egységgyökök. Végtelen számosságok. Vektoralgebra, 2- és 3-dimenziós analitikus geometria. Lineáris algebra elemei (vektortér, altér, bázis, generátorrendszer). Lineáris transzformációk, mátrixok, lineáris egyenletrendszer megoldhatósága, egyértelműsége. Determináns definíciói, tulajdonságai. Négyzetes mátrixok sajátértékei, sajátvektorai. Alapvető kombinatorikai ismeretek (permutációk, variációk, kombinációk), binomiális tétel. Gráfelméleti alapfogalmak, fák, fák száma, minimális költségű fa keresése. Síkbarajzolhatóság, dualitás. Gráfok mátrixai.
Gráfok pont- és élszínezése, Mycielsky konstrukciója, perfekt gráfok. Négy- és ötszíntétel. Euler- és Hamilton-tételkör. Szélességi és mélységi keresés, legrövidebb út kereső algoritmusok. Párosítások, Hall és Tutte tételei. Gallai tételei. Hálózati folyamok. Menger-tételkör. A mélységi keresés alkalmazásai, topológiai rendezés, PERT-módszer.
Számelmélet (oszthatóság, a számelmélet alaptétele, euklideszi algoritmus, kongruencia, maradékosztályok, Euler-Fermat tétel, lineáris kongruenciák megoldása, prímtesztelés, nyilvános kulcsú titkosírások).
Absztrakt algebra (félcsoport, csoport, rend, nevezetes csoportok, részcsoport,, gyűrű,).
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
Tanulástámogató anyagok
Not provided.
Recommended preliminary knowledge for completing the subject
General rules
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
Curriculum placement
No curriculum placements recorded for this subject version.