Bevezetés a számításelméletbe II. előadás, 2014/15.  1. félév



 
 
 

Előadó, terem, időpont

 

Wiener Gábor

wiener kukac cs pont bme pont hu

IB 025

kedd 12.15-14.00

 

Aktuális

Az első zh (okt. 27., 8 óra) terembeosztása: A-H: Q II., I-M: E1A, N-Zs: E1B.

 

Az első zh anyaga az okt. 14-i előadás anyagából a folyamokat még tartalmazza, a többszörös összefüggőség témakörét és az okt. 21-i előadás anyagát már nem.

 

Zh-időpontok: 1.zh: okt. 27. hétfő, 8.00, 2. zh: nov. 28. péntek, 8.00, pótzh: dec. 12. péntek, 8.00.

 

A BSz2 előadás a jelenlegi formájában utoljára indul. A tavaszi félévben már a megújult BSz2 tárgyat oktatjuk (ebben nagyjából a régi BSz1 és BSz2  gráfelméleti része és számos gráfalgoritmus szerepel majd). Az aláírással rendelkező hallgatók természetesen vizsgakurzusként későbbi félévekben is felvehetik a régi BSz2 tárgyat.  

Tematika

Gráfelmélet, számelmélet és egyszerű kriptográfiai alkalmazásai, az absztrakt algebra alapjai.
Javasolt jegyzetek:

   Katona-Recski-Szabó: A számítástudomány alapjai,

   Friedl-Recski-Simonyi: Gráfelméleti feladatok (elsősorban gyakorlatra), 

   BSZ 2 letölthető jegyzet

Félévközi követelmények 

A félév során két zárthelyi lesz. A félévvégi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) feltétele, hogy mindkét zárthelyinek külön-külön legalább elégségesre kell sikerülnie.

Az érvényes TVSz-nek megfelelően a két zárthelyi közül legalább az egyiket már az első alkalommal (pótlás nélkül) sikeresen kell megírni, pótolni legfeljebb csak a másikat lehet. Így a szorgalmi időszak alatt összesen csak egyetlen pótzárthelyi alkalom lesz, ahol vagy az első, vagy a második (de nem mindkét) zárthelyin elért elégtelen eredmény kijavítható, vagy az esetleges hiányzás pótolható. A pótolt zh-k eredménye ugyanúgy számít be a vizsgajegybe, mint a normál zh-k eredménye.

A pótzárthelyin korábban megírt, eredményes zárthelyi javítása is megkísérelhető, de csak azzal a feltétellel, hogy ilyenkor mindenképpen az új pontszám lesz érvényes, akkor is, ha rosszabb, mint az eredeti. (Ez alól egy kivétel van: a már sikeresen teljesített zárthelyi egy javítónak szánt, de elégtelenre megírt pótzárthelyivel nem vész el, viszont leviszi a megfelelő zárthelyiből származó pontszámot az elégségeshez szükséges minimális pontszám szintjére.)

Ha valaki mindkét zárthelyit (már az első alkalommal) sikeresen teljesítette, de (a TVSz biztosította jogával élve) mindkét zárthelyi eredményét javítani kívánja (és így a számára az egyetlen meghirdetett pótzárthelyi alkalom nem elegendő), az keresse meg (emailben vagy személyesen) a tárgy előadóját (még a pótzárthelyi időpontja előtt).

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.) 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 sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor a vizsgajegybe az így kapott eredmény számít bele (akkor is, ha ez rosszabb).

·         Ha nem sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor az aláírás nem vész el, de a vizsgajegybe csak az aláírás megszerzéséhez szükséges minimális pontszámot számítjuk be.

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

Szóban zajlik, az alábbiak szerint: a tételsoron szereplő tételek közül a vizsgázó egyet kap, ezt kidolgozza, majd szóban felel belőle. Számítani kell arra is, hogy a vizsgáztató a többi tételbe is belekérdez. A vizsgán az elégséges megszerzésének feltétele, hogy a vizsgázó az anyagban szereplő minden definíciót és tételt ki tudjon mondani, illetve tudjon értelmezni. A vizsgatétel kidolgozására a hallgatónak felkészülési idő áll rendelkezésére. Negyvenöt perc 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 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 olyan módon, hogy abba a zárthelyik átlaga 40 százalék erejéig, a szóbeli vizsga 60 százalék erejéig számít bele. Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen (függetlenül a zárthelyik eredményétől). Javító (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 vizsgákra a Neptunban jelentkezni kell. (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 a jelentkezést elmulasztotta.)

A vizsgatételsor a félév végén letölthető. 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.


Technikai tudnivalók a vizsgákkal kapcsolatban:

  • A szóbeli vizsgák kulturált lebonyolítását, a vizsgára való várakozás kellemesebbé tételét sorszámok kihelyezésével igyekszünk elősegíteni. A tanszéknek azonban nincs erőforrása sem arra, hogy a sorszámok kiosztását végezze, sem arra, hogy vizsga közben a soron következő sorszám nyilvántartását végezze. Arra kérjük ezért a vizsgázókat, hogy ezt önállóan szervezzék meg az alábbiak szerint:
    • Minden vizsgázó érkezéskor a következő egyetlen sorszámot tépje le. Bár ezt ellenőrizni se nem tudjuk, se nem kívánjuk, nagyon kérünk mindenkit, hogy ne tépjen egynél több sorszámot még akkor sem, ha erre olyan hallgatótársa kérné, akiről biztosan tudja, hogy a vizsgán (akár perceken belül) meg fog jelenni.
    • Kérünk minden vizsgázót, hogy ne jelentkezzen vizsgára mindaddig, amíg alacsonyabb sorszámmal rendelkező hallgatók is várnak.
    • A vizsga technikai lebonyolítását végző kollégánk nem fogja tudni számontartani, hogy milyen sorszámú hallgató kerül sorra, mindig a "következő" (vagy következő néhány) vizsgázót hívja be. Ezért kérünk mindenkit, hogy várakozás közben időnként győződjön meg arról, hogy éppen milyen sorszámú hallgató ment be vizsgázni, hogy amikor sorra kerül, rendelkezésre álljon.
    • Minden vizsgára várót bátorítunk arra, hogy szükség esetén a fentiekre nem hallgató társát udvarias, de nyomatékos formában figyelmeztesse.
  • A szóbeli vizsgák limitjét - a tanszék erőforrásainak korlátossága miatt - a vizsgaidőszak során nem fogjuk tudni megemelni (és további vizsgaalkalmat sem fogunk tudni kiírni). Ha tehát valamelyik vizsga limitje betelt, akkor szóbelizni csak a következő alkalommal lehet; ha pedig ilyen már nincs, akkor csak a következő félévben. (Továbbá a különböző BSz1 kurzusok között sem tudunk szabad vizsgahelyet átcsoportosítani; hiába van az egyiken még esetleg néhány szabad hely, ha a másik betelt, akkor arra már nem lehet jelentkezni.) Emiatt kérünk mindenkit, hogy:
    • a vizsgaidőszakját előre tervezze meg (tapasztalatunk szerint az első néhány hét BSz vizsgáin általában bőségesen maradnak helyek, a limitek csak az utolsó két hétben szoktak betelni);
    • ha valaki úgy érzi, hogy valamelyik szóbelin mégsem kíván vagy tud részt venni, akkor a többi hallgató érdekében mielőbb jelentkezzen le.
  • Minden szóbeli alkalomhoz nyitunk a Neptunban várólistát. (Ha tehát valamelyik vizsgáról egy hallgató lejelentkezik, akkor a listára automatikusan felkerül a várólista élén álló jelentkező.) Felhívjuk azonban a figyelmet arra, hogy azokat a hallgatókat, akik a vizsga napjáig a várólistán maradtak (tehát nem kerültek át a vizsgázók listájára), a szóban forgó vizsganapon nem tudjuk levizsgáztatni (az eredmény beírását a Neptun nem is engedné).
  • A szóbelikre való jelentkezés akkor zárul, ha a következő hallgató hívásakor már senki nem jelentkezik vizsgára. Kérünk mindenkit, hogy ezt vegye figyelembe: amennyiben valaki később érkezne, nem fog már tudni levizsgázni.
  • Minden szóbeli vizsga előtt tartunk konzultációt, ahol a vizsgára készülés közben felmerült kérdéseket lehet feltenni.

Tanácsok vizsgára

Gyakorlatok

A hallgatók az alább felsoroltak közül bármely gyakorlatot látogathatják, a következő feltételekkel. Természetesen mindenki járhat arra a gyakorlatra, amelyre a Neptunban fel van jelentkezve. Emellett  vagy ehelyett járhat más gyakorlat(ok)ra is, amennyiben az adott gyakorlat gyakorlatvezetőjével ezt megbeszéli, a zh-it azonban mindenképpen az a gyakorlatvezető javítja, akihez az illető hallgató a Neptun szerint jár (kivételt képeznek ez alól az emelt szintű gyakorlatra járók – az ő dolgozataikat Fleiner Tamás javítja). 

Az emelt szintű gyakorlatokat azoknak ajánljuk, akik a tárgy iránt az átlagosnál jobban érdeklődnek és kicsit magasabb szintű feladatokra vágynak. Akik ide járnak, azok számára a ZH és minden egyéb tárgykövetelmény ugyanaz, mint a többieknek. (Az emelt szintű gyakorlatok helyszíne - az IB134-es Bach Iván terem - a Számítástudományi és Információelméleti Tanszék területén található, a bejárattal szemben.)

Akik a normál gyakorlatot kevésnek találják és úgy érzik, hogy további feladatokra, konzultációs lehetőségre van szükségük, azok számára ajánljuk Domján Pál (email: domjan
_KUKAC_cs.bme.hu) konzultációit keddenként 18.15-től az IB 134 teremben.

Kurzuskód

Időpont

Gyakorlatvezető

Terem

12

kedd, 16:15-18:00

Károlyi Márton

IB134

13

kedd, 16:15-18:00

Kiss Attila

IB145

16

kedd, 16:15-18:00

Mihálka Éva Zsuzsa

IB146

11

csütörtök, 10:15-12:00

Károlyi Márton

IB134

14

csütörtök, 10:15-12:00

Csákány Rita

IB138

15

csütörtök, 10:15-12:00

Mann Zoltán

IB139

17

csütörtök, 10:15-12:00

Kőrösi Attila

IB140

 

 

Zh-k

 

 

 

 

 

Zh-időpontok: 1.zh: okt. 27. hétfő, 8.00, 2. zh: nov. 28. péntek, 8.00, pótzh: dec. 12. péntek, 8.00.

Kérjük, hogy a zh-ra mindenki úgy érkezzen, hogy fejből tudja annak a gyakorlatvezetőnek a nevét, akihez a Neptun szerint jár és a dolgozaton (a saját nevén kívül) ezt a nevet tüntesse fel. (Kivételt jelentenek az emelt szintű gyakorlatra járó hallgatók: ők az emelt szintű gyakorlat vezetőjének nevét tüntessék fel, feltéve, hogy a gyakorlaton feliratkoztak a listájára.) Akinek ez problémát okoz, az a dolgozat írása közben, a teremben felügyelő oktatónál lévő listáról is kaphat segítséget a gyakorlatvezető nevének kiderítésében. Felhívjuk a figyelmet arra, hogy érvénytelen minden olyan dolgozat, amin a feltüntetett gyakorlatvezető neve különbözik a Neptun által nyilvántartottól.

A zárthelyiken semmilyen segédeszköz nem használható. Mindig hat feladat van, mindegyik 10 pontot ér, az elégséges alsó határa 24 pont; a munkaidő 90 perc. Kérjük, hogy a zárthelyik írásakor mindenki megfelelő mennyiségű, előre összetűzött, üres lappal érkezzen és a zárthelyi írása közben csak ezeken dolgozzon. (A lapokra szabad előre felírni a nevet, a Neptun kódot és a gyakorlatvezető nevét, hogy ezzel a zárthelyi írása közben ne kelljen időt tölteni.) Akinek nincs tűzőgépe, annak szívesen összetűzzük a lapjait a zárthelyi előtt.

Felhívjuk a figyelmet arra, hogy a zárthelyi írása közben senkinél nem lehet sem bekapcsolt mobiltelefon (még elnémítva sem), sem bármely más elektronikus eszköz; kérjük, aki igényli, gondoskodjon karóráról a dolgozat írásának idejére.  Felhívjuk továbbá a figyelmet arra is, hogy a dolgozat írásának megkezdése után az első 30 percben a termet elhagyni csak rendkívül alapos indokkal lehet, ennek az időnek a letelte után pedig a késve érkező hallgatók már nem kezdhetik el a zárthelyi írását.

 

 

  Aláíráspótló vizsga

 

  

Amennyiben a zárthelyik és pótzárthelyi segítségével sem sikerül mindkét zárthelyit legalább elégségesre megírni, már csak egy  lehetőség  marad az aláírás (és így a vizsgázás jogának) megszerzésére: a vizsgaidőszak előtti "pótlási héten" lehetőség nyílik az  egyik (értelemszerűen a sikertelen) zárthelyinek az újbóli pótlására. Erre a második pótzárthelyi alkalomra a TVSz "aláíráspótló vizsga" néven  hivatkozik (de ez természetesen nem valódi vizsga).  Azonban az aláíráspótló vizsgára is vonatkozik a TVSz fent említett  szabálya: bármelyik zárthelyi csak akkor pótolható, ha a másik már az első alkalommal (pótlás nélkül) sikerült. Az aláíráspótló vizsgán már nem lehetséges korábban eredményesen megírt zárthelyi javítása.

Mindez tehát azt jelenti, hogy ha valaki a két zárthelyi közül mindkettőn elégtelent ír (vagy nem jelenik meg), akkor ebben a félévben  már semmilyen módon nem szerezheti meg az aláírást. Ha viszont valaki a két zárthelyi közül legalább az egyiket elsőre legalább  elégségesre írja meg, akkor a másik zárthelyit összesen akár három alkalommal (a zárthelyin, a pótzárthelyin, illetve az aláíráspótló  vizsgán) is megpróbálhatja teljesíteni.

Az aláíráspótló zárthelyi a pótlási héten lesz (a pontos időpont később derül ki) . Az aláíráspótló vizsgára a Neptunban jelentkezni kell. (Aki ezt elmulasztja, annak az ezen az alkalmon megszerzett aláírását nem tudjuk beírni a Neptun rendszerbe. Így nincs lehetőségünk arra, hogy olyan hallgatónak engedélyezzük a részvételt, aki a Neptunban a jelentkezést elmulasztotta.)

   

Feladatsorok

Korábbi félévek zárthelyi (és 2006-tól aláíráspótló) feladatsorai:


2012.
tavaszi félév: pdf

2011. tavaszi félév: pdf (Pontozási útmutatóval.)

2010. tavaszi félév: pdf
2009. tavaszi félév: pdf (A pontozási útmutató itt található.)
2008. tavaszi félév: pdf

2007. tavaszi félév: pdf (Ezek egy részéhez megoldások itt találhatók.)
2006. tavaszi félév: pdf
2005. tavaszi félév: pdf
2004. tavaszi félév: pdf
2003. tavaszi félév: pdf
2002. tavaszi félév: pdf
2001. tavaszi félév: pdf
2000. tavaszi félév: pdf
1999. tavaszi félév: pdf

2006 előtti félévek aláíráspótló feladatsorai:

2006. tavaszi félév: pdf
2005. tavaszi félév: pdf
2004. tavaszi félév: pdf
2003. tavaszi félév: pdf

 
2002. tavaszi félév: pdf, html
2001. tavaszi félév: pdf, html
2000. tavaszi félév: pdf, html
1999. tavaszi félév: pdf, html

Gyakorló feladatok - a Katona-Recski-Szabó jegyzet régi, egyetemi kiadásának utolsó fejezete, ami az új kiadásban nem szerepel:  pdf, postscript