Csima Judit csoportjának feladott feladatok a feladatgyűjtemény szerinti számozással

1. gyakorlat (február 18.)

Órán megoldottuk: Rendezés 5, 44, 2, 29a, kupacos rendezéssel rendeztük az 1,6,5,3,7,4 számokat, összefésüléssel rendeztük az 1,8,27,2,13,5,7,4 számokat

HÁZI: 18, 27, 37, 10, 20 (ezek lesznek a pótgyakon is majd még)
 
 
1. pótgyakorlat (február 25.)

Órán megoldottuk: Rendezés 18, 27, 37, 10

gyakorolni: 20, 30, 38, 9, 39, 21
 
  2. gyakorlat (március 3.)

Az óra elmaradt nyílt nap miatt. Az ide tartozó anyag a következő heti pótgyakon, március 10-én került csak elő.
 
  2. pótgyakorlat (március 10.)

Órán megoldottuk: egy bináris fa 3-féle konkrét bejárása, 4. fejezet (Keresőfák): 19, 7, 15, 3, 9, 21; 6. fejezet (hash): 5, 7
 
  3. gyakorlat (március 17.)

Órán megoldottuk: 7. fejezet (Gráfok): 27c, 27d, 2, 14, 19, 33
Házinak maradt: 23, 7
Még gyakorolni: 5, 35, 24, 37, 6, 16
 
  3. (pót)gyakorlat (március 24.)

Órán megoldottuk: 7. fejezet (Gráfok): 27ab+ Boruvka is,32, 7, 23, 28
Még gyakorolni: 5, 21, 46, 35, 24
 
  4. gyakorlat (március 31.)

Órán megoldottuk: 8. fejezet (Turing-gépek): 1ab, 5,6
Még gyakorolni: 14, 7, 18
 
  4. pótgyakorlat (április 7.)

Órán megoldottuk: R=coR, R=RE metszet co RE, 8. fejezet (Turing-gépek): 14
Még gyakorolni: 18, 7, 8, 9, 10, 11
 
  5. gyakorlat (április 14.)

Órán megoldottuk: 8. fejezet (Turing-gépek): 16, 18, 23, 8 és
9. fejezet (Bonyolultsági osztályok): 15
Még gyakorolni: 8/17, 19, 7, 9, 10, 11, 21 és 9/12
 
  5. pótgyakorlat (április 21.)

Órán megoldottuk: P része PSPACE-nek, EXPTIME része R-nek, P=coP
9. fejezet (Bonyolultsági osztályok): 25
Igaz-e, hogy ha L1 RE-beli és L2 P-beli, akkor a metszetük RE-beli?, R-beli?, P-beli?
P része NP, 3-SZIN NP-beli, Euler-körrel rendelkező gráfok nyelve P-beli, NP-beli, coNP-beli, Prímszámok nyelve coNP-beli
Még gyakorolni: 9/26, 6 és
Igaz-e, hogy ha L1 P-beli, L2 PSPACE-beli, akkor a metszetük R-beli?, PSPACE-beli?, EXPTIME-beli?

6. gyakorlat (április 28.)

Órán megoldottuk: 3-SZIN visszavezetése 4-SZIN-re, MAXFTLEN visszavezetése MAXKLIKK-re, kSZIN NP-teljességének belátása, ha k legalább 4,
9. fejezet (Bonyolultsági osztályok): 39
Bizbe, hogy az összetett számok nyelve Karp-redukálható a H nyelvre!
9/ 61, 62 (csak az ötleteket beszéltük meg)
Még gyakorolni: 9/58

6. pótgyakorlat (május 5.)

Órán megoldottuk: 9/ 61, 62
Ha NP nem egyenlő coNP, akkor MAXKLIKK nincs P-ben (lásd be ezt)
9/41
P-ben van-e vagy NP-teljes azon súlyozott élű gráfok nyelve, melyekben van két olyan pont, melyek távolsága nagyobb, mint 100
Még gyakorolni: 9/58, 27, 37, 28

7. gyakorlat (május 12.)

Órán megoldottuk: 8/ 25a, 28, 32
Bináris fában keressünk lineáris időben leghosszabb utat.
Egy súlyozott csúcsú bináris fában keressük meg lineáris időben a maximális súlyú független ponthalmaz súlyát. (Minden csúcshoz van rendelve egy súly és olyan ponthalmazt keresünk, aminek pontjai függetlenek és amelynek összsúlya maximális.)