Számítástudomány alapjai hatvani előadás és gyakorlat 2022 ősz
Követelmények:
A félév során kettő zárthelyi lesz. Mindkét zárthelyi 90 perces és hat darab, egyenként 10 pontot érő feladatból áll. A zárthelyin 50 pont megszerzése jelent 100%-os teljesítményt. Aki ennél is többet ér el, annak az 50 pont feletti részt IMSC pontokban írjuk jóvá. A zárthelyikre osztélyzatot nem adunk, hanem az azokon szerzett összpontszámot konvertáljuk aláírásra ill. számítjuk be a vizsgajegybe.
Az aláírás megszerzésének a feltétele, hogy mindkét zárthelyin külön-külön 24 pontot érjetek el. Mindkét zárthelyihez tartozik külön-külön egy pótlási alkalom, illetve különeljárási díj fejében a pótlási héten harmadik alkalommal is megkísérelhető valamelyik zárthelyi teljesítése. Ezen alkalmak egyelőre nem szerepelnek a menetrendben, igény esetén ezek idejét egyeztetjük. A végső jegybe a zhk eredméyne 40%-kal, a szóbeli vizsga eredméyne 60%-kal számít bele.
Vizsga:
Vizsga tudnivalók. A vizsgán használt tételsor itt található.
Menetrend:
Hét |
Időpont |
Külön tudnivaló |
Feladatsor |
Segédanyag |
1. |
szeptember 10. |
|
1. hét |
Gráfelméleti alapfogalmak. Gráfok fokszámösszege, komponensek, élsorozatok, séták, utak, izomorfia. Fák és erdők egyszerűbb tulajdonságai. Feszítőfa és ennek létezése tetszőleges összefüggő gráfban. |
2. |
szeptember 16. |
|
2. hét |
Alapkörrendszer, minimális költségű feszítőfa, Kruskal algoritmusa, normál fák. |
3. |
szeptember 24. |
|
3. hét |
Gráfbejárás fogalma, élek osztályozása, BFS. Legrövidebb utak és BFS tulajdonságai. Legrövidebb utak fája. Élmenti javítás. Dijkstra algoritmusa. Ford algoritmusa, Floyd algoritmusa. |
4. |
szeptember 30. |
|
4. hét |
Mélységi keresés. Irányított körök keresése. Aciklikus gráfok jellemzése. PERT feladat és algoritmus a megoldására. |
5. |
október 8. |
|
5. hét |
Euler-séta és körséta, létezésének szükséges és elégséges feltétele. Hamilton-kör és út fogalma, Dirac és Ore tételei, szükséges feltétel Hamilton-kör létezésére. |
6. |
október 14. |
|
6. hét |
Gráf síkba illetve gömbre rajzolhatósága, Euler-féle poliédertétel, Kuratowski gráfok, Kuratowski tétele. |
7. |
október 22. |
1. ZH |
7. hét |
Lineáris egyenletrendszerek megoldása Gauss-eliminációval. Kapcsolat az egyenletek és ismeretlenek száma, illetve a megoldás egyértelműsége közöttt. (Fleiner Tamás diasora) |
8. |
október 28. |
|
8. hét |
R^n, altér, lineáris kombináció, generált altér, lineáris függetlenség, újonnan érkező vektor lemmája. |
9. |
november 5. |
|
9. hét |
F-G egyenlőtlenség. Bázis és dimenzió. Standard bázis. R^n dimenziója, koordinátavektor. Bázis létezése R^n tetszőleges alterében. |
10. |
november 11. |
1. pótZH |
|
|
11. |
november 19. |
|
10. feladatsor |
Permutáció inverziószáma, Determináns és alaptulajdonságai, Determináns kiszámíta Gauss-eliminációval, Kifejtési tétel. Transzponált determinánsa. |
12. |
november 25. |
|
11. feladatsor |
Mátrixműveletek és ezek tulajdonságai. Determinánsok szorzástétele. Lineáris leképezések |
13. |
december 3. |
2. ZH |
12. feladatsor |
Mátrixok inverze, létezésének szükséges és elégséges feltétele. Az inverz kiszámítása. Rangfogalmak és ezek egyenlősége |
14. |
december 9. |
PótZH azoknak akit érint |
13. feladatsor |
Kapcsolat a lineáris egyenletrendszerek, az R^n-beli generált altérhez tartozás kérdése illetve a mátrixszorzáson alapuló mátrixegyenletek között. |
További segédanyagok
Rengeteg gyakorló feladat az 1. zhra készüléshez, Katona-Recski-Szabó könyv régi kiadásából.
A lineáris algebrás részhez pedig itt találtok jegyzetet és példákat a 2. zhre készüléshez.
További információk a tárgyhonlapon találhatóak. Vigyázzunk, az ütemezés a budapesti diákokra vonatkozik!