Algoritmuselmélet

A tantárgy angol neve: Theory of Algorithms

Adatlap utolsó módosítása: 2011. január 25.

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

Műszaki Informatika Szak

BSc

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZA213 4. 2/2/0/v 5 1/1
3. A tantárgyfelelős személy és tanszék Dr. Friedl Katalin,
A tantárgy tanszéki weboldala //cs.bme.hu/algel
4. A tantárgy előadója

Név:

Beosztás:

Tanszék, Int.:

Dr. Friedl Katalin

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

Gráfelmélet

6. Előtanulmányi rend
Kötelező:
(TárgyEredmény( "BMEVISZA110" , "aláírás" , _ ) = -1
VAGY TárgyEredmény( "BMEVISZA031" , "jegy" , _ ) >= 2
VAGY TárgyEredmény( ahol a TárgyKód = "BMEVIMA1236", ahol a Típus = "VIZSGA", ahol a Ciklus = tetszőleges, ahol a KépzésKód = tetszőleges) >=2
VAGY Aláírás( ahol a TárgyKód = "BMEVIMA2603", ahol a Ciklus = tetszőleges)
VAGY TárgyEredmény( "BMEVISZA071" , "jegy" , _ ) >= 2 )
VAGY KépzésLétezik( ahol a KépzésKód = "9N-MM09")

ÉS
NEM ( TárgyEredmény( "BMEVISZAB01" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZAB01", "FELVETEL", AktualisFelev()) > 0)

ÉS Training.Code=("5N-A8")

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

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

Ajánlott:
Bevezetés a Számításelméletbe II.-ből aláírás
7. A tantárgy célkitűzése

Az algoritmusok tervezésével, elemzésével kapcsolatos alapvető módszerek, készségek elsajátítása.

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

Kereső algoritmusok. Alapvető adatszerkezetek: keresőfa, kiegyensúlyozott keresőfa (AVL-fa), B-fa, hash-tábla, kupac.

Rendező algoritmusok: buborék rendezés, beszúrásos rendezés, összefésülés, kupacos rendezés, gyorsrendezés, láda- és radixrendezés.

Alsó becslés az összehasonlitó rendezések lépésszámára.

Alapvető gráfelméleti algoritmusok:

Mélységi és szélességi bejárás, összefüggő és erősen összefüggő komponensek meghatározása, maximális párositás keresése páros gráfban.

Legrövidebb utak keresése Dijkstra, Bellman-Ford és Ford algoritmussal.

Minimális költségű feszitőfa keresése Prim módszerével, Kruskal algoritmusa és az unióüholvan adatszerkezet.

Általános algoritmus-tervezési módszerek: mohó algoritmus, oszd meg és uralkodj, dinamikus programozás, elágazás és korlátozás.

Közelitő algoritmus a ládapakolás és az euklideszi utazóügynök problémára.

A bonyolultságelmélet alapjai: kiszámithatóság, NP, NP-teljesség

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

Előadás, gyakorlat

10. Követelmények

a. A szorgalmi időszakban:

- a félév lezárásának módja: aláírás

- a félév lezárásához szükséges követelmény: sikeres zárthelyi

b. A vizsgaidőszakban: - írásbeli vizsga

c. Elővizsga: nincs

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

 pótzárthelyi

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

Igény szerint folyamatosan biztosítjuk.

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

Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, Typotex, Budapest, 1999.

T. Cormen, C. Leiserson, R. Rivest, C. Stein: Új algoritmusok, Scolar Kiadó, 2003.

Feladatgyűjtemény: http://cs.bme.hu/algel/fasor.pdf

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

56

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

28

Felkészülés zárthelyire

10

Házi feladat elkészítése

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

Zárthelyi megírása..

2

Vizsgafelkészülés

54

Összesen

150

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

Név:

Beosztás:

Tanszék, Int.:

Dr. Friedl Katalin

egy. docens

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

Visza213.rtf