Algoritmusok és bonyolultságuk

A tantárgy angol neve: Algorithms and Complexity 

Adatlap utolsó módosítása: 2023. január 12.

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

Mérnökinformatikus MSc

Számításelmélet mellékspecializáció
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZMA14   2/1/0/v 5  
3. A tantárgyfelelős személy és tanszék Dr. Friedl Katalin,
A tantárgy tanszéki weboldala http://cs.bme.hu/algbony
4. A tantárgy előadója

Dr. Csima Judit,      egyetemi docens, SZIT  

Dr. Friedl Katalin,   egyetemi docens, SZIT 

Dr. Katona Gyula,   egyetemi docens, SZIT 

5. A tantárgy az alábbi témakörök ismeretére épít Alapvető adatszerkezetek és algoritmusok (a BSc Algoritmuselmélet tantárgyának anyaga)
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ó.

7. A tantárgy célkitűzése

A tantárgy célja az algoritmikus gondolkodás fejlesztése, további módszerek, technikák megismerése. A hallgatók betekintést kapnak nem csak a klasszikus, de az újabb és jövőbeli eszközökkel kapcsolatos eredményekbe, kérdésekbe is. Az aktuális témák és időzítésük a hallgatói érdeklődés függvényében valamennyire változhatnak. Cél, hogy mindenki, általában angol nyelvű anyagok alapján, két témakört önállóan is feldolgozzon, majd prezentálja a többieknek.

 

A tantárgy követelményeit eredményesen teljesítő hallgatóktól elvárható, hogy:  

 (1) ismerjék meg a tárgyalt módszereket, képesek legyenek oktatói segítséggel egy kisebb témakört önállóan is feldolgozni,  

 (2) átlássák a módszerek helyességét és ezt világos módon el is tudják magyarázni, 

 (3) képesek legyenek egy nagyobb anyagból kiválasztani az érdekes és releváns részeket, 

 (4) felismerjék az egyes anyagrészek közötti kapcsolatokat, alkalmazási lehetőségeiket valós problémákra.

 

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

A témák listája és sorrendje a hallgatók érdeklődésének függvényében változhat. Ez itt egy lehetséges változat. Az aktuális féléves anyag és beosztás a honlapon megtalálható.

  1. A várható témakörök megbeszélése, annak felmérése, ki milyen témákkal szeretne mélyebben foglalkozni. A kvantumalgoritmusok alapjai.
  2. Hatékony keresés kvantumalgoritmussal. A kvantumtitkosítás alapmódszere.
  3. Interaktív bizonyítások – az NP osztály kiterjesztése. Az AM és az IP osztályok, IP=PSPACE, a PCP alapötlete.
  4. Kommunikációs bonyolultság alapfeladata, determinisztikus és nemdeterminisztikus változata, ezek kapcsolata. Példa, amikor a véletlen segíthet.
  5. Gyakorlati mintaillesztő algoritmusok: Boyer-Moore.-algoritmus és egyéb heurisztikák.
  6. Párhuzamos algoritmusok: a PRAM modell különböző változatai. Algoritmus néhány alapvető függvényre. Bináris fa alapú algoritmusok. A processzorszám csökkentése, Brent-elv.
  7. Batcher párhuzamos rendező algoritmusa. Párhuzamos prefix-számítás és alkalmazásai. A rang meghatározása.
  8. Elosztott algoritmusok: elméleti modell. Vezetőválasztás gyűrűben szinkron és aszinkron esetben. Általánosítás tetszőleges összefüggő gráfra. Alsó becslés.
  9. Elosztott algoritmus hibák esetén. A vonalhiba esete. Algoritmus leállási hibákra. Tetszőleges (bizánci) hibák kezelése. A maximálisan tolerálható hibás processzorok száma.
  10. Hálózati topológiák pl. rács, CCC, pillangó, Benes-hálózat gráfelméleti tulajdonságai (legrövidebb utak, átmérő, vágások, összefüggőségi szám), egymásba ágyazhatóságuk, algoritmikus szempontok.
  11. Véletlen gráfok különböző modelljei, alaptulajdonságuk (pl. fokszámok, utak, összefüggőség). Véletlen gráfok mint hálózati modellek.
  12. On-line algoritmusok: modell, hatékonyság mérése. A listaelérési feladat, dinamikus adatszerkezetek, k-szerver probléma, népszerű ütemező eljárások elemzése.
  13. Paraméteres bonyolultság: NP-nehéz de kis paraméterérték mellet gyorsan megoldható feladatok. Keresőfa korlátozása és a kernelizációs módszer. W[1]-teljesség.


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

A tananyag nagyobb részét szeminárium-szerűen, hallgatók által tartott órákkal dolgozzuk fel. A témák sorrendje, pontos köre évről évre változhat valamennyit. Az aktuális szabályokat, menetrendet az első órán megbeszéljük. 

10. Követelmények
  • Jelenlét az órákon (a TVSZ-ben előírt mértékben). 
  • A jelenlét mellett aktív, odafigyelő  részvétel is elvárt. 
  • Az előre egyeztetett témákból felkészülés és  az előadások megtartása. Ez mindenkinek két témát jelent, egyet a félév első, egyet a második felében.
12. Konzultációs lehetőségek

Az előadóval való egyeztetés szerint.

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

Thomas H. Cormen,  Charles E. Leiserson , Ronald L. Rivest,  Clifford Stein: Új algoritmusok Scolar Kiadó, 2003  

A. Gibbons, W. Rytter: Efficient Parallel Algorithms, Cambridge University press, 1988 

J. Flum, M. Groha: Parametrized Complexity Theory, Springer 2006 

H. Attiya: Distributed Computing lecture notes 

További, az interneten elérhető jegyzetek, anyagok

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra42
Félévközi készülés órákra36
Felkészülés zárthelyire 
Házi feladat elkészítése 
Kijelölt írásos tananyag elsajátítása52
Vizsgafelkészülés20
Összesen150
15. A tantárgy tematikáját kidolgozta

Dr. Friedl Katalin egyetemi docens, SZIT