BME VIK - Algoritmusok és bonyolultságuk

vissza a tantárgylistához nyomtatható verzió

Algoritmusok és bonyolultságuk

A tantárgy angol neve: Algorithms and Complexity

Adatlap utolsó módosítása: 2010. június 8.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Mérnök informatikus szak, MSc képzés

Számításelmélet szakirány

Tantárgykód	Szemeszter	Követelmények	Kredit	Tantárgyfélév
VISZM143	1	2/1/0/v	4

3. A tantárgyfelelős személy és tanszék Dr. Friedl Katalin,

4. A tantárgy előadója Dr. Friedl Katalin egyetemi docens

5. A tantárgy az alábbi témakörök ismeretére épít

Alapvető algoritmikus technikák

6. Előtanulmányi rend

Kötelező:

NEM ( TárgyEredmény( "BMEVISZMA00" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZMA00", "FELVETEL", AktualisFelev()) > 0)

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

Ajánlott:
Ezt a tárgyat nem vehetik fel, akik a VISZM031 kódú “ Algoritmusok és bonyolultságuk – matematikusoknak” című tárgyat teljesítették.

7. A tantárgy célkitűzése A tantárgy célja az algoritmikus gondolkodás továbbfejlesztése, a BSc-hez képest további módszerek, technikák megismerése. A hallgatók betekintést kapnak a témakör modern irányzataiba, az új és jövőbeli eszközök (párhuzamos számítások, kvantumszámítógépek) által megoldható kérdésekre, felvetett problémákra.

8. A tantárgy részletes tematikája

Geometriai algoritmusok (legközelebbi pontpár, konvex burok meghatározása)
Párhuzamos algoritmusok (PRAM modellek, egyszerű függvények kiszámítása az eltérő modellekben, Brent-elv, párhuzamos rendezés, prefix számítások)
Elosztott algoritmusok (a vezetőválasztás algoritmusai, egyezségre jutás, illetve ennek lehetetlensége különböző típusú hibák esetén: vonalhiba, leállási hiba, bizánci hiba)
Interaktív bizonyítások (az NP kiterjesztése interaktív algoritmusok segítségével, interakció egy erős és egy gyenge fél között, az AM és az IP nyelvosztály, jellemző példák, IP=PSPACE, a PCP elmélet kapcsolata a közel optimális megoldás megtalálhatóságával)
On-line algoritmusok (modell, hatékonyság mérése, listaelérési feladat, ütemezési problémák)
Paraméteres bonyolultság (NP-nehéz, de paraméteresen megoldható feladatok, korlátos mélységű keresőfák, a gráfminor tétel és következményei, W[1]-teljesség)
A kvantumalgoritmusok alapjai (számítási modell, lépés mint unitér transzformáció, illetve vetítés, no-cloning tétel, egyszerű algoritmusok, prímfaktorizáció, keresés, kvantumszámítás és titkosítás)

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) előadás + gyakorlat

10. Követelmények

szorgalmi időszakban: öt kiszárthelyi (10-15 perces) dolgozat a gyakorlatokon; az aláíráshoz ezekből legalább hármat megfelelt szinten kell teljesíteni
vizsgaidőszakban: szóbeli vizsga

11. Pótlási lehetőségek

A kiszárthelyik pótlására nincs mód.

12. Konzultációs lehetőségek Előzetes egyeztetés szerint.

13. Jegyzet, tankönyv, felhasználható irodalom

T. Corman, C. Leiserson, R. Rivest, C. Stein: Új algoritmusok, Scolar Kiadó, 2003.

H. Attiya: Distributed Computing (lecture notes)

J. Flum, M. Grohe: Parameterized Complexity Theory, Springer 2006.

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

Kontakt óra	42
Félévközi készülés órákra	30
Felkészülés zárthelyire
Házi feladat elkészítése
Kijelölt írásos tananyag elsajátítása
Vizsgafelkészülés	48
Összesen	120

15. A tantárgy tematikáját kidolgozta Dr Friedl Katalin egyetemi docens

Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

Algoritmusok és bonyolultságuk