Algoritmuselmélet (VISZAB03)

2020 tavasz


Kvízek:



  • Akinek nem sikerült eddig megszereznie az aláírást, az a pótlási héten még  javíthat Neptunos jelentkezés mellett. Kiírunk  a Neptunban egy házi feladat pótlást  május  25-én reggel 8 órára, ekkorra kiteszünk egy új, két feladatból álló feladatsort a Teamsben a jelentkezett hallgatók számára. A megoldásokat a Teamsbe kell feltölteni május 27., szerda 14 óráig, visszajelzést is itt fognak kapni május 28., csütörtök reggel 8 óráig.  Ha valakinek kérdése van a javítással kapcsolatban, akkor azt május 28. délután 14 óráig teheti meg  úgy, hogy ír a Teamsben nekem (Csima Judit) vagy emailben a csima@cs.bme.hu címre.
  • A pótházival megszerezhető maximum 20 pont a legrosszabb heti házi pontjait váltja ki, a másik öt feladatsor pontja marad. Az így kapott összpontszámnak kell elérnie a 40-et.
A vizsgákat a Moodle-ben fogjuk tartani az alábbi szabályok szerint:
1. vizsga:
2. vizsga:
  • konzultáció: június 10., szerda, 14-16
  • vizsga: június 11., csütörtök 8-10
  • megtekintés várhatóan: június 12., péntek 12-14

3. vizsga:

  • konzultáció: június 12., péntek 14-16
  • vizsga: június 15., hétfő, 12-14
  • megtekintés várhatóan: június 16., kedd 14-16
4. vizsga:
  • konzultáció: június 17., szerda, 14-16
  • vizsga: június 18., csütörtök 8-10
  • megtekintés várhatóan: június 19., péntek 12-14

5. vizsga:

  • konzultáció: június 19., péntek 14-16
  • vizsga: június 22., hétfő, 12-14
  • megtekintés várhatóan: június 23., kedd 14-16

6. vizsga:

  • konzultáció: június 26., péntek 14-16
  • vizsga: június 29., hétfő, 12-14
  • megtekintés várhatóan: június 30., kedd 14-16


Az előadás fontosabb témakörei itt elérhetőek (hétről hétre frissül). A címszavak nagyjából az alább található segédanyagok megfelelő részeit jelentik, ezektől nem tervezek   jelentősen eltérni (ha mégis, akkor szólok). Az előadás anyaga az, ami az órán elhangzik.

A gyakorlatokon használt feladatsorok:


1. gyakorlat (nagyságrendek: ordó, omega, theta és mintaillesztés), megoldások, Kvíz a nagyságrendekről
2. gyakorlat (véges automata, reguláris nyelv) megoldások
3. gyakorlat (mi nem reguláris nyelv, reguláris kifejezés, CF nyelvtan) megoldások
4. gyakorlat (egyértelmű CF nyelvtan, veremautomata) megoldások
5 heti. gyakorlat (CF nyelvtanból PDA; Turing-gép) megoldások
6 heti. gyakorlat (Turing-gép, TG kódolása, diagonális nyelv) megoldások
7. heti gyakorlat (P, NP, coNP) megoldások
8. heti gyakorlat (Karp-redukció) megoldások
9. heti gyakorlat (NP-teljesség) megoldások
10. heti gyakorlat(NP-teljesség még mindig és EP)  megoldások
11. heti gyakorlat (Dinamikus programozás) megoldások
12. heti gyakorlat (DP még mindig és keresés, rendezés) megoldások
13. heti gyakorlat  (Rendezés, bináris keresőfa) megoldások
14, heti gyakorlat (2-3 fa, hash) megoldások

Beadandó házik:
 
1. feladatsor (ordó és PDA, kitűzve március 30, beadandó április 6., 14:00) megoldások
2. feladatsor (véges automata, Turing-gép, beadandó április 13., 14:00) megoldások
3. feladatsor (nem reguláris nyelv, reguláris kifejezés) megoldások
4. feladatsor (mintaillesztés, NP) megoldások
5. feladatsor (CF nyelvtan egyértelműsége, NP-teljesség), megoldások
6. feladatsor (CF nyelvtan, EP) megoldások



Segédanyagok: 

Tankönyv:
Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok (TYPOTEX). Link a Typotex oldalára (ahol a könyv online olvasható)

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

  1. Mintaillesztés
  2. Az O jelölésről és fóliák erről
  3. Véges automaták
  4. Környezetfüggetlen nyelvtanok
  5. Veremautomaták
  6. Turing-gépek
  7. NP-teljes problémák
  8. Lineáris és egészértékű programozás
  9. Elágazás és korlátozás, dinamikus programozás
  10. Közelítő algoritmusok
  11. Keresés, rendezés
  12. Keresőfák
  13. Piros-fekete fák
  14. 2-3-fák
  15. Hash (vödrös és nyitott címzésű)

Korábbi zh-k, vizsgák

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


Záróvizsga

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


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)


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
És még kettő: topcoder és code jam

Csima Judit, BME   VIK   SZIT