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


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

Előadó:
Időpont:
Helyszín:
Pach Péter Pál (email: ppp_KUKAC_cs.bme.hu)
Hétfő 10.15 - 12.00
IB027
Szeszlér Dávid (email: szeszler_KUKAC_cs.bme.hu)
Hétfő 10.15 - 12.00
IB028


Gyakorlatok, gyakorlatvezetők:

Kurzuskód:
Gyakorlatvezető:
Időpont:
Helyszín:
11
Marx Pál Fülöp (email: palfulop95_KUKAC_gmail.com)
Szerda, 12:15-13:45
IB138
12
Drótos Márton (email: marton.drotos_KUKAC_sztaki.hu)
Szerda, 12:15-13:45
IB139
13
Dücső Márton (email: ducsom_KUKAC_gmail.com)
Szerda, 12:15-13:45
IB140
14
Szabó Dávid (email: dzsabo_KUKAC_cs.bme.hu)
Szerda, 12:15-13:45
R508
15
Horváth Ákos (email: horvath.akos1997_KUKAC_gmail.com)
Szerda, 12:15-13:45
IB146
16
Varga Rudolf (email: vrudolf.vr_KUKAC_gmail.com)
Szerda, 12:15-13:45
IB147
17
Richlik György (email: richlik_KUKAC_szit.bme.hu)
Szerda, 12:15-13:45
E404
18
Szeszlér Dávid (email: szeszler_KUKAC_cs.bme.hu)
Szerda, 12:15-13:45
E405
19
Kutas Péter (email: kutasp_KUKAC_gmail.com)
Szerda, 12:15-13:45
E406
20
Pintér József (email: jozsikamk_KUKAC_gmail.com)
Kedd, 8:15-9:45
IB147
21
Almási Nóra (email: almasinori_KUKAC_gmail.com)
Kedd, 8:15-9:45
IB139
22
Salyámosy András (email: salyamos_KUKAC_gmail.com)
Kedd, 8:15-9:45
IB140
23
Ács Bernadett (email: acsbernadett_KUKAC_gmail.com)
Kedd, 8:15-9:45
IB145
24
Fleiner Zsófia (email: fleiner.zsofia_KUKAC_gmail.com)
Kedd, 8:15-9:45
IB146
25
Richlik György (email: richlik_KUKAC_szit.bme.hu)
Kedd, 8:15-9:45
E404
26
Kutas Péter (email: kutasp_KUKAC_gmail.com)
Kedd, 8:15-9:45
E406
I1 (IMSc)
Balázs Barbara (email: balazs.barbara.a_KUKAC_gmail.com)
Kedd, 8:15-9:45
IB144
I2 (IMSc)
Farkas Rebeka (email: rebus.detenyleg_KUKAC_gmail.com)
Kedd, 8:15-9:45
IE218
I3 (IMSc)
Takács Balázs (email: t.balazs49_KUKAC_gmail.com)
Kedd, 8:15-9:45
IE219
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, 3. gyakorlat, 4. gyakorlat, 5. gyakorlat, 6. gyakorlat, 7. gyakorlat, 8. gyakorlat, 9. 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!

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

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á a vizsgaidőszak előtti pótlási héten (később, a Neptunban megjelenő időpontban) egy második pótzárthelyi alkalom is. Ezek mindegyikén újból meg lehet írni akár az első, akár a második zárthelyi dolgozatot, de egyszerre csak az egyiket. (A dolgozat újbóli megírása természetesen nem azt jelenti, hogy a feladatsorok azonosak volnának, de mindhárom esetben ugyanazokat az anyagrészeket kérik számon és - szándékaink szerint - a nehézségük is azonos.) A két pótzárthelyi alkalmat lehet tehát használni az elmulasztott zárthelyik teljesítésére vagy egy korábban megírt dolgozat eredményének a javítására. 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, a pótlási héten biztosított 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:

Az érvényes TVSz-nek megfelelően a tárgyból korábban megszerzett aláírás 3 évig érvényes. (Részletesebben ez azt jelenti, hogy az aláírás megszerzését követő hatodik félév vizsgaidőszakjának végéig az aláírás még érvényes.) Ezen az időkereten belül a BMEVISZA103 kódú és a BMEVISZAA00 kódú BSz1 tárgyak aláírása érvényes az új, BMEVISZAA03 kódú tárgyból is. Azok, akik egy korábbi félévből érvényes 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, vagy az aláírás érvényességét meghosszabbítsák. Erre az esetre az alábbi feltételek vonatkoznak:
Ha egy érvényes 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 érvényes 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ó vizsgatételsor a félév végén letölthető lesz innen.

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

Technikai tudnivalók a vizsgákkal kapcsolatban:


Zárthelyik:

Első zárthelyi:
október 18. (csütörtök)
8:00 - 10:00
Második zárthelyi:
november 29. (csütörtök)
8:00 - 10:00

Első vagy második (de nem mindkét) zárthelyi pótlása:
december 10. (hétfő)


Az október 18-i, első zárthelyi terembeosztása az alábbi.
Kérjük szépen, hogy mindenki keresse meg (pontosan), hogy a (vezeték)neve az ábécé melyik részébe tartozik és az ennek megfelelő terembe menjen dolgozatot írni.
A zárthelyi anyaga az első hat előadás (és gyakorlat) anyaga. (Címszavakban ez a következőket jelenti: a teljes számelmélet anyagrész; térbeli koordináatgeometria; Rn és az ezzel kapcsolatos fogalmak: altér, generált altér, generátorrendszer, lineáris függetlenség, bázis, dimenzió, koordinátavektor; FG-egyenlőtlenség és következményei.)
A zárthelyin a feladatok 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 hivatkozni bizonyítás nélkül. A korábbi tanulmányokból, más tárgyakból vagy képzésekből származó ismeretek (így például a vektoriális szorzat fogalma és annak kiszámítása) tehát bizonyítás nélkül nem használhatók.
Mindenkinek sok sikert kívánunk!
A - Cs: IB028
D - H: E.1.B
I - K: ST.F.NAGY
L - Sh: CH.MAX
Si - Zs: K.2.34

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.

Állásfoglalás a HK által szervezett BSz1 konzultációkról

Korábbi félévek zárthelyi feladatsorai és pontozási útmutatói:

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: