• Amit a kurzusról tudni kell
• Tematika/Mintavizsga/Vizsgakérdések
• Az algoritmusok futásukon keresztül érthetők meg legjobban. Az interneten több "applet" is található ahol konkrét algoritmusok futása vizualizált. Egy ilyen lap. Az interneten talált forrásoknál vigyázni kell, eltérések lehetnek az előadáson leírt algoritus változatoktól!

1. hét, Szeptember 8.:Algoritmuselméleti alapok

• Alapok    klasszikus jegyzet pdf file-ja    kivetítés pdf file-ja    kivetítés handout file-ja
• Segédanyagok:
  • Egy NYT cikk Donald Knuth-ról
  • Egy cikk Donald Knuth könyveiről, Bill Gates-ről és másokról
  • Bill Gates (tudtommal) egyetlen tudományos cikke algortimuselméleti cikk

2. hét, Szeptember 15.: Mohó algoritmusok: Kruskal, szélességi keresés, Dijkstra-algoritmus

• Mohó algoritmusok    kivetítés pdf file-ja    kivetítés handout file-ja
• Segédanyagok:
  • Graham és Hell egy cikke a minimális költségű feszítőfa problmáról

3. hét, Szeptember 22.: Rekurzió: Szalámi taktika,

• Szalámi technika: Bináris keresés, medián keresés
• Segédanyagok:
  • Egy Cornell University jegyzet a medián keresésről pdf/beamer file-ja

4. hét, Szeptember 29.: Rekurzió: Oszd meg és uralkodj, Dinamikus programozás

• Oszd meg és uralkodj   kivetítés pdf file-ja   kivetítés handout file-ja
• Dinamikus programozás   kivetítés pdf file-ja   kivetítés handout file-ja
• Segédanyagok:
  • Egy CMU előadás jegyzete a dinamikus programozásról
  • Egy könyvfejezet az M.I.T.-ról a dinamikus programozás témájáról
  • Egy Stanford egyetemi előadás jegyezete a dinamikus programozásról

5. hét, Október 6.: Dinamikus programozás, Javítgatásos algoritmusok, folyamok

• Dinamikus programozás   kivetítés pdf file-ja   kivetítés handout file-ja
• Hálózatok, folyamok, Ford-Fulkerson-algoritmus   kivetítés pdf file-ja   kivetítés handout file-ja
• Segédanyagok:
  • Ford és Fulkerson eredeti cikke
  • Ford és Fulkerson egy könyve a folyamokról (RAND corporation honlapjáról)

6. hét, Október 13.: Folyam algoritmusok, Amortizációs analízis

• Edmonds-Karp-algoritmus (sokkal részletesebb mint előadáson volt)   kivetítés pdf file-ja   kivetítés handout file-ja
• Amortizációs analízis    kivetítés pdf file-ja    kivetítés handout file-ja
• Segédanyagok:
  • Dinitz egy cikke saját algoritmusáról (amiről nem volt szó az előadáson)
  • Robert Endre Tarjan   eredeti, 1985-ös cikke   az amortizált analízisről

7-8. hét, Október 20-27.: Amortizációs analízis (folytatás): Fibonacci-kupacok

• Segédanyagok:
  • Robert Endre Tarjan és Friedman eredeti (1987-es) cikke a Fibonacci-kupacról.
  • Egy stanfordi jegyzet a Fibonacci-kupacokról.
  • Kevin Wayne princeton-i honlapjára feltett előadás jegyete a Fibonacci-kupacokról.
  • Egy cikk a megvalósítás gyorsaságáról. (Forrás: arXiv)
  • Robert Endre Tarjan kiemelkedő díjai
  • A Fibonacci-sorozat az On-line Encyclopedia of Integer Sequences/OEIS -ben.

9. hét, November 3.: Kódolás

• Kódolások, LZW tömörítés Az előadás jegyzete

10. hét, November. 10: Algoritmusok/Turing-gépek definíciója

• Algoritmusok/Turing-gépek definíciója    klasszikus jegyzet pdf file-ja    kivetítés pdf file-ja    kivetítés handout file-ja
• Segédanyagok:
  • 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

11. hét, November 17.: Példák, Univerzális Turing-gép, nem-kiszámítható nyelvek

• Példák, Univerzális Turing-gép, nem-kiszámítható nyelvek    kivetítés pdf file-ja    kivetítés handout file-ja
• Segédanyagok:
  • Wikipedia oldal eldönthetetlen problémákról

12. hét, November 24.: Nem-determiniszmus, példák

• Nem-determiniszmus, példák    kivetítés pdf file-ja    kivetítés handout file-ja
• Segédanyagok:
  • 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
  • Richard Lipton blogja a Savitch-tételről

13. hét, December 1.: Redukciók, teljesség

• Redukciók, teljesség    klasszikus jegyzet pdf file-ja    kivetítés pdf file-ja    kivetítés handout file-ja
• Segédanyagok:
  • A redukció fogalma a wikipedia szerint

14. hét, December 8.: Hálózatok, P-teljes probléma, NP-teljes problémák

• Hálózatok, P-teljes probléma, NP-teljes problémák    klasszikus jegyzet pdf file-ja    kivetítés pdf file-ja    kivetítés handout file-ja
• Segédanyagok:
  • 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.
  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.

    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.