A számítástudomány alapjai

2023/24 első félév


Ez az előadás a villamosmérnök alapképzés (BSc program) VISZAA07 neptun-kód alatt szereplő, 5 kredites tárgyához tartozik. A szakot ebben a félévben kezdő hallgatók ezt az elméleti kurzust és egy hozzá tartozó gyakorlatot vegyenek fel, csakúgy mint mindenki más, aki a félév végén vizsgázni szeretne, de nincs érvényes VISZAA07 aláírása. Indul SzA-ból egy vizsgakurzus is, mégpedig azoknak, akik aláírással rendelkezek a korábban oktatott VISZAA05 tárgyból, és ennek birtokában a régi (lineáris algebra nélküli, több gráfelméletet tartalmazó) tárgyból szeretnének vizsgázni. Ehhez a vizsgakurzushoz nem tartozik gyakorlat, így ezen a kurzuson aláírás sem szerezhető, és a vizsgára hozott pontszám sem javítható. Természetesen nem tilos érvényes VISZAA05 aláírás mellett felvenni a VISZAA07 kurzust (és egy hozzá tartozó gyakorlatot). Ekkor a tárgy teljesítéséhez ismét meg kell szerezni az aláírást (az időközben módosult tananyagból), majd sikeresen levizsgázni.

A kétféle kurzushoz természetesen külön tételsorok tartoznak: egy a VISZAA05 vizsgakurzushoz, egy másik, VISZA07 tételsor pedig a jelenleg futó kurzushoz, ami a tavalyihoz képest némileg módosult.


Előadások:

Kurzuskód
Időpont
Előadó
Terem
1
kedd 8:15-10:00
kedd 17:15-18:00
Fleiner Tamás
(fleiner@cs.bme.hu)

IB028

Gyakorlatok:

Kurzuskód
Időpont
Gyakorlatvezető
Terem
11
szerda 8:30-10:00
Varga Kitti IB138
12 szerda 8:30-10:00 Kabódi László
IB139
13
szerda 8:30-10:00 Vincze András
IB140
14
szerda 8:30-10:00 Szakács Lili Kata IB145
15
szerda 10:15-11:45 Varga Kitti IB138
16 szerda 10:15-11:45 Kabódi László IB139
17
szerda 10:15-11:45 Varga Eszter Anna
IB140
18 szerda 10:15-11:45 Garami Bence
IB145
19 szerda 8:30-10:00 Fleiner Tamás IB134
I1 (IMSC)
szerda 8:30-10:00 Kaszanitzky Viktória
IB144
I2 (IMSC)
szerda 10:15-11:45 Fleiner Tamás IB134



Ütemterv:


1.hét
2023. szeptember 5.
Gráfelméleti alapfogalmak. Gráfok fokszámösszege, komponensek, utak, séták, élsorozatok, izomorfia. Fák és erdők, azok egyszerűbb tulajdonságai.
Gyakorló feladatsor
Előadás pdf
2.hét 2023. szeptember 12. Egyetemi sportnap: az előadás elmarad.
3.hét 2023. szeptember 19. Feszítőfa, alapkörrendszer (fundamentális körrendszer), fundamentális vágásrendszer. Minimális költségű feszítőfa és feszítő erdő, ezek karakterizációja, Kruskal algoritmusa. Normál fák és áramkörök egyértelmű megoldhatósága.
Gyakorló feladatsor
Előadás pdf
4.hét 2023. szeptember 26. Gráfbejárás fogalma, élek osztályozása, BFS. Legrövidebb utak és a BFS tulajdonságai, legrövidebb utak fája. Élmenti javítás, Dijkstra algoritmusa.
Gyakorló feladatsor
Előadás pdf
5.hét 2023. október 3. Ford és Floyd algoritmusai. Mélységi keresés, irányított körök keresése, aciklikus gráfok jellemzése, leghosszabb utak keresése, PERT feladat.
Gyakorló feladatsor
Előadás pdf
6.hét 2023. október 10. Euler-séta és körséta, létezésének szükséges és elégséges feltétele (összefüggő gráf esetén). Hamilton-kör és út fogalma. Szükséges, illetve elégséges feltételek Hamilton-kör létezésére: Dirac és Ore tételei ill. komponensszám pontelhagyások esetén.
Gyakorló feladatsor
Előadás pdf
7.hét
2023. október 17.
Gráf síkba, illetve gömbre rajzolhatósága. Az Euler-féle poliédertétel és következményei egyszerű, síkbarajzolható gráfokra. Kuratowski gráfok, soros bővítés, Kuratowski tétele. Síkbarajzolt gráf duálisa. Elvágó él, soros élek, vágás. A duális gráf tulajdonságai (élszám, csúcsszám, összefüggőség, kör-vágás dualitás, annak speciális esetei).
Gyakorló feladatsor
Előadás pdf

Az I. ZH anyaga eddig tart.
8.hét 2023. október 24. Lineáris egyenletrendszerek megoldása Gauss-eliminációval. Elemi sorekvivalens lépés, lépcsős alak és redukált lépcsős alak fogalma. Kapcsolat az egyenletek és ismeretlenek száma, illetve a megoldás egyértelműsége között.
Gyakorló feladatsor
Előadás pdf
9.hét 2023. október 31. Rn és Rn alterének fogalma. Lineáris kombináció, generált altér (és ennek altér volta), generátorrendszer. Lineáris függetlenség (ennek kétféle definíciója és ezek ekvivalenciája). Az újonnan érkező vektor lemmája. F-G egyenlőtlenség.
Gyakorló feladatsor
Előadás pdf
2023. november 1. Mindenszentek ünnepe, a gyakorlat elmarad.
2023. november 2. 8-10 óra I. ZH feladatok, mintamegoldás 
Terembeosztás (vezetéknév kezdőbetűje szerint):

A-D
E-I
J-Ny
O-Zs
E1A
IB026
KF76
IB028
10.hét 2023. november 7. Bázis és dimenzió fogalma, a dimenzió egyértelműsége. Standard bázis,  Rn dimenziója. Koordinátavektor fogalma és annak egyértelműsége. Bázis létezése   Rn tetszőleges alterében.
Gyakorló feladatsor
Előadás pdf
11.hét 2023. november 14. Permutáció és inverziószám. Determináns definíciója. Mátrix transzponáltja és négyzetes mátrix transzponáltjának determinánsa. A determináns alaptulajdonságai. Determináns kiszámítása Gauss-eliminációval és a kifejtési tétel segítségével.
Gyakorló feladatsor
Előadás pdf
12.hét 2023. november 20. 18-20 óra I. pótZH feladatok, mintamegoldás 
Terembeosztás (vezetéknév kezdőbetűje szerint):

A-Zs
KF51

2023. november 21. Műveletek mátrixokkal (összeadás, skalárral szorzás, szorzás, transzponálás), ezek tulajdonságai. Determinánsok szorzástétele (biz. nélkül). Lineáris leképezések.
Gyakorló feladatsor
Előadás pdf

A II. ZH anyaga eddig tart. 
13.hét 2023. november 28. Mátrix inverze, létezésének szükséges és elégséges feltétele, az inverz kiszámítása. Mátrix rangja, a rangfogalmak egyenlősége, a rang meghatározása. Kapcsolat négyzetes mátrix determinánsa, illetve a sorok és az oszlopok lineáris függetlensége között.
Gyakorló feladatsor
Előadás pdf

2023. november 30.
8-10 óra II. ZH feladatok, mintamegoldás 
Terembeosztás (vezetéknév kezdőbetűje szerint):

A-D
E-I
J-Ny
O-Zs
E1A
IB026
KF76
IB028
14.hét 2023. december 5. Kapcsolat a lineáris egyenletrendszerek, az Rn-beli generált altérhez tartozás kérdése, illetve a mátrixszorzáson alapuló mátrixegyenletek között. Az nxn-es lineáris egyenletrendszerek egyértelmű megoldhatóságának jellemzése a determináns segítségével.
Előadás pdf
Pótlási hét 2023. december 13.
10-12 óra II. pótZH feladatok, mintamegoldás 
Terembeosztás (vezetéknév kezdőbetűje szerint):

A-Zs
Q-I

A betekintés helyszínéről és időpontjáról minden gyakorlatvezető tájékoztatja a csoportját.
1. vizsgahét
2023. december 18.
10-12 óra, IB 134, konzultáció
2023. december 19. 8-10 óra, IB027, aláíráspótlás (a neptunban jelentkezni kell)

A betekintés helyszínéről és időpontjáról a helyszínen adunk tájékoztatást.

2024. január 8. 10-12 óra, IB 134, konzultáció

2024. január 15.
10-12 óra, IB 134, konzultáció

2024. január 22.
15-17 óra, IB 134, konzultáció


Jegyzetek   Szeszlér Dávid: Bevezetés a számításelméletbe 1.
                        Katona-Recski-Szabó: A számítástudomány alapjai   (Typotex 2002, 2003)

                       NESZ

Előadás videók     Az előadások után egy-két nappal a tömörített videó innen tölthető le.

Gyakorló feladatok 

Wiener Gábor:Bevezetés a számításelméletbe 1. feladatgyűjtemény
Friedl-Recski-Simonyi:
Gráfelméleti feladatok   (Typotex 2006)
A gráfelméleti részhez van egy letölthető
példatár, sőt, egy animációgyűjtemény is.
A korábbi kurzus nem tartalmazott lineáris algebrát, de a korábbi ZH-feladatok egy része segítheti a felkészülést.

2014 őszi ZH feladatok, megoldások
2015 őszi ZH feladatok, megoldások
2016 őszi ZH feladatok, megoldások
2017 őszi ZH feladatok, megoldások
2018 őszi ZH feladatok, megoldások

2019 őszi ZH feladatok, megoldások
2020 őszi ZH feladatok, megoldások
2021 őszi ZH feladatok, megoldások
2022 őszi ZH feladatok, megoldások

Lineáris algebrából készült feladatgyűjtemény az informatikusok számára, ami (részben) használható az SzA-hoz is.

Értékelés, tárgykövetelmények, vizsga

A kari vezetés rendelkezésének megfelelően a gyakorlatokon kötelező a részvétel mindazok számára, akik azt felvették. Akinek a tárgy adatlapján meghatározottnál (ebben a félévben 3-nál) több hiányzása bizonyítható, az nem szerezhet sem aláírást, sem kreditet a VISZAA07 tárgyból. Ez tehát azt jelenti, hogy hiába van érvényes aláírása valakinek, ha felveszi a gyakorlatot, és nem látogatja a foglalkozásokat, akkor nem vizsgázhat.

Zárthelyik, pótzárthelyik, aláírás

A félév során két zárthelyi (ZH) 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. A zárthelyi megírásakor az alábbi szabályok betartását követeljük meg.

Kérjük, hogy mindazon hallgatók, akikre a dolgozatíráskor speciális szabályokat kell alkalmazni, ezt legkésőbb egy héttel a dolgozatírás előtt jelezzék ezt a tárgy előadójának.

A félév végi aláírást az szerzi meg (vagyis a szóbeli vizsgára az jelentkezhet), aki az alábbi két feltételt teljesíti:

A két ZH mindegyikéhez van egy-egy pótzárthelyinek nevezett pótlási alkalom, valamint a vizsgaidőszak első hétében egy díjköteles pótlás fedőnevű újabb lehetőség. A pótzárthelyin az adott ZH-t lehet javítani vagy pótolni. Ha valaki egy korábban már megírt dolgozatot teljesít újra valamelyik pótzárthelyin, akkor az újonnan szerzett pontszáma lesz érvényes (akkor is, ha az rosszabb, mint a korábbi), azzal a kivétellel, hogy a már megírt, legalább 24 pontos ZH pontszáma nem csökkenhet 24 alá. A pótzárthelyin ugyanazt az anyagrészt kérjük számon, mint a megfelelő ZH-n és - a szándékunk szerint - a kitűzött feladatsorok egyforma nehézségűek. A kijavított ZH és pótzárthelyi dolgozatokba a dolgozatok kijavítását követő gyakorlaton betekintést biztosítunk, és jogos reklamáció esetén az elért pontszámot  módosítjuk. Később is lehetőség van a betekintésre, ám a pontszámon ekkor már nem módosítunk.

A fent említett harmadik pótlási alkalom a neptunban aláíráspótló vizsga néven jelenik meg. (Ez a név tehát némileg félrevezető, itt nem egy valódi vizsgáról van szó.) Erre az alkalomra az alábbi szabályok vonatkoznak:

Az aláíráspótló vizsgán írt dolgozatokat még aznap kijavítjuk és biztosítjuk abba a betekintést. (Ennek a pontos helyszínét és időpontját a dolgozatírás közben hirdetjük ki.) A dolgozatok eredményei (legkésőbb a következő napon) a tárgy honlapjára is felkerülnek. Aki a megtekintésen nem tud megjelenni, az a dolgozatát kérésre később is megnézheti, de ekkor már a dolgozat pontozásán nem tudunk változtatni.

Aláírások érvényessége

A tárgyból korábban szerzett aláírások a TVSZ 2019-es változása nyomán nem évülnek el, így a korábban vagy az idén szerzett aláírások (a hozzá tartozó pontszámmal) érvényesek maradnak a tanulmányok végéig.

Szóbeli vizsga

Vizsgázni csak az jöhet, aki a neptunban jelentkezett az adott vizsgaalkalomra, továbbá a vizsgára jelentkezéshez érvényes aláírással rendelkezik. Felhívjuk a figyelmet arra, hogy a neptun csak a vizsgára jelentkezett hallgatók eredményeinek a felvitelét engedélyezi, így nincs lehetőségünk olyan hallgatót vizsgáztatni, aki bármilyen okból nem szerepel a neptun által generált vizsgalapon. Ezért nagyon fontos tudni arról, hogy a neptun jelentkezések (és lemondások) a vizsgát megelőző napon 12 órakor lezárulnak. Elővizsgát nem tartunk.

A vizsga ebből a tárgyból szóbeli. A vizsga megkezdésekor a vizsgázónak kisorsolunk egy tételt a tárgyhoz tartozó (később kialakuló) vizsgatételsorból. A kisorsolt tétel kidolgozására (vagyis a szóbeli felelethez használt vázlat vagy bő jegyzet elkészítésére) legalább 40 percet biztosítunk. Ezen felkészülési idő letelte után a vizsgáztató abban az esetben is elkezdheti a vizsgáztatást, ha a hallgató még nem jelezte, hogy elkészült. A felelet abból áll, hogy a vizsgázó egyrészt a jegyzeteire támaszkodva részletesen beszámol a húzott tételben található tananyagról, másrészt a vizsgáztató néhány szúrópróbaszerű, a tananyag további részével kapcsolatos kérdésére válaszol. (A vizsga sikerességéhez tehát nem elég a kihúzott tétel ismertetése, az fent említett további kérdésekre is kell tudni válaszolni.) A szóbelin az elégséges megszerzésének elengedhetetlen feltétele, hogy a vizsgázó az anyagban szereplő minden lényeges (a tételsorban félkövéren szedett) definíciót és tételt pontosan ki tudjon mondani, illetve tudjon értelmezni.  Ugyancsak szükséges, hogy a nem vastagon szedett részek esetében is legfeljebb egy-két hiányossága legyen a vizsgázónak. Ennél több viszont nem is kell a ketteshez, azaz a tételsorban szereplő tételek bizonyításainak ismerete csak a közepes vagy jobb jegy megszerzéséhez szükséges. Ha  valaki az egyszerűbb bizonyításokat is tudja, akkor jók az esélyei a hármas szóbeli feleletre.   A négyes vagy ötös felelethez (esetleg kisebb-nagyobb segítséggel) már a nehéz bizonyításokat is el kell tudni mondani (és persze érteni is kell azokat). A vizsgán számítani kell arra is, hogy a zárthelyik által le nem fedett anyagrészből is kaphat kérdést a vizsgázó.

A vizsgajegy a két zárthelyi eredményének ill. a vizsgán nyújtott szóbeli teljesítménynek a súlyozott átlaga, amiben a zárthelyik összeredményének súlya 2, a szóbeli vizsgáé pedig 3. Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen (függetlenül a zárthelyik eredményétől). Ez a gyakorlatban azt jelenti, hogy a zárthelyik eredményei alapján egy 19 és 40 közötti "hozott pontszámot"  számítunk ki, ami a két ZH (IMSC pontok nélküli) összpontszámának 40%-a. A szóbelin nyújtott teljesítményre legfeljebb 60 pont kapható. Ha a szóbelire kapott pontszám 24-nél kevesebb, akkor a vizsgajegy elégtelen, egyébként pedig a szóbelin szerzett pontszám a szóbelire kapott pontszám 1,2-szerese, de legfeljebb 60. A vizsgajegyet a hozott pontszám és a szóbelin szerzett pontok összegéből az alábbiak szerint számítjuk : 40 és 54 pont között elégséges, 55 és 69 pont között közepes, 70 és 84 pont között jó, végül 85 és 100 pont között jeles.

Aki elégtelenre vizsgázik, az egy ízben ismétlő vizsgát tehet amennyiben a vizsgaidőszak hátralévő részében még van meghirdetett vizsgaalkalom és arra tud jelentkezni. Sikeres vizsga esetén is tehető javító vizsga. Ismétlő ill. javító vizsga esetén a zárthelyikből származó eredmények változatlan módon érvényesek. A férőhelyek függvényében további ismétlő/javító vizsgára is van lehetőség, azonban ugyanabban félévben csupán két vizsga díjmentes: a harmadik alkalomtól ez díjköteles, amit a neptun kiszámláz.  

A vizsgákat megelőző konzultáción a vizsgára való készülés közben felmerült kérdéseket lehet feltenni. A konzultációk időpontja és helyszíne a fenti ütemtervben található. A konzultáción bárki részt vehet, nem csak az, aki az éppen soron következő vizsgára jelentkezett.

A vizsgán (ebből a tárgyból) nem szükséges alkalmi viseletben megjelenni.  A hallgató (egyébként civilizált) öltözködése a vizsga  eredményét semmilyen tekintetben sem befolyásolja.

Összegyűjtöttünk néhány hasznos tanácsot a sikeres vizsgázást megkönnyítendő.

IMSC pontszámok

10-10 IMSC pontot lehet szerezni a két ZH mindegyikén a fent leírtak szerint, pótlás esetén a legutolsónak megírt dolgozatok alapján, az aláíráspótlási alkalommal már nem szerezhető IMSC pont. További 10 IMSC pont szerezhető a szóbeli vizsgán mégpedig úgy, hogy a szóbelin nyújtott teljesítményt (az esetlegesen feltett, mélyebb megértést ellenőrző kérdéseket is beleértve) legfeljebb 60 ponttal értékeljük. Ez, illetve ebből legfeljebb 50 számít a vizsgajegybe. Az 50-en felüli szóbeli pontszám IMSC pontként kerül jóváírásra azzal a megkötéssel, hogy a tárgyból szerezhető végső IMSC pontszám legfeljebb 25 lehet.

Adatellenőrzés
A vizsgát követően mindenki győződjön meg arról, hogy a neptunba helyesen került be a vizsga eredménye és a félév során esetlegesen összegyűjtött IMSC pontszáma. Tömegével kell adminisztrálnunk ezeket az adatokat, és időnként sajnos hibázunk. Azonban minél hamarabb kapunk visszajelzést, annál hamarabb tudjuk korrigálni a hibát, és ezzel elejét venni az esetleges hátrányos következményeknek.

Extra stressz!!

A következő jelenségre hívjuk fel a figyelmet. Úgyszólván minden évben előfordul, hogy a vizsga előtt a jelentkezett hallgatók egy része nem érzi magát eléggé felkészültnek, ezért átjelentkezik egy későbbi alkalomra. Sőt, ezt akár többször is megteszi. Sajnos az is megesik, hogy valaki elégtelenre vizsgázik, és ezért szeretne ismétlő vizsgát tenni. Mindennek az eredménye, hogy az utolsó 1-2 vizsgaalkalommal a létszámkorlátnál lényegesen többen szeretnének próbálkozni. Ilyenkor aztán rengeteg kérést szoktunk kapni a létszámkorlát felemelésére. Mivel a vizsgáztatók időbeosztását jó előre meg kell határoznunk és a tanszék kapacitása amúgy is véges (és nem túl nagy), ezért erre egészen biztosan nem leszünk képesek. Ennek megfelelően csak az jöhet vizsgázni, aki befér az eredeti létszámkorlátba. Aki tehát várólistán marad a vizsga kezdetére, az sajnos egyáltalán nem jöhet. (A vizsgához ugyanis időnként várólistát is készítünk, hogy a jelentkezők sorba tudjanak állni a visszalépők miatt felszabaduló helyekért. Ennek az az egyedüli célja, hogy ne kelljen azon versenyezni, ki csap le hamarabb egy visszalépés miatt hirtelen adódó lehetőségre.) Mindannyiunk érdekében kérjük azt is, hogy aki már biztosan nem fog eljönni egy alkalomra, az mihamarabb jelentkezzen le (akkor is, ha várólistán van), hogy a várólistán maradóknak minél több esélye legyen. Azért sem butaság ezt időben megtenni, mert aki feljelentkezve marad, és így igazolatlan távollétet nyer, arra a neptun pénzbüntetést szabhat ki. A jelentkezések és lemondások a vizsgát megelőző napon 12 órakor lezárulnak: az ezt követő állapot végleges. Tudjuk, hogy rém kellemetlen, ha valaki mindössze 20 órával a vizsga előtt tudja meg, hogy jöhet vagy sem az adott számonkérésre. Sajnos ez a rendszer sajátosságából adódik, így ezen nem tudunk segíteni.

Mindezek miatt tisztelettel azt javasoljuk, hogy mindenki igyekezzék már az elsőnek választott alkalomra megfelelően felkészülni. Ez talán a legfrappánsabb módszer a fentiek miatti bosszúság elkerülésére.