Tantárgy kódja

PMB1213

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

Előkövetelmény

PMB1207

Ajánlott félév

6

Cél

megszerzése, elmélyítése. Algoritmusok helyességének és bonyolultságának tanulmányozása.

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 programhelyesség fogalmai ? Algoritmusok helyességének bizonyítása ? A ciklusinvariáns ? Az optimalitás fogalma és bizonyítása ? Bonyolultságelmélet (futási idő és tárigény) ? Iteratív és rekurzív algoritmusok futási idejének és tárigényének elemzése ? Divide et Impera típusú algoritmusok tervezése és elemzése ? Véletlenített algoritmusok ? Rendezett minta és medián. Kiválasztási algoritmusok tervezése és elemzése ? NP és NP-teljes feladatok megoldása. Közelítő algoritmusok tervezése és elemzése ? Nem determinisztikus algoritmusok

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

Ekvivalencia

PTF1213