Algoritmusok és bonyolultságuk
Infósoknak: VISZMA00,
matekosoknak: VISZM031 kódon fut, kérem mindenki a neki szánt
változatot vegye fel!
2022 tavasz
Figyelmeztetés:
A tantárgy erősen épít a Bevezetés a számításelméletbe 2
(matematikusoknál: Kombinatorika és gráfelmélet 1) és az
Algoritmuselmélet tantárgyakban szereplő algoritmusokra,
adatszerkezetekre, bonyolultságelméleti alapokra. Akinek ezen a
téren hiányosak az ismeretei, előbb ezeket pótolja, utána vegye
csak fel a kurzust!
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, utána már legfeljebb
csak kisebb részletek tisztázása maradjon az utolsó hétre.
- Az előadás után 1 héttel jelentkezzenek a
visszajelzésekért.
Kérem, 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
Mikor mi történik:
-
- febr.15. 8:15-től: Megbeszélés, osztozkodás a
témákon, időpontokon.
- febr.18. A polinomiális hierarchia (FK)
( --Matek)
-
- febr.22. Kvantumalgoritmusok/1 (FK)
- febr.25. Kvantumalgoritmusok/2 (FK)
-
- márc. 1. A kupac adatszerkezet (Barta Botond, Ágó
Bernát)
- márc. 4. Rekurzió nagyságrendje - mester tétel (Bartis
Zsolt, Homolya Panni) -- Matek
-
- márc. 8. k. elem keresés+intervallumfák (Varga Dóra.
Mezei Szabolcs)
- márc.11. Párhuzamos algoritmusok/1 (Zakar-Polyák
Enikő, Vizi Béla)
-
- márc.15. ünnep
- márc.18. Amortizált elemzés (Turcsik Zsófia, Ködmön
Lili) --Matek
-
- márc.22. Geometriai algoritmusok (Lellei Benedek,
Körtvélyesi Viktor)
- márc.25. Mintaillesztés (Lakatos Dorina, Zách Levente)
-
- márc.29. Az unió-holvan adatszerkezet (Kálvin Tamás,
Mészáros Bálint)
- ápr. 1. Bonyolultságelmélet: P és NP között
(Tóth Szilárd, Csonka Bence) --Matek
-
- ápr. 5. On-line algoritmusok (Garami Bence, Popovics
Bence)
- ápr. 8. Elosztott algoritmusok/1 (Barta Botond, Ágó
Bernát)
-
- ápr.12. Kommunikációs bonyolultság (Mezei Szabolcs,
Varga Dóra)
- ápr.15. szünet
-
- ápr.19. szünet
- ápr.22. Mintaillesztés/2: Boyer-Moore; szerkesztési
távolság (Zakar-Polyák Enikő, Vizi Béla)
-
- ápr.26. Interaktív protokollok (Körtvélyesi Viktor,
Lellei Benedek)
- ápr.29. Bonyolultságelmélet/2: tárbonyolultság
(Bartis Zsolt, Homolya Panni) -- Matek
-
- máj.3. Paraméteres bonyolultság//1: bevezető,
korlátozott keresőfa (Turcsik Zsófia, Ködmön Lili)
- máj.6. Paraméteres bonyolultság/2: kernelizáció,
fafelbontás (Popovics Bence, Garami Bence)
-
- máj.10. Elosztott algoritmusok/2: egyezség hibák
esetén (Zách Levente, Lakatos Dorina)
- máj.13. Zárkózottság (Tóth Szilárd, Csonka Bence)
--Matek
-
- máj.17. Binomiális kupac (Mészáros Bálint,
Kálvin Tamás)
- máj.20. ?? (FK)
További lehetséges témák
(ezekre folyamatosan lehet jelentkezni):
- Párhuzamos algoritmusok/2
- ??? (lehet kérni, javasolni)