Kurzus nemzetközi vendég- és részidős hallgatóknak

Kar

Informatikai Kar

Szervezet

IK Algoritmusok és Alkalmazásaik Tanszék

Kód

IP-18fSZEA1G

Cím

A számításelmélet alapjai I. Gy

Tervezett félév

Tavaszi

Meghirdetve

2024/25/1, 2024/25/2

ECTS

3

Nyelv

en

Oktatás célja

a) tudása - Ismeri az informatikai szakterület tudásanyagát megalapozó általános és specifikus matematikai, számítástudományi elveket, tényeket, szabályokat, összefüggéseket, és eljárásokat. - Ismeri és érti az informatikai szakterület legfontosabb általános elméleteit, összefüggéseit, tényanyagát és az ezekhez szükséges felépítő fogalomrendszert, különösen az alábbi területeken: a programozás módszertani alapjai, programozási nyelvek, fordítóprogramok, alkalmazások fejlesztése, programozási környezet; számítógép architektúrák, operációs rendszerek, számítógépes hálózatok, osztott rendszerek, az adatbázisok elméleti alapjai. b) képességei - Képes az általános és specifikus matematikai, számítástudományi elveket, tényeket, szabályokat, összefüggéseket alkalmazni informatikai szakterületen. - Képes informatikai tudását az elsajátított matematikai, számítástudományi elvek, tények, szabályok, eljárások alapján folyamatosan fejleszteni. - Képes az informatika formális modelljeinek alkalmazására.

Tantárgy tartalma

Formális nyelvi alapfogalmak, grammatika, nyelv. Grammatika- és nyelvtípusok. A Chomsky-féle nyelvhierarchia. Véges automaták (determinisztikus, parciális determinisztikus, nemdeterminisztikus). Determinisztikus véges automaták minimalizálása. Reguláris kifejezések. Reguláris grammatikák egy normálformája. Determinisztikus és nemdeterminisztikus véges automata egyenlő elfogadó ereje.  Összefüggés a véges automaták által felismerhető, a reguláris kifejezések által leírható és a reguláris grammatikák által generálható nyelvek osztályai között. A reguláris nyelvek algoritmikus kérdései (szóprobléma, üresség, egyenlőség, diszjunktság, végesség). Reguláris nyelvek zártsági tételei. Myhill-Nerode tétel és egy pumpálási lemma. Környezetfüggetlen (CF) nyelvek. Levezetési fa. Baloldali levezetés és egyértelműség. CF grammatikák átalakításai, a Chomsky és a Greibach normálforma. CF nyelvek zártsági kérdései és pumpálási lemmája. Veremautomata és kapcsolata CF nyelvekkel, a  determinisztikus környezetfüggetlen nyelvek. CF nyelvek algoritmikus kérdései (szóprobléma, üresség, végesség). Algoritmikus kérdések és zártsági tételek környezetfüggő és 0-típusú nyelvekre. Környezetfüggő és hossz-nemcsökkentő grammatikák generatív ereje közötti összefüggés. Normál formák. Formális nyelvi fogalmak gyakorlati alkalmazásai: lexikális és szintaktikai elemzés.  Felülről lefelé illetve  alulról felfelé elemzés.

Számonkérés és értékelés

A hallgatóknak teljesíteniük kell a kurzus tanára által a félév elején ismertetett követelményeket, mely általában tartalmaz 2 sikeres zárthelyi dolgozatot és egy rendszeres részvételre vonatkozó feltételt. Ötfokozatú értékelés.

Irodalomjegyzék

J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd ed. Pearson Education Ltd., 2014. A. V. Aho, R. Sethi, J. D. Ullman: Compilers - Principles, Techniques, and Tools, 2nd ed. Pearson Education Ltd., 2014. A. Salomaa, G. Rozenberg (eds.): The Handbook of Formal Languages I., II., Springer Publishing Company, 1997. Arto Salomaa: Formal Languages, Academic Press, 1973.

Kurzus szakjai