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!