Algoritmusok elmélete előadás


2014/2015 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.

Eredmények

Szerdai vizsga: Sajnos nem számítottunk arra, hogy a hallgatók több mint a fele fog jelentkezni a most következő vizsgára, így némi nehézséget fog jelenteni a lebonyolítás. Azt reméljük, hogy sikerül kijavítani a dolgozatokat csütörtökön legkésőbb 11-ig. Ha van, aki semmiképp nem jönne a pénteki vizsgára amúgy sem, az kérjük írja rá a dolgozatra ,,Pénteken nem jövök". Ezeket akkor ráérünk még aznap estig kijavítani. Az eredmények folyamatosan kerülnek fel a fenti linkre. Akinek megvan az eredmény, az annak megfelelően jelentkezzen le ill. fel a pénteki vizsgára. (Ha valakinek a szoros határidő miatt nem sikerül, akkor ezt majd megoldjuk utólag. Nekünk egyszerűbb, ha valaki nincs feljelentkezve, és utólag kell feltenni, mint fordítva. Ezért kérünk mindenkit, feleslegesen ne jelentkezzen fel. Aki szerdán írt, és nem sikerült, az mindenképp jöhet pénteken, ha van még szabad vizsgaalkalma.)

A szerdai dolgozatok kiosztása továbbra is péntek 14 órától lesz, tehát a pénteki vizsga után. Ez annak jelent igazából problémát, akinek a pontszáma kevés lett, de utólag sikerült reklamálással 32 fölé kerülni. Kérek mindenkit, hogy akinek kevés a pontszáma a táblázatban, írja meg a vizsgát pénteken, ha utólag mégis sikerül a szerdain reklamálással javítani, akkor az fog számítani, a pénteki nem. (A tapasztalatok szerint ez nagyon kevés hallgatót érint, tőlük nagyon elnézést kérek, nincs jobb ötletem.)

Konzultációk

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

2015. május 26. kedd, 14:00-16:00 IB134
2015. június 9. kedd, 14:00-16:00 IB134
2015. június 16. kedd, 14:00-16:00,  IB134
2015. június 18. csütörtök, 14:00-16:00,  IE217.1

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.

2015. május 27. szerda, 12:15-13:55  A-Z: EIB
2015. június 10.
szerda, 12:15-13:55  A-O: IB028, P-Z: IB027.
2015. június 17.
szerda, 12:15-13:55A-K: IB028, L-S: IB027, Sz-Z: IE007.
2015. június 19. péntek,
12:15-13:55A-Z: IB028.

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

A ZH írást szereténk elkezdeni 12:15-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 vizsga időtartama 100 perc, anyaga a  teljes félévi anyag.

Eredményhirdetés, esetleges szóbeli

2015. május 29. péntek, 14:00-15:00,  QBF10
2015. június 12.
péntek, 14:00-15:00QBF10
2015. június 19.
péntek14:00-15:00,  QBF10
2015. június 22. hétfő, 
14:00-15:00IB134

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

Követelmények

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



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)
2014 tavaszi BSc-s zárthelyi+vizsgák:  pdf
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.