Bevezetés a Számításelméletbe 1
2021/2022. első félév


Aktuális:

Vetítés a polinomiális algoritmus fogalmáról (a 2. előadásról)




Online anyagok:

Előadásvideók (MS Stream, edu.bme.hu belépéssel nézhetők): BSz1 előadások. A felvételek a 2020. őszi órákon készültek.

Online jegyzet

Online feladatgyűjtemény

Gyakorlat példasorok: 1. gyakorlat, 2. gyakorlat,


COVID-19 információk:

A BME koronavírus-helyzettel kapcsolatos aktuális tájékoztatója itt található, a VIK oktatásszervezési információi pedig itt.

Bármely információ, mely ezen a honlapon megjelenik, visszavonásig érvényes (különösen igaz ez az előadások és gyakorlatok rendjére és a számonkérések módjára). Természetesen igyekszünk a hallgatókat a lehető leghamarabb tájékoztatni minden fejleményről. Kérjük a hallgatókat, hogy a honlapot rendszeresen figyeljék.

A BSz1 tárgyat koronavírussal kapcsolatos intézkedések pillanatnyilag nem érintik. Azok, akik bármely okból nem tudnak az órákon megjelenni, készülhetnek az előadásvideók, az online jegyzet, a gyakorlatok feladatsorai és az online feladatgyűjtemény segítségével (ld. feljebb).


Előadások, előadók:

Előadó:
Időpont:
Helyszín:
Szeszlér Dávid (email: szeszler_KUKAC_cs.bme.hu)
Szerda 8.15 - 10.00
IB028
Wiener Gábor (email: wiener_KUKAC_cs.bme.hu)
Szerda 8.15 - 10.00
E1B


Gyakorlatok, gyakorlatvezetők:

Kurzuskód:
Gyakorlatvezető:
Időpont:
Helyszín:
11
Szabó Réka (email: szabo_KUKAC_cs.bme.hu)
Kedd, 8:15-9:45
IB139
12
Kabódi László (email: kabodil_KUKAC_gmail.com)
Kedd, 8:15-9:45
E306cd
13
Kiss Attila (email: ttkkissat_KUKAC_gmail.com)
Kedd, 8:15-9:45
IB140
14
Richlik György (email: richlik_KUKAC_szit.bme.hu)
Kedd, 8:15-9:45
IB145
15
Lakatos Dorina Petra (email: dorinapetra_KUKAC_gmail.com)
Kedd, 8:15-9:45
IB146
16
Papp László (email: lazsa88_KUKAC_gmail.com)
Kedd, 8:15-9:45
IB147
17
Kertész Gergő Csaba (email: kerteszcsgergo_KUKAC_gmail.com)
Kedd, 8:15-9:45
E407
18
Varga Kitti (email: vkitti_KUKAC_math.bme.hu)
Kedd, 10:15-11:45
IB138
19
Szabó Réka (email: szabo_KUKAC_cs.bme.hu)
Kedd, 10:15-11:45
IB139
20
Kiss Attila (email: ttkkissat_KUKAC_gmail.com)
Kedd, 10:15-11:45
IB140
21
Richlik György (email: richlik_KUKAC_szit.bme.hu)
Kedd, 10:15-11:45
IB145
22
Wiener Gábor (email: wiener_KUKAC_cs.bme.hu)
Kedd, 10:15-11:45
IB147
23
Szeszlér Dávid (email: szeszler_KUKAC_cs.bme.hu)
Kedd, 10:15-11:45
IB146
24
Csonka Bence (slenhortag_KUKAC_gmail.com)
Kedd, 10:15-11:45
R517
25
Drótos Márton (email: drotos_KUKAC_cs.bme.hu)
Kedd, 10:15-11:45
E402
26
Telbisz Csanád (email: csanadtelbisz_KUKAC_edu.bme.hu)
Kedd, 8:15-9:45
E306ab
27
Zalavári Márton (email: zalavarm_KUKAC_gmail.com)
Kedd, 10:15-11:45
E401
28
Tőri Tünde (email: tori.tunde_KUKAC_gmail.com)
Kedd, 8:15-9:45
E405
I1 (IMSc)
Kaszanitzky Viktória (email: kaszanitzky_KUKAC_cs.bme.hu)
Kedd, 8:15-9:45
IB138
I2 (IMSc)
Varga Kitti (email: vkitti_KUKAC_math.bme.hu)
Kedd, 8:15-9:45
IE219
I3 (IMSc)
Wiener Gábor (email: wiener_KUKAC_cs.bme.hu)
Kedd, 8:15-9:45
IE218
E1 (Emelt)
Szeszlér Dávid (email: szeszler_KUKAC_cs.bme.hu)
Kedd, 8:15-9:45
IB134

Az emelt szintű gyakorlatot olyan érdeklődő hallgatóknak ajánljuk, akik nehezebb feladatok megoldására vágynak; az ide járók számára a zh és minden egyéb követelmény a többiekével azonos. Aki szívesen járna ide, de az időpont nem megfelelő neki, az keresse meg valamelyik előadót e-mailben vagy az előadás szünetében.

A gyakorlatokra az előadók minden héten készítenek feladatsort, a gyakorlatvezetők jelentős része ezeket (is) használja az óráján.

1. gyakorlat, 2. gyakorlat,


Segédanyagok:

Jegyzet:

A tárgyhoz készült digitális jegyzet letölthető innen: http://cs.bme.hu/bsz1/jegyzet

Kérjük szépen, hogy aki a jegyzetben hibát talál (legyen az akár csak egy apró elírás vagy egy félreérthető, pontatlan fogalmazás) az ezt jelezze a szeszler_KUKAC_cs.bme.hu emailcímen. A segítséget előre is köszönjük!

Feladatgyűjtemény:

A tárgyhoz készült, megoldásokat is tartalmazó feladatgyűjtemény letölthető innen: http://cs.bme.hu/bsz1/feladatgyujtemeny

Kérjük szépen, hogy aki a feladatgyűjteményben hibát talál (legyen az akár csak egy apró elírás vagy egy félreérthető, pontatlan fogalmazás) az ezt jelezze a wiener_KUKAC_cs.bme.hu emailcímen. A segítséget előre is köszönjük!

Figyelem! A kari mérnökinformatikus alapképzés 2014. őszétől átalakult és megújult, ez a Bevezetés a számításelméletbe 1 tárgyat is jelentős mértékben érintette. Az átalakulás azzal is járt, hogy a tárgy oktatása során keletkezett, 2014-nél korábbi segédanyagok (jegyzetek, feladatsorok, zárthelyi dolgozatok) nem illeszkednek a megújult anyaghoz. Ezért azt javasoljuk mindenkinek, hogy ne, vagy csak nagyon korlátozott mértékben és kritikával használjon minden, a 2014/2015-ös tanévnél korábbról származó, a BSz1-hez készült segédanyagot; könnyen előfordulhat, hogy ezek inkább hátráltatnák, mint segítenék a tárgy tanulásában. (A fenti jegyzet és feladatgyűjtemény természetesen már a megújult tárgyhoz illeszkedik.)


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

Zárthelyik, pótzárthelyik:

A félév során két zárthelyi dolgozatot íratunk, mindkettőben 6 darab 10 pontot érő feladat lesz. Ezek közül az utolsó a többinél (szándékaink szerint) valamivel nehezebb, csillaggal jelölt feladat. A félév végi aláírást az szerzi meg (vagyis a vizsgára az jelentkezhet), aki az alábbi feltételek mindegyikét teljesíti:
A két zárthelyi alkalom mellett lesz még egy pótzárthelyi alkalom, továbbá egy második pótzárthelyi alkalom is. Az első pótzárthelyi alkalmat fel lehet használni az elmulasztott zárthelyik valamelyikének teljesítésére vagy egy korábban megírt dolgozat eredményének a javítására. A második pótzárthelyi alkalom ugyanezen célokra használható, de csak akkor, ha a hallgató addigra az aláírást még nem szerezte meg. Ha valaki egy korábban már megírt dolgozatot teljesít újra valamelyik pótzárthelyin, akkor mindenképpen az új pontszáma lesz érvényes - akkor is, ha az rosszabb, mint a korábbi. Ez alól egy kivétel van: a már megszerzett aláírást és az adott zh-n a megszerzéséhez tartozó minimális pontszámot egy balsikerű javítási kísérlettel nem lehet elveszíteni. Ha valaki egy pótzárthelyin megjelenik (és a feladatsort átveszi), azt úgy tekintjük, hogy az illető kísérletet tett a dolgozat megírására (és így rá a fenti feltételek vonatkoznak).

A pótzárthelyiken mindenki szabadon eldöntheti, hogy az első vagy a második zárthelyit kívánja pótolni vagy javítani; annak sincs akadálya, hogy valaki mindkét pótzárthelyin ugyanannak a dolgozatnak a pótlását vagy javítását kísérelje meg.

Az első pótzárthelyire nem szükséges jelentkezni a Neptunban (sem máshol), azon mindenki a saját döntése szerint részt vehet (függetlenül attól, hogy a dolgozatot pótlási vagy javítási szándékkal írja meg).

Ha valaki a két normál zárthelyivel (tehát pótlás nélkül) sikeresen teljesítette az aláírás feltételeit és (a TVSz biztosította jogával élve) mindkét zárthelyi eredményét még a szorgalmi időszakban javítani kívánja (és így erre az első pótzárthelyi alkalom nem elegendő), az keresse meg (emailben vagy személyesen) a tárgy valamelyik előadóját legkésőbb egy héttel az első pótzárthelyi időpontja előtt.

A zárthelyik eredménye beszámít a tárgyból kapott végső jegybe, ennek a részleteit lásd alább.

Díjköteles pótlás:

A fentebb említett második pótzárthelyi alkalom a Neptunban díjköteles pótlás néven jelenik meg. Erre a második pótzárthelyi alkalomra vonatkozó szabályok az alábbiakban különböznek az elsőre vonatkozóktól:
A díjköteles pótlás időpontja (körülbelül a szorgalmi időszak közepétől) a Neptunból deríthető ki. A díjköteles pótláson írt dolgozatokat még aznap kijavítjuk és biztosítjuk a megtekintésüket. A megtekintés pontos időpontját és helyszíné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 a dolgozat pontozásán változtatni már nem tudunk (kivéve természetesen a pontszámok téves összeadásából vagy adminisztrációs hibából adódó eseteket).

Korábbi félévben szerzett aláírás:

Azok, akik egy korábbi félévből aláírással rendelkeznek és ebben a félévben is a reguláris előadást és gyakorlatot (tehát nem a vizsgakurzust) vették fel, megkísérelhetik újból megírni a zárthelyiket abból a célból, hogy a korábbi zárthelyik eredményein javítsanak. Erre az esetre az alábbi feltételek vonatkoznak:
Ha egy aláírással rendelkező hallgató az aktuális félévben legalább egy zárthelyin megjelenik, azt úgy tekintjük, hogy az illető kísérletet tett az aláírás feltételeinek újbóli teljesítésére (és rá a fenti feltételek vonatkoznak, mindkét zárthelyi tekintetében). Ellenkező esetben a legutolsó olyan félévbeli teljesítményt vesszük figyelembe, amikor a hallgató megkísérelte az aláírás feltételeinek teljesítését.

Vizsga:

Vizsgára az jelentkezhet, aki aláírással rendelkezik.

A vizsga szóban zajlik, az alábbiak szerint: a tételsoron szereplő tételek közül a vizsgázó egyet kap, ezt kidolgozza (vagyis a szóbeli felelethez egy bő jegyzetet készít, ehhez legalább 45 perc áll rendelkezésére), majd szóban felel belőle. A felelet abból áll, hogy egyrészt a vizsgázó a jegyzeteire támaszkodva részletesen beszámol a húzott tételről, másrészt a vizsgáztató néhány szúrópróbaszerű, az anyag tö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 imént említett további kérdésekre is kell tudni válaszolni.) A vizsgán az elégséges megszerzésének feltétele, hogy a vizsgázó a tételsorban vastagon szedett definíciókat, tételeket, algoritmusokat el tudja mondani és értse is azokat. Természetesen a tételsor nem vastagon szedett részeit is tudni (és érteni) kell, ezek esetében azonban egy-két hiányosság még nem okoz bukást.

A vizsgajegyet a két zárthelyi eredményéből és a vizsgán nyújtott szóbeli teljesítményből alakítjuk ki az alábbi módon. Mindkét zárthelyin és a szóbeli vizsgán is 60 pontot lehet elérni. Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen (függetlenül a zárthelyik eredményétől). Ellenkező esetben a következő képletet használjuk:

végső_pont = 0,4*(min(50,zh1) + min(50,zh2)) + 1,2*min(50,v),

ahol zh1 és zh2 az első, illetve második zárthelyin, v pedig a szóbeli vizsgán szerzett pontszám. A végső jegy a végső pontszám alapján: 0-39: elégtelen, 40-54: elégséges, 55-69: közepes, 70-84: jó, 85-100: jeles.

Javító vagy ismétlő vizsga a TVSz szerint tehető. Javító vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek.

A tárgyhoz tartozó 2019-es tételsor (ez jobban hasonlít majd az ideire, mint a 2020-as) letölthető innen. A tényleges, friss tételsor a félév végén lesz elérhető.

Figyelem! A vizsgákra a Neptunban jelentkezni kell. Mivel 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 a jelentkezést elmulasztotta.

A vizsgán (ebből a tárgyból) nem szükséges alkalmi ruhában megjelenni, ez a vizsga eredményét semmilyen mértékben nem befolyásolja.

További jótanácsok a vizsgára való felkészüléshez itt olvashatók.

IMSc pontok:

Az IMSc pontokat az alábbi képlettel számítjuk ki (ahol zh1 és zh2 ismét az első, illetve második zárthelyin, v pedig a szóbeli vizsgán szerzett pontszám (legfeljebb 60)).

IMSc_pont = min(25, max(0,zh1-50) + max(0,zh2-50) + max(0,v-50)).

Az IMSc pontok a vizsgaeredményekkel együtt kerülnek be a Neptunba. Kérünk mindenkit, hogy ellenőrizze, hogy a Neptunban nyilvántartott IMSc pontszáma megfelel a valóságnak és amennyiben eltérést tapasztal, azt a lehető leghamarabb jelezze a SzIT tanszéki adminisztrációján a boltizar_KUKAC_cs.bme.hu emailcímen.

Technikai tudnivalók a vizsgákkal kapcsolatban:


Zárthelyik:


Első zárthelyi:
október 28. (csütörtök)
8:00 - 10:00
Második zárthelyi:
december 2. (csütörtök)
8:00 - 10:00
Első vagy második (de nem mindkét) zárthelyi pótlása:
december 13. (hétfő) A pótzh-k anyaga azonos a megfelelő zh-k anyagával.


Pótpótzh (a Neptunban jelentkezni kell rá!):
december 20. (hétfő)




A zárthelyiken a megoldások indoklásakor csak az előadásokon elhangzott tételekre és állításokra (és persze a középiskolában tanult, az alapszintű anyagba tartozó ismeretekre) lehet bizonyítás nélkül hivatkozni. Az, hogy a kérdéses tétel vagy állítás az anyagnak az adott zh-hoz tartozó részében vagy máshol szerepel, nem számít.
Mindenkinek sok sikert kívánunk!

Technikai tudnivalók a zárthelyik lebonyolításával kapcsolatban:

Mindenkinek sok sikert kívánunk!

A zárthelyikre való felkészüléshez használható a tárgyhoz tartozó feladatgyűjtemény és a korábbi évek zárthelyi feladatsorai (az ott részletezett szempontok figyelembevételével). Természetesen figyelni kell arra, hogy az egyes tanévekben változhat az anyag sorrendje vagy a dolgozatok időpontja, ezért a zárthelyik anyaga nem azonos; értelemszerűen olyan feladatokat érdemes keresni, amelyek az épp aktuális zárthelyi anyagához tartoznak.


Korábbi félévek zárthelyi feladatsorai és pontozási útmutatói (2020 őszén a vírushelyzet miatt csak egy zh-t írattunk):

A fentebb írtak szerint a 2014. őszi félévinél korábbi zárthelyi dolgozatok nem, vagy csak részben illeszkednek a tárgyhoz. Ennek ellenére, alább elérhetővé tesszük a 2010. és 2013. közötti évek zárthelyi dolgozatait is - azonban felhívjuk a figyelmet arra, hogy ezeket csak az utánuk írtak figyelembevételével érdemes használni.
A 2010. és 2013. közötti évekből az első zárthelyik (és az ezekhez tartozó első és második pótzárthelyik) feladatai jórészt változtatás nélkül használhatók. A csak kisebb változtatással, vagy egyáltalán nem használható feladatok az alábbiak:
2013. október 24.: A 2. feladatban "U tetszőleges vektortér" helyett Rn egy U altere értendő.
2013. december 9., első pótzárthelyi: A 2. feladatban "V vektortér" helyett Rn egy V altere értendő.
2013. december 17., első pótzárthelyi: A 2. feladat elhagyandó, a 3. feladatban "V vektortér" helyett Rn értendő.
2012. október 18.: A 3. feladatban "V tetszőleges vektortér" helyett Rn egy V altere értendő.
2012. december 3., első pótzárthelyi: Mindegyik feladat használható.
2012. december 11., első pótzárthelyi: A 2. feladat elhagyandó, a 3. feladatban "V vektortér" helyett Rn értendő.
2011. október 20.: A 2. feladat elhagyandó, a 3. feladatban "V vektortér" helyett Rn egy V altere értendő.
2011. december 5., első pótzárthelyi: A 2. feladat elhagyandó, a 4. feladatban "V tetszőleges vektortér" helyett Rn egy V altere értendő.
2011. december 13., első pótzárthelyi: A 2. feladatban "V vektortér" helyett Rn egy V altere értendő, a 3. feladatban "V vektortér" helyett V=Rn (és annak egy W altere) értendő.
2010. október 21.: A 2. és 6. feladat elhagyandó, a 3. feladatban "V tetszőleges vektortér" helyett V=Rn értendő.
2010. december 6., első pótzárthelyi: A 2. feladatban "V vektortér" helyett V=Rn (és annak egy W altere) értendő, az 5. és 6. feladatok elhagyandók.
2010. december 15., első pótzárthelyi: A 2., 5. és 6. feladatok elhagyandók.
A 2011. és 2013. közötti évekből a második zárthelyi dolgozatokból (és az ezekhez tartozó első és második pótzárthelyikből) a feladatok egy része változtatás nélkül használható. A csak kis változtatással, vagy egyáltalán nem használható feladatok az alábbiak:
2013. november 28.: A 4. feladat szövegéből "a szokásos bázisban" rész törlendő. Az 5. feladatban a transzformáció sajátértéke, sajátvektora helyett a transzformáció mátrixának sajátértéke, ill. sajátvektora értendő. A 6. feladat elhagyandó.
2013. december 9., második pótzárthelyi: A 4. feladat szövegéből "a szokásos bázisban" rész törlendő. Az 5. feladatban a transzformáció sajátértéke, sajátvektora helyett a transzformáció mátrixának sajátértéke, ill. sajátvektora értendő. A 6. feladat elhagyandó.
2013. december 17., második pótzárthelyi: A 4. és 5. feladatban a transzformáció sajátértéke, sajátvektora helyett a transzformáció mátrixának sajátértéke, ill. sajátvektora értendő. A 6. feladat elhagyandó.
2012. november 22.: A 4. feladatban a transzformáció sajátértéke, sajátvektora helyett a transzformáció mátrixának sajátértéke, ill. sajátvektora értendő. Az 5. és 6. feladat elhagyandó.
2012. december 3., második pótzárthelyi: Az 5. és 6. feladat elhagyandó.
2012. december 11., második pótzárthelyi: A 3. feladatban a transzformáció sajátértéke, sajátvektora helyett a transzformáció mátrixának sajátértéke, ill. sajátvektora értendő. Az 5. és 6. feladat elhagyandó.
2011. november 24.: A 3., 5. és 6. feladatok elhagyandók.
2011. december 5., második pótzárthelyi: A 3., 5. és 6. feladatok elhagyandók.
2011. december 13., második pótzárthelyi: A 3. és 4. feladatban "V vektortér" helyett Rn (és annak egy lineáris transzformációja) értendő, a 4. feladatban a transzformáció sajátértéke, sajátvektora helyett a transzformáció mátrixának sajátértéke, ill. sajátvektora értendő. Az 5. és 6. feladat elhagyandó.

Hasznos linkek: