Algoritmusok és bonyolultságuk 

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

2023 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! Kétségek, kérdések esetén keressenek meg!

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: Az előadásra való felkészülést az alábbiak szerint kell ütemezni:
Az előadás kitűzött időpontja előtt

Ezeknek időpontját minden esetben az órán vagy emailen előre egyeztessük. Kérem, az ütemezéséhez vegyék azt is figyelembe, hogy az oktató sem ér rá mindig :(


Időpont: Cs 10:15-12   és 14:15-16, IB134

Mikor mi történik:
  1. márc.2.
    • Megbeszélés, osztozkodás a témákon, időpontokon.
    • P és NP között, Ladner-tétel   (Matek) -- FK
  2. márc.9.
    • Kvantumalgoritmusok/1 -- FK
    • Kvantumalgoritmusok/2 -- FK
  3. márc.16.
    • Kommunikációs bonyolultság/1 -- Kárpáti Márk, Szabó Gergő, Bindics Boldizsár
    • Zárkózottság   (Matek) -- Vastag Emese, Medgyes Csaba, Marits Márton
  4. márc.23.
    • On-line algoritmusok -- Telbisz Csanád, Somorjai Márk, Fuchs Gábor
    • Paraméteres bonyolultság/1 -- Kiss Ádám, Majthény-Wass Józsué, Bárkányi Csaba
  5. márc.30.
    • Elosztott algoritmusok/1: vezetőválasztás -- Tárnok Márton, Polyik Péter, Keceli-Mészáros Tivadar
    • Döntési fák   (Matek) -- Kássa Kristóf Péter, Hamdi Fatma, Kovács Bálint
  6. ápr.6. - tavaszi szünet
  7. ápr.13.
    • Paraméteres bonyolultság/2 -- Miszlai Domonkos, Gergály Anna, Mészáros Péter
    • A polinomiális hierarchia   (Matek) -- Virsinger Dominika, Vlaszov Artúr, Köller Donát
  8. ápr.20.
    • Elosztott algoritmusok/2: vannak hibák... -- Matyasi Lilla, Belkacemi Nordin, Bánfi Zsombor
    • Párhuzamos algoritmusok/1 -- Szász Matej, FK
  9. ápr.27.
    • Erős összefüggőség -- Somorjai Márk, Fuchs Gábor, Telbisz Csanád
    • Orákulumos Turing-gépek   (Matek) -- FK
  10. máj.4.
    • Mintaillesztő heurisztikák-- Keceli-Mészáros Tivadar, Polyik Péter, Tárnok Márton
    • Kommunikációs bonyolultság/2 -- Belkacemi Nordin, Bánfi Zsombor, FK
  11. máj.11.
    • Interaktív protokollok -- Szabó Gergő, Kárpáti Márk, Medgyes Csaba
    • Gráfok és trükkök   (Matek) -- Matyasi Lilla, Vastag Emese, Marits Márton
  12. máj.18.
    • Szerkesztési távolság -- Miszlai Domonkos, Mészáros Péter, Gergály Anna
    • Boole-hálózatok bonyolultsága -- Kássa Kristóf Péter, Hamdi Fatma, Kovács Bálint
  13. máj.25.
    • Párhuzamos algoritmusok/2 -- Kiss Ádám, Steltzer Soma, Bindics Boldizsár
    • On-line algoritmusok/2 --   (Matek) -- Virsinger Dominika, Vlaszov Artúr, Köller Donát
  14. jún.1.
    • Tárbonyolultság -- Szász Matej, Majthény-Wass Józsué, Bárkányi Csaba,
    • Félávzárás


A félév végi felmérés eredménye:

- minden téma kapott szavazatot (azaz mindegyikhez volt valaki, aki érdekesnek találta)
- 1. díj: Online algoritmusok
- 2. díj: Kommunikációs bonyolultság
- 3. díj: Párhuzamos algoritmusok + Paraméteres bonyolultság

A matekos előadásoknál: 1. díj: Gráfok és trükkök + Zárkózottság

A felidézett eredmények között legtöbbször az Erős összefüggőségbeli egyik algoritmus szerepelt

Gratulálok az érintett előadóknak!



Friedl Katalin, BME   VIK   SZIT