Számítástudomány

A GeekWiki wikiből
Számítástudomány
Tárgykód
2SZ31NAK12B
Általános infók
Kredit
5
Ajánlott félév
2.
Félév
tavaszi félév
Előadás
van
Szeminárium
hetente egyszer
Tanszék
Számítástudományi Tanszék
Követelmények
Jelenlét
nem kötelező
KisZH
3 db
Házi feladat
nincs
Vizsga
szóbeli
Előtanulmány
nincs
Elérhetőségek
Tárgyfelelős
Dr. Tasnádi Attila
Oktatók
Fleiner Balázs
Dr. Tasnádi Attila
Okató(k) e-mail címe
balazs.fleiner@uni-corvinus.hu
attila.tasnadi@uni-corvinus.hu

A modern számítástudomány alapjainak megismertetése. A tárgy keretén belül a hallgatók elsajátítják azokat a számítástudományhoz szükséges matematikai alapismereteket is, amelyeket a kötelező alapozó matematikai tárgyak (analízis, lineáris algebra és valószínűségszámítás) tananyaga nem tartalmaz, viszont egy informatikus szakos hallgató részére nélkülözhetetlenek. A tárgy alapozást nyújt a felsőbb éves informatikai tárgyakhoz, fejleszti az algoritmikus gondolkodást és elősegíti a számítástechnika területén dolgozó más informatikus szakon végzett hallgatókkal való aktív együttműködést.

Követelmények

A szorgalmi időszakban

A félévközi számonkérés három 40 perces 20 pontos dolgozatból áll, amelyek közül a két legjobb dolgozat számít. A dolgozatok időpontjai: III.8-10., IV.12-14. és V.10-12. A félévközi dolgozatok utólagos pótlására nincs lehetőség.

Az érdemjegyek ponthatárait a következő táblázat mutatja:

Pontszám Jegy
0 - 15 1
16 - 21 2
22 - 27 3
28 - 34 4
35 - 40 5

Vizsgakövetelmény

Vizsgajegy

Az értékelés módszere

Félévközi számonkérés és félév végi szóbeli vizsga a vizsgaidőszakban. A vizsgákra a Neptunon kell jelentkezni!

Tematika

A tananyag leírása

1. hét: Algoritmusok műveletigénye, O és Θ jelölések, a lineáris és a logaritmikus keresés példáján.
2. hét: Relációk és gráfok.
3. hét: Párosítások, König és Hall tételei.
4. hét: Gráf algoritmusok és hálózati folyamok.
5. hét: Euklideszi algoritmus, lineáris diofantoszi egyenlet, kongruencia.
6. hét: Euler–Fermat-tétel, RSA algoritmus.
7. hét: Összeshasonlító rendezések (összefésülő-, kupac- és gyorsrendezés).
8. hét: Adatszerkezetek (tömb, lista, verem és sor).
9. hét: Hash-elés és bináris keresőfák.
10. hét: Kiegyensúlyozott bináris keresőfák.
11. hét: Formális nyelvek definíciója, grammatikák, Chomsky-féle nyelvosztályok.
12. hét: Véges determinisztikus automata és a veremautomata.
13. hét: Turing-gép, kiszámíthatóság alapfogalmai, alapvető kiszámíthatatlansági tételek.
14. hét: Algoritmusok bonyolultsága, NP-teljesség.

Kompetencia leírása

Alapvető számelméleti, kereső és rendező eljárások elsajátítása. A műveletigény analízis és számítógéppel megoldhatatlan problémák megismerése. A tárgyalt adatszerkezetek használata programokban. A matematikai nyelvészet alapjainak megértése. A feladatmegoldó képességet és a tárgyalt módszerek ismeretét az évközi dolgozatokban ellenőrizzük. Az elméleti eredmények megértését a szóbeli vizsgán várjuk el.

Irodalomjegyzék

Kötelező irodalom

  • Tasnádi Attila: Számítástudomány gazdaságinformatikusoknak Aula Kiadó, 2006

Ajánlott irodalom

  • Katona Gyula Y., Recski András, Szabó Csaba: A számítástudomány alapjai TypoTex Kiadó, 2003.
  • Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok TypoTex Kiadó, 1999.
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Új algoritmusok Scolar Kiadó, 2003.