Algoritmuselmélet (VISZAB03)



2018 tavasz

Előadás: hétfő 10:15-12; Q.I. Katona Gyula

Gyakorlat: a neptunban jelzett időpontokban és helyszíneken.

Figyelem: 2016-tól a tantárgy tematikája megváltozott! Ez a kurzus azoknak szól, akik az új BSz2 (VISZAA04 vagy VISZAA01) kurzust végezték el.

Aki a régi fajta BSz2 (VISZA110) vagy KombiGráf2 (VISZA026) kurzusokat végezte el, azoknak a korábbi tematikájú (VISZA213) kurzust kell elvégezni. (Vigyázat, az anyag sorrendje ott is változik, és így a zh anyaga is!) Ezzel a kurzussal kapcsolatos kérdésekkel Friedl Katalin tanárnőt keressétek, infomációk itt.
Ebből van is vizsgakurzus azok számára, akiknek már van aláírása és nem akarnak megint zh-t írni.

Akinek van aláírása a VISZAB01 kódú tárgyból, annak van ilyen kóddal vizsgakurzus. Ennek vizsgatematikája azonos a VISZAB03 kódú tárggyal. A vizsgajegybe bele fog számítani a régebbi ZH eredmény, de lehetőség van ebben a félévben is megpróbálkozni a ZH-val. Ez esetben az új eredmény beszámítása úgy történik, mint a pót/javítóZH esetében.

A matematikus hallgatóknak a számukra külön kiírt VISZAB01 kódú tárgyat kell felvenniük. Ehhez nem lesz külön előadás a többiekkel együtt kell járni, külön gyakorlat viszont van.


Követelmények
VISZAB03 (és VISZAB01)



Az előadások fontosabb témakörei (gyakorló feladatokkal).


Itt kísérleti jelleggel kérdéseket lehet feltenni az anyaggal kapcsolatban. A legtöbb like-ot kapó kérdéseket mindenképp megválaszolom.



Záróvizsga

Az informatikus BSc záróvizsga/MSc felvételi tematikája módosult, 2018 januárjában már az új változat szerint volt a vizsga és ebben a félévben is ez érvényes természetesen (lásd a kari honlapot).

Az algoritmusokról szóló rész tematikája itt is megtalálható.

Figyelem, ez minden vizsgázóra vonatkozik, függetlenül attól, hogy mikor, milyen változatát végezte el az Algoritmuselmélet tantárgynak. Csak egyféle feladatsor lesz!



Vizsga eredmények




A PPZH időpontja: 2018. május 24. csütörtök 12-14. Terembeosztás (VISZAB03 és VISZAB01):
mindenki az IB028-ba menjen. A PPZH-ra a NEPTUN-ban jelentkezni kell.
Megtekintés infósoknak: 2018. május 28. hétfő 14:15-15:00 IB134
Megtekintés matematikusoknak: 2018. május 29. kedd 15:00- H505

A ppZH-n javítani nem lehet, csak az jöjjön, akinek még nincs aláírása.

A PPZH anyaga is a március 19.-i előadás elején elhangzó "coNP, tanú tétel alkalmazása" anyagrészig bezárólag minden addigi témakör, a hozzá tartozó feladatokkal együtt. Formája, stílusa, értékelése a 2016 és 2017 évi ZH-khoz lesz hasonló (lásd lejjebb a linket). (Mivel ezekben az években később volt a ZH, az anyaga is tartalmaz olyat, amit most nem.)
A ZH-n 6 rendes és egy ráadás (IMSC) feladat lesz, de mindegyik feladatra mindenkinek ugyanúgy 10 pontot lehet kapni, beleértve a ráadás feladatot is. Az aláírás megszerzéséhez 24 pontot kell elérni, 51 ponttól pedig már jeles szintnek felel meg.

A ZH-t összetűzött lapokra kell írni, mindenki hozzon magával lapokat lehetőleg összetűzve. Mivel a ZH-t a gyakorlatvezetők javítják, a gyakorlatvezető nevét is fel kell majd írni a dolgozatra, ez ne érjen senkit váratlanul.




Vizsga

Vizsga Dátum Terembeosztás Konzultáció Megtekintés, szóbeli Probléma esetén
1. vizsga 2018.05.31 A-K → Q.I. és L-Z → IB028 2018.05.30 14:15 IE220 2018.06.04 14:00 IE220 Friedl Katalin friedl@cs.bme.hu
2. vizsga 2018.06.07 A-L → Q.I. és M-Z → IB028 2018.06.06 14:15 IE220 2018.06.11 14:00 QBF13 Friedl Katalin friedl@cs.bme.hu
3. vizsga 2018.06.14 A-L → Q.I. és M-Z → IB028 2018.06.13 14:15 IB134 2018.06.18 14:00 IE217-1 Csima Judit csima@cs.bme.hu
4. vizsga 2018.06.21 mindenki IB028 2018.06.20 14:15 IB134 2018.06.25 14:00 IE217-1 Katona Gyula kiskat@cs.bme.hu

VISZA213 kurzus hallgatói mindig az IB028-ban menjenek megírni a dolgozatot.
Matematikus hallgatóknak a megtekintés, szóbeli a fenti időpontokban lesz, de a H505 teremben.



Segédanyagok

Tankönyv
Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok (TYPOTEX).
Kiegészítések a tankönyvhöz:
  1. Mintaillesztés
  2. Az O jelölésről
  3. Véges automaták
  4. Környezetfüggetlen nyelvtanok
  5. Veremautomaták
  6. Turing-gépek
  7. Piros-fekete fák

A régi tárgyhoz készült fóliák is használhatók a többi anyagrészhez: itt

A 2017-es zh és a vizsgák feladatsorai
A 2016-os zh és a vizsgák feladatsorai

Feladatsor (1999) (nagyrészt a régi anyaghoz)
pdf(380K), a5 füzet

Korábbi zh-k és vizsgák amik most már csak kevés támpontot adnak
2015 2014 2013 2012 2011 2010 2009 2008 2007
5éves képzés: 2009 2008 2007 2006-2002



Lehetséges folytatások közül néhány:

– automaták → Nyelvek és automaták VISZMA04 (Info MSc közös tárgy)
– algoritmusok → Algoritmusok és bonyolultságuk (VISZMA00 info MSc specializáció tárgy vagy VISZM031 matek MSc),
Rendszeroptimalizálás (VISZMA02 info MSc Felsőbb matek tárgy vagy VISZM117 matek MSc)
– fordítók → Fordítóprogramok a gyakorlatban VIAUAV33 (választható tárgy)


Java animációk (Salamon Gábor gyűjtése), lásd még itt is -- é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
na és még egy, shell sort

Vers a megállási probléma eldönthetetlenségéről

A dalok bonyolultságáról

Egy igazi Turing-gép

A természetes nyelvek bonyolultságáról :)


A Fun with algorithms konferencia weboldala

Versenyek

Őszre: ACM programozási verseny
És ha valaki inkább programozni szeret: 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
Vagy pl. az évente megrendezett gráf rajzoló verseny
Na és persze: topcoder és code jam