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

 
  7. gyakorlat (május 17.)

Órán megoldottuk:
7/28ab, 8/25a

HÁZI:
7/32, 28, 21; 9/40, 41, 8/28, 32
 
  6. pótgyakorlat (május 10.)

H, 3-SZIN, Euler-körös gráfok nyelve NP-beli, Prímszámok nyevle coNP-beli
9/36, 61, 62 található.
 
  6. gyakorlat (május 3.)

Órán megoldottuk:
P része PSPACE-nek, EXPTIME része R-nek, P=coP,
Igez-e, hogy ha L1 P-beli, L2 pedig PSPACE-beli, akkor a metszetuk a) R-beli, b) PSPACE-beli, c) EXPTIME-beli
9. fejezet 26.
 
  5. pótgyakorlat (április 26.)

Ezen az órán konzultáció volt, hozott feladatokkal. Egy feladatnál nem teljesen helyesen mondtam el a megoldást, a feladat és a megoldása is itt található.
 
  5. gyakorlat (április 19.)

Órán megoldottuk:
Hash: 5
Gráfok: 27c,d, 2, 19

HÁZI:
Hash 7,4 Gráfok: 14, 23, 5, 6
 
  4. pótgyakorlat (április 12.)

Órán megoldottuk:
Turing gépek: 14, 10
Bizonyítsuk be, hogy L benne van coRE-ben, ha L azon Turing gépek kódjait tartalmazza, amik nem fogadnak el semmit.
Igaz-e, hogy L_1 és L_2 metszete mindig RE-beli (R-beli) ha tudjuk, hogy L_1 RE-ben, L_2 pedig R-ben van?
HÁZI:
Turing gépek 11
 
  4. gyakorlat (április 5.)

Órán megoldottuk:
Turing gépek: 7, 6 vége (ami a múltkor kimaradt), 8

HÁZI:
14, 10, 11
 
 
3. pótgyakorlat (március 29.)

Órán megoldottuk:
Milyen lehet a fa alakja, ha a piros-fekete fában az egy szinten levő csúcsok egyszínűek?
Keresőfák 15, 9, 3
Rendezés 38
HÁZI:
Keresőfák 1, 6, 16, 12, 17
 
  3. gyakorlat (március 22.)

Órán megoldottuk:
Rendezés: 2
Kupacos rendezés az 1,6,5,3,7,4 elemek beszúrásával és mintörjével
Binkerfa építés a 8, 6, 10, 2, 7, 9, 10, 11, 12 elemekből, majd ezen a fán pre-, in- és posztorder bejárás, majd törlés: 7, 10, 8
Piros-fekete fa építés az 1,2,3,4,5,6 elemekből
2-3 fa építés a D,B,E,A,C,F elemkből
Rendezés 29a, 37

HÁZI:
Milyen lehet a fa alakja, ha a piros-fekete fában az egy szinten levő csúcsok egyszínűek?
Kupacos rendezés az 5,4,3,2,1 elemek beszúrásával és mintörjével
Binkerfa építés a 7, 10, 8, 5, 3, 2, 1 elemekből, majd ezen a fán pre-, in- és posztorder bejárás, majd törlés: 1, 5, 7
Piros-fekete fa építés az 7, 8, 2, 10, 5, 6 elemekből
2-3 fa építés a 10, 8, 3, 7, 12, 4 elemkből
 
 
2. pótgyakorlat (március 15.)

Elmaradt március 15 miatt.
 
2. gyakorlat (március 8.)

Órán megoldottuk:
Turing-gép: 1, 5 és 6-ból a metszetes és uniós kérdések

HÁZI:
A 6-ból a maradék.
 
 
1. pótgyakorlat (március 1.)

Órán megoldottuk:
Igaz-e, hogy ha f=Omega(g) és g=Omega(h), akkor f=Omega(h)?

A Rendezés részből: 20, 10, 9, 18,

Ha tudjuk, hogy az A algo n hosszú bemeneteken O(n^2) lépést tesz, akkor előfordulhat-e, hogy
minden n hosszú bemeneten O(n) lépést tesz?

HÁZI:
Előfordulhat-e (ha tudjuk, hogy az A algo n hosszú bemeneteken O(n^2) lépést tesz), hogy egy x bemeneten 10|x|^2 log|x|-800 lépést tesz? (Ahol |x| az x bemenet hossza.)

Rendezésből: 27
 
 
1. gyakorlat (február 22.)

Órán megoldottuk:
Technika 2a;

Ha G egy öfő gráf, n csúccsal és legalább egy éllel (élek száma e), akkor ha egy algoritmus O(n+e) lépést tesz, akkor az is igaz, hogy O(e)-t tesz

Igaz-e, hogy ha f=O(g) és g=O(h), akkor f=O(h)?

Az alábbi függvények közül melyekre teljesül, hogy f=O(g)? A függvények: 11n^2, 8n^2 logn, n^2+10000

A Rendezés részből: 3, 5, 44

HÁZI:
Igaz-e, hogy ha f=Omega(g) és g=Omega(h), akkor f=Omega(h)?

Rendezésből: 20,

Rendezni buborékkal, beszúrásosan és összefésülve az 1, 27, 3, 12, 8, 31, 5, 2 sorozatot.