3. csoport: páros hét, szerda, IB.140, 10:15 -- 12:00
6. csoport: páros hét, szerda, IB.138, 15:15 -- 16:45
Pótgyakorlat: minden páratlan héten a fenti helyszínen.
A gyakorlatokra hozd magaddal kinyomtatva a példatárat!
Letölthető a tárgy honlapjáról,
illetve kicsinyített formában kétoldalas nyomtatáshoz
PS,
PS.GZ és
PDF-ben.
ZH és pótZH eredmények már nem elérhetőek. Aki a pótZH dolgozatát meg szeretné nézni, írjon e-mailt az fd kukac cs.bme.hu címre május 20-ig. Utána az eredmények véglegesek.
Ha bármi kérdésed van a tárgyról, feladatokról vagy másról, írj az fd kukac cs.bme.hu címre!
| Gyakorlat dátuma | Gyakorlat témája | Elhangzott példák példatári sorszáma | Gyakorolni | |
| 1. | 2004. február 18. | Technika, rendezés:Ordo,Omega,Teta, legkisebb elem keresése, bináris keresés, rendezés | Technika/2b,2d, Rendezés/17,4,24,44,21 | Rendezés/29a,5,6,10, Keresés/2c |
| 1. pót | 2004. február 25. | Rendezés: Ládarendezés, radix, kupac | 29a, 14, 37, 38, 30, n elem közul az elso k legnagyobb megtalálása O(n log(k)) időben. | 39, 40, 49, 36, 39, 47 |
| 2. | 2004. március 3. | ELMARAD! | ||
| 2. pót | 2004. március 10. | Keresőfák | 3, Biz. be, hogy egy bináris keresőfa építéséhez Omega(n log n) idő szükséges; 6, 15, 26, 20, 7, 8, 9 | 29, 23, 24, 32, 5 |
| 3. | 2004. március 17. | Hash, legrövidebb utak, mélységi és szélességi bejárás | Hash:6,7 Gráfok: 2,4,14,15,16 | 12,20,3,6,25 |
| 3. pót | 2004. március 24. | Szélességi bejárás, DAG, min. fesz. fa | 18,7,8,5,28, alagut hidas min.fesz.fa | 23,27a-d,39,31 |
| 4. | 2004. március 31. | Turing-gép fogalma | ZH feladatok, Turing-gép/1 | |
| 4. pót | 2004. április 7. | Turing-gép: rekurzív, rekurzíve felsorolható nyelvek | 6,5,14 | 15,24 |
| 5. | 2004. április 14. | Turing gép: nehéz problémák, nem rekurzív(e felsorolható) nyelvek | 24,7,8;Biz be, hogy azon x#y párokból alkotott nyelv nem rekurzív, ahol x egy T-gép leírása, y pedig egy input, aminek hatására a T-gép valamikor azt írja az utolsó szalagjára, hogy alma. ; 15 | 9,16,17,19,10 |
| 5. pót | 2004. április 21. | Bonyolultsági osztályok. Polinomiális-exponenciális algoritmusok, NP, coNP, tanú-tétel | Bonyolultsági osztályok: 2,4,8; Bizonyos nyelevekrol (Hamilton-k variánsai) igazoljuk az NP (coNP)-beliséget.; Mutassunk exponenciális algo.-t H-kör keresésére. | 9,12,15,16,25 |
| 6. | 2004. április 28. | Karp-redukció, NP-teljesség | 12, 53, 37, 36 | |
| 6. pót | 2004. május 5. | NP-teljesség | 58,62,61,55, Biz.be,hogy 4FTLEN problémára van polinomiális algo | 60,54 |
| 7 | 2004. május 12. | Spec. eset P-beli vagy NP-teljes, Dinamikus programozás, Közelíto algo., Kolmogorov bonyolultság | Bonyolultsági osztályok: 40, 43; Tuing-gép: 25a, 28, 25b | Bonyolultsági osztályok: 39, 46, 42; Turing-gép: 28, 26, 25c,25d |
Tárgy honlapja követelmények, régi ZH-k, vizsgák, információk.
Infosite-algel közelmúlt vizsgái és ZH-i.
Java animációk gyujteménye algoritmusok szemléltetése kis példákon
(Salamon Gábortól).