Bevezetés a számításelméletbe I.

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

Adatlap utolsó módosítása: 2006. július 1.

Tantárgy lejárati dátuma: 2015. január 31.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Műszaki Informatika Szak

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VIMA1235 1 2/2/0/v 5 1/1
3. A tantárgyfelelős személy és tanszék Dr. Csákány Rita,
4. A tantárgy előadója

Név:

Beosztás:

Tanszék, Int.:

Dr. Sali Attila

egyetemi docens

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

Dr. Simonyi 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
Ajánlott:

-

7. A tantárgy célkitűzése

Az informatikusmérnöki tanulmányokhoz szükséges legfontosabb diszkrét matematikai ismeretek elsajátítása, szemléletmódjának kialakítása.

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

Komplex számok, kanonikus és trigonometrikus alak, műveletek, egységgyökök. Végtelen számosságok, hatványhalmaz, kontinuum-hipotézis. Vektoralgebra, 2- és 3-dimenziós analitikus geometria. Lineáris algebra elemei (vektortér, altér, bázis, generátorrendszer). Lineáris transzformációk, mátrixok, lineáris egyenletrendszer megoldhatósága, egyértelműsége. Determináns definíciói, tulajdonságai. Négyzetes mátrixok sajátértékei, sajátvektorai. Kvadratikus alakok, definitség. Alapvető kombinatorikai ismeretek (permutációk, variációk, kombinációk), binomiális tétel. Gráfelméleti alapfogalmak, fák, fák száma, minimális költségű fa keresése. Síkbarajzolhatóság, dualitás. Gráfok mátrixai.

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

(előadás, gyakorlat, laboratórium):

Előadás és gyakorlat.

10. Követelmények

a. A szorgalmi időszakban:

A félév folyamán két zárthelyit iratunk.

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. A két zárthelyihez van egy-egy pótlási lehetőség a félév utolsó hetében: ilyenkor az elégtelen(-ek) kijavítható(-ak), illetve az esetleges hiányzás(-ok) pótolható(-ak). A pótzárthelyin gyenge, de nem elégtelen 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 megszerzett aláírás egy javítónak szánt, de elégtelenre megírt pótzárthelyivel nem vész el, viszont leviszi a zárthelyikből származó pontszámot az elégségeshez szükséges minimális pontszám szintjére.)

Amennyiben a pótlás sem sikerül, már csak ismétlő vizsga (gyakIV) jelleggel lehet megszerezni az aláírást, és így a vizsgázás jogát. Ennek módja, hogy a vizsgaidőszakban egy újabb zárthelyit kell legalább elégségesre megírni. (Ez a zárthelyi a félév teljes anyagához kapcsolódó feladatokat tartalmazhat függetlenül attól, hogy a szorgalmi időszakban melyik zárthelyi nem sikerült.) A vizsgaidőszakban két gyakIV alkalmat hirdetünk meg (ezek közül az egyiket várhatóan az első héten), de a két alkalom közül mindenki csak az egyiken próbálkozhat. Így ha valaki az első alkalommal megpróbált aláírást szerezni, de ez nem sikerült, annak sajnos a második alkalommal már nem lesz lehetősége erre. A gyakIV-kre a Neptunban jelentkezni kell.

Ha a gyakIV jelleggel megírt zárthelyi eléri a legalább elégséges szintet, akkor egy későbbi vizsgaalkalommal lehet vizsgázni. Ha valaki az aláírást gyakIV-vel szerzi meg, akkor ezt a vizsgán úgy számítjuk be, mintha mindkét zárthelyin az elégségeshez szükséges minimális pontszámot érte volna el. Ha a gyakIV sem sikerül, akkor a félév sajnos sikertelen.

b. A vizsgaidőszakban:

A tárgyból szóbeli vizsga van.

A vizsga úgy zajlik, hogy 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ó néhány definíció, vagy tétel kimondása erejéig 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, illetve 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).

Aki elégtelenre vizsgázik, egy ízben ismétlő vizsgát tehet. Ez a pótlási lehetőség szükség esetén az olyan hallgatót is megilleti, aki az aláírást gyakIV-vel szerezte meg. Ismétlő vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek.

  1. Elővizsga: nincs rá lehetőség.
11. Pótlási lehetőségek

lásd a 10. pontot.

12. Konzultációs lehetőségek

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

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

Freud Róbert : Lineáris Algebra, ELTE Kiadó

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

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

(a tantárgyhoz tartozó tanulmányi idő körülbelüli felosztása a tanórák, továbbá a házi feladatok és a zárthelyik között (a felkészülésre, ill. a kidolgozásra átlagosan fordítandó/elvárható idők félévi munkaórában, kredit x 30 óra, pl. 5 kredit esetén 150 óra)):

Kontakt óra

60

Félévközi készülés órákra

15

Felkészülés zárthelyire

10

Házi feladat elkészítése

15

Kijelölt írásos tananyag elsajátítása

0

..

Vizsgafelkészülés

50

Összesen

150

15. A tantárgy tematikáját kidolgozta

Név:

Beosztás:

Tanszék, Int.:

Dr. Recski András

egyetemi tanár, tanszékvezető

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