Algoritmuselmélet és bonyolultságelmélet

2017 Tavasz

Tananyagok

1. hét

Szeptember 5.: Algoritmuselméleti alapok, dinamikus programozás
Szeptember 7.: 1. feladatsor: Alapok, dinamikus programozás

2. hét

Szeptember 12.: Javítgatásos algoritmusok, mohó algoritmusok, példák, folyamok: Az előadás jegyzete (Csuma-Kovács Rita jegyzete)
- Ford és Fulkerson eredeti cikke
- Ford és Fulkerson egy könyve a folyamokról (RAND corporation honlapjáról)
Szeptember 14.: 2. feladatsor: Javítgatásos algoritmusok, folyamok

3. hét

Szeptember 19.: Folyam algoritmusok: Ford-Fulkerson, Edmonds-Karp, Dinic: Az előadás jegyzete
- Dinitz egy cikke saját algoritmusáról

4. hét

Szeptember 26.: Amortizációs analízis: példák, Fibonacci-kupac I: Az előadás jegyzete
- Robert Tarjan eredeti, 1985-ös cikke az amortizált analízisről
- Kevin Wayne princeton-i honlapjára feltett oldal a Fibonacci heap-ekről
- Robert Endre Tarjan kiemelkedő díjai

5. hét

Október 3.: Fibonacci-kupac II.: Az előadás jegyzete, kódolás

6. hét

Október 10.:
- Adattömörítés,
- Számelméleti algoritmusok I.: Az előadás jegyzete
Október 12.: 3. feladatsor: Kupacok

7. hét

Október 17.: Számelméleti algoritmusok II.: Az előadás jegyzete
- Az AKS algoritmus wikipedia oldala
- A 2016-os Fulkerson-díj méltatása
Október 19.: I. Zh

8. hét

Október 24.: Turing-gép: Az előadás jegyzete
- Java szimulációk Turing-gép programozásra: I II
- A Wikipedia Turing-gépről szóló oldala
- Alan Turing életéről és munkájáról szóló honlapok: I II
Október 26.: 4. feladatsor: Turing-gépek

9. hét

Október 31.: Bonyolultsági osztályok: Az előadás jegyzete
- Nemcsak azok az osztályok léteznek, amiket bevezettünk: Egy egész állatkert létezik:
- Scott Aaronson - The Complexity Zoo html oldal pdf file
- Greg Kuperberg (Mathematics Department at UC Davis) kiegészítés
- Allender, Loui, Regan cikk

10. hét

November 7.: Nem-determinizmus: Az előadás jegyzete
- Wikipedia oldal a nem-determinisztikus algoritmusokról nem-determinisztikus Turing-gépről
- Floyd eredeti cikke, amelyben a nem-determinizmus fogalmát bevezeti
- Honlapok a P?NP millenniumi problémáról Clay Mathematics Institute Cook cikke The New Yorker wikipedia
November 9.: 5. feladatsor: Bonyolultsági osztályok

11. hét

November 14.: Univerzális Turing-gép, megállási probléma (olvasmány: példák): Az előadás jegyzete, Redukció, teljes problémák Az előadás jegyzete
- Az Univerzális Turing-gép, Neumann János és a számítógépről szóló honlapok: Manolis Kellis MIT honlapja The Guardian cikk Computing history Devlin's angle
- Wikipedia oldal eldönthetetlen problémákról
- A redukció fogalma a wikipedia szerint

12. hét

November 21.: NP-teljesség: Az előadás jegyzete
- Cook eredeti cikke.
- Cook méltatása mint a Turing-díj nyertese (1982).
- Leonid Levin wikipedia oldala
- A Knuth-díj 2012. évi nyertesének - Leonid Levin-nek - méltatása.
- Egy Caltech előadás jegyzet a Cook-Levin-tételről
- Két Harvard jegyzet: első, második NP-teljességről.
- A wikipedia listája NP-teljes problémákról
- Karp eredeti cikke, amely az NP-teljes problémák sorát elindította.
- Egy Pierluigi Crescenzi és Viggo Kann által gondozott online lista NP-teljes problémákról.
- Jeff Erickson az University of Illinois at Urbana-Champaign algoritmuselméleti kurzusának NP-teljességi órájához adott anyaga

13. hét

November 28.: L
- Richard Lipton blogja a Savitch-tételről
- Az 1995-ös Gödel-díj indoklása
- Jerrum Sinclair egy előadás jegyzete az Immerman-Szelepcsényi tételről
- Lance Fortnow blogjának Immerman-Szelepcsényi bejegyzése
November 30.: II. Zh

14. hét

December 5.: Véletlen algoritmusok és osztályaik: Az előadás jegyzete
December 7.: A félév lezárása

Ha az előadással, gyakorlattal kapcsolatban bármilyen kérdés, megjegyzés, vélemény stb. felmerül, akkor azokat az hajnal@math.u-szeged.hu email címen érdeklődve várom.