• Amit a kurzusról/előadásról tudni kell
• What you always wanted to know about this course
• Exam 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./ Algorithms are best understood by running them. There are several "applets" on the Internet where the running of specific algorithms is visualized. 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!/Be careful with the sources found on the internet, they may differ from the algorithm versions described in the lecture!

1. hét, Szeptember 13. / 1st week, 13th of September:

• Algoritmuselméleti alapok / Basic notions of algorithms    beamer pdf file-ja    handout file-ja
   kivetítés pdf file-ja    handout file-ja    klasszikus jegyzet pdf file-ja
• Segédanyagok/Additional materials:
  • 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 20. / 2nd week, 20th of September:

• Mohó algoritmusok / Greedy algorithms    beamer pdf file-ja    handout file-ja
   kivetítés pdf file-ja    handout file-ja
• Oszd meg és uralkodj algoritmusok / Divide and conquer algorithms    beamer pdf file-ja    handout file-ja
   kivetítés pdf file-ja    handout file-ja
• Segédanyagok/Additional materials:
  • Graham és Hell egy cikke a minimális költségű feszítőfa problmáról

3. hét, Szeptember 27. / 3rd week, 27th of September:

• Szalámi taktika/ Salami tactics    beamer pdf file-ja    handout file-ja
   kivetítés pdf file-ja    handout file-ja
• Segédanyagok/Additional materials:
  • Egy Cornell University jegyzet a medián keresésről pdf/beamer file-ja

4. hét, Október 4. / 4th week, 4th of October:

• Dinamikus programozás /Dynamic programming    beamer pdf file    handout file
   kivetítés pdf file-ja   handout file-ja
• Hálózatok, folyamok: Ford-Fulkerson-algoritmus / Flows in networks, Ford-Fulkerson algorithm    beamer pdf file    handout file
   kivetítés pdf file-ja   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
  • Ford és Fulkerson eredeti cikke
  • Ford és Fulkerson egy könyve a folyamokról (RAND corporation honlapjáról)

5. hét, Október 11. / 5th week, 11th of October :

• Edmonds-Karp-algoritmus / Edmonds-Karp algorithm    beamer pdf file    handout file
   kivetítés kivetítés pdf file-ja   kivetítés handout file-ja
• Amortizációs analízis / Amortized analysis    beamer pdf file    handout file
   kivetítés 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

6.-7. hét, Október 17--25. / 6th-7th week, 17th-25th of October: Amortizációs analízis: Fibonacci-kupacok

• Amortizációs analízis: Fibonacci-kupacok / Fibonacci heaps    beamer pdf file    handout file
   kivetítés kivetítés pdf file-ja    kivetítés handout file-ja
• 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.

8. hét, November 1./8th week, 1st of November: Mindenszentek napja / All Saints' Day

9. hét, November 8. / 9th week 8th of November: Algoritmusok/Turing-gépek definíciója

• Szótár alapú tömörítések, LZW algoritmus / Dictionary based compressions, LZW algorithm   beamer pdf file    handout file
   klasszikus jegyzet pdf file-ja
• Algoritmusok, Turing-gépek definíciója/Algorithms, definition of Turing machines   beamer pdf file    handout file
   klasszikus jegyzet pdf file-ja    kivetítés pdf file-ja    kivetítés handout file-ja
• Segédanyagok:
  • A kiszámíthatóság története, Alan Turing és Neumann János és a számítógépről szóló honlapok:  A Guardian cikk  Alan Turing  Neumann János 

10. hét, November 15. / 10th week, 15th of November:

• Bonyolultsági osztályok / Complexity classes   beamer pdf file   handout file
   kivetítés pdf file-ja    kivetítés handout file-ja
• Segédanyagok:
  • Complexity Zoo   html  pdf

11. hét, November 22. / 10th week, 22nd of November:

• Univerzális Turing-gép, nem-kiszámítható nyelvek / Universal Turing machine, undecidable languages   beamer pdf file   handout file
   kivetítés pdf file-ja   kivetítés handout file-ja
• Segédanyagok:
  • Manolis Kellis MIT honlapja 
  • Devlin's angle
  • Wikipedia oldal   eldönthetetlen problémákról

12. hét, November 30.: Nem-determinizmus, példák

• Nem-determinizmus, példák / Non-determinism, examples    beamer pdf file   handout file
   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

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

• Redukciók, teljesség    beamer pdf file   handout file
   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
  • Richard Lipton blogja a Savitch-tételről

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

• Hálózatok, P-teljes probléma, NP-teljes problémák / Circuits, a P-complete problem, NP-complete problems    beamer pdf file   handout file
   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.
  • 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.

    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.