Algoritmusok és bonyolultságuk 

Infósoknak: VISZMA00, matekosoknak: VISZM031 kódon fut, kérem mindenki a neki szánt változatot vegye fel!

2021 tavasz

A félév túlnyomó része szemináriumként működik, az órák nagy részén  a kurzus hallgatói tartanak előadást (előre egyeztetett témából, anyagból) a többiek aktív részvételével.

Az előadások és a gyakorlatok nincsenek megkülönböztetve, mindegyik ugyanígy zajlik.

A részvétel kötelező! Csak az vegye fel a tantárgyat aki az órákon részt is tud venni!

A félévi munka (a megtartott előadás,  a többi órán való részvétel és  aktív figyelem) alapján a félév végén megajánlok egy jegyet. Aki ezzel nem elégedett, az vizsgázhat az anyagból.

Fontos: Minden alkalommal a kitűzött időpont előtt legkésőbb két héttel  az előadás  anyagát pontosítjuk. Ennek időpontját az órán vagy emailen egyeztessük. Az előadás előtt kb. egy héttel egy részletes vázlatot szeretnék hallani/ látni a készülő előadásról, legfeljebb csak kisebb részletek tisztázása maradjon az utolsó hétre. Kérem, a készülés ütemezéséhez vegyék azt is figyelembe,  hogy az oktató sem ér rá mindig :(

---

Időpont: K 8:15-10,  IB134;   P 10:15-11:45, IB134 -- helyett ideiglenesen(?) online a Teams csoportban

---

Mikor mi történik:

1. • febr. 9.  8:15-től: Megbeszélés, osztozkodás a témákon, időpontokon.
   • febr.12.  (Matek) óra nem lesz, olvasnivaló: Polynomial hierarchy fejezete - az esetleges kérdéseket várom a Teamsben.
2. • febr.16. Kvantumalgoritmusok/1 (FK)
     
   • febr.19. Kvantumalgoritmusok/2 (FK)
     
3. • febr.23. A kupac adatszerkezet (Király Bence, Urbán Milós)
     
   • febr.26. Rekurziók megoldása, mestertétel (Tasci Fatime Zeynep, Brányi Balázs)   (Matek)
     
4. • márc. 2. Geometriai algoritmusok  (Lenkefi Péter, Hajdú Zsombor)
     
   • márc. 5. Intervallumfák; k.elem keresés lineáris időben (Makara László Árpád, xx)
     
5. • márc. 9. Mintaillesztési algoritmusok (Bobula Dalma, Lauter Kinga Csilla)
     
   • márc.12. Zárkózottság (Turi-Kováts Bálint, Pintér József)   (Matek)
     
6. • márc.16. Paraméteres bonyolultság/1 (Nemkin Viktória, Kovács Milán)
     
   • márc.19. Unió-holvan adatszerkezet és a Kruskal-algoritmus (Parádi Dávid, Versényi Péter)
     
7. • márc.23. On-line algoritmusok (Pham Viet Hung, Hegyi Krisztina)
     
   • márc.26. Amortizált elemzés (Kovács Péter Tamás, Keliger Dániel)   (Matek)
     
8. • márc.30. Párhuzamos algoritmusok/1 (Szűcs Ágnes, Lenkefi Péter, Hajdú Zsombor)
     
   • ápr. 2. szünet
     
9. • ápr. 6. szünet
     
   • ápr. 9. Döntési fák (Ragács Attila, Tarnay Mátyás)   (Matek)
     
10. • ápr.13. Elosztott algoritmusok/1 (Büki Máté, Bajczi Levente)
      
    • ápr.16. Paraméteres bonyolultság - favastagság, fafelbontás ( Kiráy Bálint, Urbán Miklós, Bobula Dalma)
      
11. • ápr.20. Online algoritmusok/2 (Lauter Kinga, Kiráy Bence, Nemkin Viktória,)
      
    • ápr.23. Kommunikációs bonyolultság ( Pallag Jonatán, Fleiner Zsófia) -- Matek
      
12. • ápr.27. Közelítő mintaillesztés, szerkesztési távolság (Kovács Péter Tamás, Brányi Balázs, Pintér József, Makara László,)
      
    • ápr.30. Interaktív protokollok (Hegyi Krisztina, Turi-Kováts Bálint, Szűcs Ágnes, Pham Viet Hung)
      
13. • máj.4. SAT solver (Keliger Dániel, Pallag Jonatán, Bajczi Levente, Fleiner Zsófia )
      
    • máj.7. Tárbonyolultság (Büki Máté, Király Bálint, Ragács Attila, Tarnay Mátyás)  (Matek)
      
14. • máj.11.Elosztott algoritmusok/2 - Vannak hibák... (Versényi Péter, Kovács Milán, Parádi Dávid )
      
    • máj.14. Előadás nem lesz. Visszajelzésekről, jegyekről lehet érdeklődni
      

---

Ütemezve:

• Kupac adatszerkezet és alkalmazásai (Pl. Cormen,Leiserson,Rivest Stein: Új algoritmusok 6, 19, alkalmazás pl. a Dijkstra-algoritmusban; Rónyai,Ivanyos,Szabó: Algoritmusok 2.2.5, 6.2)
  -- Urbán Miklós Vlagyimír Király Bence
• Rekurziók megoldása, mestertétel  (matek) (Pl.Cormen,Leiserson,Rivest Stein: Új algoritmusok 4)
  -- Tasci Fatime Zeynep Brányi Balázs
• Intervallumfák (Pl.Cormen,Leiserson,Rivest Stein: Új algoritmusok 14)
  -- Makara László Árpád
• k. elem keresés lineáris időben (Pl.Cormen,Leiserson,Rivest Stein: Új algoritmusok 9)
  -- Kálvin Tamás Endre
• Geometriai algoritmusok (Pl.Cormen,Leiserson,Rivest Stein: Új algoritmusok 33)
  -- Lenkefi Péter, Hajdú Zsombor László
• Mintaillesztési algoritmusok, Boyer-Moore-heurisztika, KMP-algoritmus (Pl.Cormen,Leiserson,Rivest Stein: Új algoritmusok 32.2, 32.4; Rónyai,Ivanyos,Szabó: Algoritmusok 9.5, ) -- Bobula Dalma, Lauter Kinga Csilla
  
• Amortizált elemzés    (matek)
  -- Kovács Péter Tamás, Keliger Dániel
• Zárkózottság/Evasiveness  (matek)  forrás: Lovász-Young jegyzet 1-2. fejezetek (matek)
  -- Pintér József Turi-Kováts Bálint
• Paraméteres bonyolultság
  -- Nemkin Viktória, Kovács Milán
• Párhuzamos algoritmusok/1 -- Szűcs Ágnes, Polyák Enikő (Pl. Lecture notes 1-4 )
• Elosztott algoritmusok/1 (Pl. Attiya Distributed computing notes)
  -- Bajczi Levente Büki Máté István
• Döntési fák    (matek)
  -- Tarnay Mátyás Ragács Attila
• On-line algoritmusok -- Pham Viet Hung, Hegy Krisztina
• Unió-holvan adatszerkezet és a Kruskal-algoritmus (Pl. Cormen,Leiserson,Rivest Stein: Új algoritmusok 21.1-3, alkalmazás a Kurskal-algoritmusban; Rónyai,Ivanyos,Szabó: Algoritmusok 6.6.3)
  -- Versényi Péter, Parádi Dávid Krisztián

---

Még időpont nélkül:

• Kommunikációs bonyolultság (matek)
  -- Fleiner Zsófia Dóra, ??

---

További témák:

• Közelítő mintaillesztés, szerkesztési távolság
• Elosztott algoritmusok/2 (Pl. Attiya Distributed computing notes)
• Párhuzamos algoritmusok/2 (Pl. Lecture notes 1-4 )
• Kommunikációs bonyolultság 1-2
• Interaktív protokollok    (Pl. Arora-Barak: Computational Complexity: A Modern Approach, 8.1-8.3, 8.5
• Bonyolultsági osztályok (matek)
• ???   (lehet javasolni)

---