Bevezetés a számításelméletbe 1

A tantárgy angol neve: Introduction to the Theory of Computing 1

Adatlap utolsó módosítása: 2017. január 9.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar
Mérnök informatikus szak, BSc képzés
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZAA00 1 2/2/0/v 4  
3. A tantárgyfelelős személy és tanszék Dr. Szeszlér Dávid, Számítástudományi és Információelméleti Tanszék
A tantárgy tanszéki weboldala http://cs.bme.hu/bsz1
4. A tantárgy előadója

Név:

Beosztás:

Tanszék, Int.:

Dr. Fleiner Tamás

egyetemi docens

Számítástudományi és Információelméleti Tanszék

Dr. Pach Péter Pál

egyetemi adjunktus

Számítástudományi és Információelméleti Tanszék

Dr. Recski András

egyetemi tanár

Számítástudományi és Információelméleti Tanszék

Dr. Simonyi Gábor

egyetemi tanár

Számítástudományi és Információelméleti Tanszék

Dr. Szeszlér Dávid

egyetemi docens

Számítástudományi és Információelméleti Tanszék

Dr. Wiener Gábor

egyetemi docens

Számítástudományi és Információelméleti Tanszék

5. A tantárgy az alábbi témakörök ismeretére épít Előismeretet nem tételezünk fel.
6. Előtanulmányi rend
Kötelező:
NEM (TárgyEredmény("BMEVISZA103", "jegy", _) >= 2
VAGY
TárgyEredmény("BMEVISZA103", "felvétel", AktualisFelev()) > 0
VAGY
TárgyEredmény("BMEVISZAA03", "jegy", _) >= 2
VAGY
TárgyEredmény("BMEVISZAA03", "felvétel", AktualisFelev()) > 0
VAGY
TárgyEredmény( "BMEVISZAA03" , "aláírás" , _ ) = -1)

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rendek grafikus formában itt láthatók.

Ajánlott:
--
7. A tantárgy célkitűzése

A műszaki informatika tanulmányokhoz szükséges és a mérnöki alapműveltséghez tartozó egyes alapvető matematikai ismeretek elsajátítása, azok szemléletmódjának kialakítása.

8. A tantárgy részletes tematikája

1)      Térbeli koordinátageometria: vektorok a térben, koordinátarendszer, skaláris szorzat. A sík egyenlete. Az egyenes (paraméteres és kanonikus egyenletrendszere). Rn fogalma, műveletek oszlopvektorokkal.

2)      Rn alterének fogalma, műveleti zártság. Lineáris kombináció, generátorrendszer és generált altér fogalma, az utóbbi altér volta. Lineáris függetlenség fogalma, a kétféle definíció ekvivalenciája.

3)      Reláció az alterek lineárisan független rendszereinek, illetve generátorrendszereinek elemszáma között. Bázis és dimenzió fogalma, a dimenzió egyértelműsége. Bázisban való felírás egyértelműsége.

4)      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. Reláció az egyenletek és az ismeretlenek száma között egyértelmű megoldhatóság esetén.

5)      Determináns definíciója. Permutációk inverziószáma. A determináns alaptulajdonságai. Determináns kiszámítása Gauss-eliminációval. (n x n)-es lineáris egyenletrendszer egyértelmű megoldhatóságának jellemzése a determinánssal. A kifejtési tétel.

6)      Térvektorok vektoriális- és vegyesszorzatának fogalma, a vegyesszorzat kapcsolata a determinánssal. Műveletek mátrixok között, egységmátrix, transzponált mátrix. A determinánsok szorzástétele. Lineáris egyenletrendszerek Ax=b alakban. Kapcsolat a négyzetes mátrix oszlopainak/sorainak lineáris függetlensége, illetve a determináns között.

7)      Az inverz mátrix fogalma, az inverz létezésének szükséges és elégséges feltétele. Az inverz kiszámítása. Mátrix rangjának fogalma, a háromféle rangfogalom egyenlősége, a rang kiszámítása.

8)      Lineáris leképezés fogalma, leképezés linearitásának szükséges és elégséges feltétele. Lineáris leképezések kompozíciója, addíciós tételek a sin és cos függvényekre. Lineáris leképezés magtere, képtere, dimenziótétel.

9)      Bázistranszformáció, lineáris transzformáció mátrixa adott B bázis szerint, annak kiszámítása. Sajátérték és sajátvektor fogalma, a sajátértékek kiszámítása, a karakterisztikus polinom fogalma.

10)  A számelmélet alapjai: oszthatóság, prímszám, a számelmélet alaptétele, a prímek számossága, hézag a szomszédos prímek között, a nagy prímszámtétel. Kongruencia fogalma, alapműveletek kongruenciákkal. Lineáris kongruenciák megoldhatósága.

11)  Euklideszi algoritmus a legnagyobb közös osztó kiszámítására, illetve lineáris kongruenciák megoldására. Kétváltozós, lineáris, diofantikus egyenletek, szimultán kongruenciarendszerek megoldása. Euler-Fermat tétel, kis Fermat-tétel.

12)  Számelméleti algoritmusok: kapcsolat az input mérete és a bemenő adatok logaritmusa között, alapműveletek, hatványozás modulo m, prímtesztelés. Nyilvános kulcsú titkosírás, RSA.

13)  Végtelen halmazok számossága: egyenlő és kisebb-vagy-egyenlő számosságú halmaz fogalma. Megszámlálhatóan végtelen és kontinuum számosságú halmaz fogalma. Az N, Z, Q és R számhalmazok számossága.

14)  Ismétlés, összefoglalás, a tanult anyagrészek rendszerezett áttekintése. A szóbeli vizsgára vonatkozó aktuális vizsgatételsor és az egyes vizsgatételekkel kapcsolatos részletes elvárások ismertetése.

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

Heti 2 óra előadás és heti 2 órás kiscsoportos gyakorlat.

10. Követelmények

Az előadások és a gyakorlatok látogatása kötelező. Az előadásokon a jelenlétet azok kezdetén és végén is a félév folyamán minden alkalommal ellenőrizzük, aláírást nem kaphat az a hallgató, aki ezek alapján az alkalmak több, mint 30%-áról hiányzott (a viszonyítási alap a ténylegesen megtartott előadások száma). A gyakorlatokon a jelenlétet minden alkalommal ellenőrizzük, 30%-ot meghaladó hiányzás esetén a tantárgyból sem aláírás sem kreditpont nem szerezhető.  

A szorgalmi időszakban: A félév folyamán két zárthelyit íratunk. A félévvégi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) feltétele a zárthelyiken külön-külön legalább 30% -os teljesítmény és a két zárthelyi átlagában legalább 40%-os teljesítmény.

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 a hallgatók, akik egy korábbi félévből érvényes aláírással rendelkeznek, megkísérelhetik újból megírni a zárthelyiket, hogy a korábbi zárthelyik eredményein javítsanak. 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 (lásd lentebb) 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). 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.

A vizsgaidőszakban: Vizsgára az jelentkezhet, aki érvényes aláírással rendelkezik.

A vizsga ebből a tárgyból szóbeli. A vizsga megkezdésekor a vizsgázó a tárgyhoz tartozó tételsorból egyetlen tételt kap, amelynek a kidolgozására (vagyis a szóbeli felelethez egy bő jegyzet készítésére) legalább 45 perc áll rendelkezésre. 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.) 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 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). Ismétlő vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek.

A tárgyhoz tartozó vizsgatételsor félévről félévre változik, az aktuális félévre érvényes vizsgatételsor a tárgy tanszéki weboldaláról tölthető le a szorgalmi időszak utolsó hetétől.

Elővizsga: nem lehetséges

11. Pótlási lehetőségek

A két zárthelyin kívül a szorgalmi időszakban pótzárthelyi írható, melyen bármelyik (de nem mindkettő) zárthelyi eredménye javítható vagy a hiányzás pótolható. 

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 az rosszabb, mint az eredeti. (Ez alól egy kivétel van: ha a hallgató az aláírás feltételeit már teljesítette, de a javítónak szánt zárthelyi új pontszámával a feltételek valamelyikét nem teljesíti, akkor a hallgató az aláírást megkapja, de a zárthelyikből származó pontszáma az elégségeshez szükséges minimális pontszám lesz.)

Amennyiben a zárthelyik és a pótzárthelyi segítségével sem sikerül a feltételeket teljesíteni, a vizsgaidőszak előtti "pótlási héten" lehetőség nyílik az egyik (szabadon választott) zárthelyinek az újbóli pótlására, illetve javítására a feltételek teljesítése érdekében. Ennek a második pótzárthelyi alkalomnak a neve “aláíráspótló vizsga” (de ez természetesen nem helyettesíti a szóbeli vizsgát).
12. Konzultációs lehetőségek

A vizsgák előtt konzultációs lehetőséget biztosítunk.

13. Jegyzet, tankönyv, felhasználható irodalom

Bevezetés a számításelméletbe – digitális jegyzet, a tárgy tanszéki weboldaláról letölthető

Katona Y. Gyula - Recski András - Szabó Csaba: A számítástudomány alapjai, TypoTeX Kiadó, 2003.

Friedl Katalin - Recski András - Simonyi Gábor: Gráfelméleti feladatok, TypoTeX Kiadó, 2006.

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra56.
Félévközi készülés órákra 8
Felkészülés zárthelyire 6
Házi feladat elkészítése 8
Kijelölt írásos tananyag elsajátítása 0
Vizsgafelkészülés 42
Összesen 120
15. A tantárgy tematikáját kidolgozta

Név:

Beosztás:

Tanszék, Int.:

Dr. Szeszlér Dávid

egyetemi docens

Számítástudományi és Információelméleti Tanszék

 

IMSc tematika és módszer A plusz pontokat a hatékonyabb tanulásért és az anyag magasabb szintű, mélyebb elsajátításáért kapják a hallgatók. A gyakorlatokon más feladatokat dolgozunk fel, mint a többi kurzuson. Kevesebb bevezető, rutin, gyakorló feladat szerepel és több nehezebb, gondolkodtatóbb feladat lesz.
IMSc pontozás
Mindkét zárthelyin és a szóbeli vizsgán is 60 pontot lehet elérni. Az IMSc pontokat az alábbi képlettel számítjuk ki, ahol zh1 és zh2 az első, illetve második zárthelyin, v pedig a szóbeli vizsgán szerzett pontszám.

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

Az IMSc pontok megszerzése a programban nem résztvevő hallgatók számára is biztosított. Az aláírás és a vizsgajegy megszerzése mindenki számára egységes követelmények szerint, a 10. pontban leírtaknak megfelelően történik,
ezt az IMSc pontok nem befolyásolják. A vizsgán kapott végső jegyet meghatározó pontszámot az alábbi képlettel számítjuk ki.

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

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.
Egyéb megjegyzések NEM (TárgyTeljesítve("BMEVISZA103") )