A számítástudomány alapjai

2022/23 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 vizsgakurzushoz, egy másik pedig az új VISZAA07-hez, ami részleteiben a félév végére alakul ki.


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
Nguyen Hai
IB138
12 szerda 8:30-10:00 Szakács Lili Kata
IB139
13
szerda 8:30-10:00 Vékássy Áron
IB140
14
szerda 8:30-10:00 Vidor Sára
IB145
15
szerda 10:15-11:45 Nguyen Hai IB138
16 szerda 10:15-11:45 Szakács Lili Kata
IB139
17
szerda 10:15-11:45 Vékássy Áron
IB140
18 szerda 10:15-11:45 Drótos Márton
IB145
I1 (IMSC)
szerda 8:30-10:00 Varga Kitti
IE218
I2 (IMSC)
szerda 10:15-11:45 Fleiner Tamás IE218

Az előadások és gyakorlatok látogatásakor is be kell tartani az egyetem területén érvényes járványügyi szabályokat.


Ütemterv:


1.hét
2022. szeptember 6.
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
Előadás videó 1. rész
Előadás videó 2. rész
2.hét 2022. szeptember 13. 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
Előadás videó 1. rész
Előadás videó 2. rész
2022. szeptember 14. Egyetemi sportnap: a gyakorlatok elmaradnak.
3.hét 2022. szeptember 20. 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
Előadás videó 1. rész
Előadás videó 2. rész
4.hét 2022. szeptember 27. 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
Előadás videó 1. rész
Előadás videó 2. rész
5.hét 2022. október 4. 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
Előadás videó 1. rész
Előadás videó 2. rész
6.hét 2022. október 11. 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
Előadás videó 1. rész
Előadás videó 2. rész

Az I. ZH anyaga eddig tart.
7.hét
2022. október 18.
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
Előadás videó 1. rész
Előadás videó 2. rész
8.hét 2022. október 25. 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
Előadás videó 1. rész
Előadás videó 2/1. rész (sajnos a felvétel csak hanganyagként használható: az előadás diasorát érdemes mellette megnyitni)
Előadás videó 2/2. rész
9.hét 2022. november 1. Mindenszentek ünnepe, az előadás elmarad.
2022. november 3. 8-10 óra I. ZH feladatok, mintamegoldás 
Terembeosztás (vezetéknév kezdőbetűje szerint):

A
B-I
J-M
N-Zs
IB027
IB028
IB026
Q-I

10.hét 2022. november 8. 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
Előadás videó 1. rész
Előadás videó 2. rész
11.hét 2022. november 15. 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
Előadás videó 1. rész
Előadás videó 2. rész

12.hét 2022. november 21. 18-20 óra I. pótZH feladatok, mintamegoldás 
Terembeosztás (vezetéknév kezdőbetűje szerint):

A-T
U-Zs
Q-I
IB 026

2022. november 22. 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
Előadás videó 1. rész
Előadás videó 2. rész

A II. ZH anyaga eddig tart. 
13.hét 2022. november 29. 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. Az nxn-es lineáris egyenletrendszerek egyértelmű megoldhatóságának jellemzése a determináns segítségével.
Gyakorló feladatsor
Előadás pdf
Előadás videó 1. rész
Előadás videó 2. rész


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

A
B-I
J-M
N-Zs
IB027
IB028
IB026
Q-I
14.hét 2022. december 6. 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. Kapcsolat négyzetes mátrix determinánsa, illetve a sorok és az oszlopok lineáris függetlensége között.
Pótlási hét 2022. december 14.
II. pótZH, (helyszín, pontos időpont még nem dőlt el) feladatok, mintamegoldás
1. vizsgahét
2022. december 19. konzultáció (??)
2022. december 20.
aláíráspótlás, (helyszín, pontos időpont még nem dőlt el)
3. vizsgahét


4. vizsgahét




5. vizsgahét




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

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

A lineáris algebrához 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 (a jövőben, amikor már nem első alkalommal fut ez a kurzus) azt (fogja) jelenti, hogy hiába van érvényes aláírása valakinek: ha felveszi a gyakorlatot, de 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 aláíráspótló vizsga 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.

Korábban szerzett aláírások

A tárgyból korábban szerzett aláírások a TVSZ 2019-es változása nyomán nem évülnek el, ám ebből a tárgyból nem lehetett korábban aláírást szerezni. Viszont a most 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. Érdemes bölcsen élni ezzel a lehetőséggel, hiszen ha valaki ugyanazon tárgyból hat vizsgán is elégtelen eredményt ér el, azt az egyetem tanulmányi okból kötelezően elbocsátja. 

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 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.