Tantárgy kódja

PTF1213

Tantárgy neve

Algoritmusok tervezése és elemzése

Tantárgy angol neve

Algorithm Theory

Kredit

3

Félévi követelmény

Vizsga

Heti óraszám

2 + 0

Elmélet + Gyakorlat

Ajánlott félév

2

Cél

Programozás- és algoritmuselméleti ismeretek megszerzése, elmélyítése. Kompetenciák: programhelyesség bizonyítás képessége, párhuzamos programok jellemzőinek megismerése, problémamegoldó képesség fejlesztése, összefüggés-felismerő képesség fejlesztése.

Cél angol

 The subject aims are to reach competences in the ability to program correctness proof, understanding the characteristics of parallel programs, problem solving skills, and the development context-aware capabilities.

Tartalom

A program szemantika definiálásának módjai: operációs, denotációs, axiomatikus szemantika. A programhelyesség fogalmai. A programbizonyítás módszerei. Floyd-Naur-féle lépésenkénti bizonyítás, Hoare-féle induktív kifejezések módszere, Dijkstra-féle leggyengébb előfeltétel-kalkulus. Nem szekvenciális programok analízise. Párhuzamos programok speciális tulajdonságai. Párhuzamos programok helyességének Owitzki-Gries- és Stirling-féle módszere. Nem determinisztikus programok, helyességük bizonyítása, Dijkstra-féle őrzött utasítások. A Kröger-féle programmodell, programtulajdonságok kifejezése az időlogikában. Rekurzív programok.

Tartalom angol

The program semantics for defining ways: operating, denotációs, axiomatic semantics. The program notions of correctness. The program proof methods. Floyd-Naur's step-proof, Hoare's terms inductive method of Dijkstra's weakest precondition calculus. Analysis of nonsequential programs. The special characteristics of parallel programs.  Correctness of arallel programs by Owitzki-Gries and Stirling's method. Proof of correctness of non-deterministic programs,  Dijkstra's guarded commands. The Kroger's program model, expression of program features in time logics . Recursive programs.

Számonkérés

vizsga

Számonkérés angol

Examination

Irodalom

Herendi Tamás: Algoritmusok, Kelet-Magyarországi Informatikai Tananyag Tárház, 2012 http://progmat.hu/tananyagok/algoritmusok/book.html 

Irodalom angol

Ian Sommerville: Software Engineering (9th ed) , Addison-Wesley, Boston, 2009.                                                 Iványi Antal ed.: ALGORITHMS OF INFORMATICS I, Kelet-Magyarországi Informatikai Tananyag Tárház, 2012 http://progmat.hu/tananyagok/algorithms_of_informatics_volume1/book.html  Iványi Antal ed.: ALGORITHMS OF INFORMATICS II, Kelet-Magyarországi  Informatikai Tananyag Tárház, 2012

Tantárgyfelelős intézet kódja

MII

Tantárgyfelelős oktató

Dr. Dömösi Pál Béla