Algoritmusok elmélete előadás


2013/2014 tavasz


Előadó

Katona Gyula Y.  (kiskat at cs.bme.hu)

Előadás: hétfő 12:15-14:00   IB028

Gyakorlatok: (a neptunban jelzett időpontokban)

A tantárgyból vizsgakurzus is van azok számára, akiknek már van aláírásuk és nem akarnak megint zh-t írni.
Vizsgakurzuson aláírást nem lehet szerezni! A jegybe korábbi félévben írt zh nem számít bele.

Követelmények

Az  előadások fontosabb témakörei.

4. Vizsga ZH pontszámok

4. VizsgaZH megtekintése, szóbeli: 2014. június 23. hétfő, 15:00-16:00, QBF10

Konzultációk

A vizsgák előtti napon konzultációt tartunk:

2014. május 28. szerda, 14:00-16:00,  QBF10
 2014.  június 4. szerda, 14:00-16:00,  QBF10
 2014. június 11. szerda, 14:00-16:00,  IB134
 2014. június 18. szerda, 14:00-16:00,  IB134

A termek a létszám függvényében változhatnak még.

Vizsgák

A terembeosztás a jelentkezők számának függvényében még valószínű változni fog menet közben, előző nap ellenőrizzétek.

2014. május 29. csütörtök, 8:15-9:55,  A-Z: IB028
 2014. június 5. csütörtök, 8:15-9:55,   A-K: IB028, L-Z: Q-I.
2014. június 12. csütörtök, 8:15-9:55,  A-Z: Q-I.
2014. június 19. csütörtök, 8:15-9:55,  ?A-K: IB028, L-Z: Q-I.?

A termek a létszám függvényében változhatnak még.

A ZH írást szereténk elkezdeni 8:10-kor, ezért kérek mindenkit, hogy addigra már legyen elhelyezkedve, minden szükséges kellékkel felszerelkezve. Mindenkinél legyenek összetűzött lapok, írószer, fényképes igazolvány. Más segédeszköz nem használható. A PPZH időtartama 100 perc, anyaga a ZH anyaggal egyezik meg.

Eredményhirdetés, esetleges szóbeli

2014. június 2. hétfő, 15:00-16:00,  QBF10
2014. június 10. kedd, 15:00-16:00,  QBF11
 2014. június 16. hétfő, 15:00-16:00,  QBF10
 2014. június 23. hétfő, 15:00-16:00,  QBF10

A termek a létszám függvényében változhatnak még.

Segédanyagok

Az alábbi anyagok lényegében a a tavalyi előadáson elhangzottakat tartalmazzák. Várhatóan kb. ez lesz idén is.
Itt inkább téma szerint vannak szétvágva előadásokra, nem feltétlen úgy, ahogy az időbe éppen belefért.
Ezért is van kevesebb rész itt, mint ahány előadás volt.

Függvények nagyságrendje, elágazás és korlátozás, dinamikus programozás (vetített változat)
Gráfok megadása, szélességi keresés és alkalmazásai (vetített változat)
Legrövidebb utak, Bellmann-Ford, Floyd, Dijkstra (vetített változat)
Kupac adatszerkezet, Dijkstra kupaccal (vetített változat)
Keresés, rendezés (vetített változat)
Bináris keresőfa, piros-fekete fa (vetített változat)
2-3 fák, B-fák (vetített változat)
Hashelés (vetített változat)
Mélységi keresés (vetített változat)
Minimális költségű feszítőfák (vetített változat)
Bonyolultságelmélet (vetített változat)
NP-teljes problémák (vetített változat)
(A bonyolultságelmélethez alább is van egy jó anyag)
Közelítő algoritmusok (vetített változat)


Algel song kottája

Kiegészítések a tankönyvhöz:

  1. Az O jelölésről

  2. Piros-fekete fák

  3. Összefoglaló BSc-seknek a P és NP osztályokról. Egy rövid előadás, a témáról ami nyelvgyakorlásnak sem utolsó.

2010 tavaszán videófelvétel készült az előadásokon és az egyik csoport gyakorlatain (Vigyázat! Semmi garancia nincs arra, hogy mindig minden ugyanúgy és ugyanakkor fog elhangzani a későbbi félévekben!)
Tankönyv
Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok (TYPOTEX).
Feladatsor (1999)
pdf(380K),   a5 füzet
ps változatok: sima (200K),   a5 formátum ,   a5 formátum lapfordítással ,   a5 füzet

Néhány ráadás feladat a nagyságrendekről
A 2013/2014/2 ZH itt, a mintamegoldása itt.
A 2011/2012/1 pótZH itt, a mintamegoldása itt.
Egy régebbi vizsga zárhelyi itt,   a mintamegoldása itt.
Egy másik régebbi vizsga zárhelyi itt,   a mintamegoldása itt. (Búr Márton megoldásai)
2013 tavaszi BSc-s zárthelyi+vizsgák:  pdf
2012 tavaszi BSc-s zárthelyi+vizsgák:  pdf
2011 tavaszi BSc-s zárthelyi+vizsgák:  pdf
2010 tavaszi BSc-s zárthelyi+vizsgák:   pdf
2009 tavaszi BSc-s zárthelyi+vizsgák:   pdf         5éves képzésbeli zárthelyi+vizsgák:   pdf
2008 tavaszi BSc-s zárthelyi+vizsgák:   pdf         5éves képzésbeli zárthelyi+vizsgák:   pdf
2007 tavaszi BSc-s zárthelyi+vizsgák:   pdf         5éves képzésbeli zárthelyi+vizsgák:   pdf
2002-2006 zárthelyi+vizsgák egyben (5 éves képzés):   ps   pdf
 
Animációk gyűjteménye    -- és ha valaki hallani is szeretné az algoritmusokat...
Algoritmusok tánclépésben:
buborék rendezés
beszúrásos rendezés
kiválasztásos rendezés 
összefésüléses rendezés
na és még egy, shell sort
A Fun with algorithms konferencia weboldala

Versenyek

Őszre: ACM programozási verseny
Játékos változat az ACM-től rövid határidővel
És ha valaki inkább programozni szeret: IBM 48 órás programozó bajnokság
Tavaszra: 24 órás programozási verseny
Egy másik verseny a tavaszi félévre
 
A legrövidebb út és más "triviális" problémák-- Implementation challenges
Modeling and Optimization verseny
Student Contest on Software Engineering (Irány Hawaii)
Vagy pl. az évente megrendezett PASCO Programming Challenge (Parallel symbolic computation), illetve gráf rajzoló verseny

Régebbi segédanyagok

A régebbi, általam tartott előadáson vetített anyagok:
2002. február 11.: eredeti pdf, nyomtatható pdf, nyomtatható PS
2002. február 12.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. február 18.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. február 25.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. február 26.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. március 4.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. március 11.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. március 12.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. március 18.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. március 25.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. március 26.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. április 9.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. április 15.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. április 22.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. április 23.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. április 29.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. május 6.: eredeti pdf, nyomtatható pdf,nyomtatható PS
2002. május 7.: eredeti pdf, nyomtatható pdf,nyomtatható PS  
 

Ezt a lapot KATONA GYULA  tartja karban.