Válogatott fejezetek az algoritmusok köréből 1

A tantárgy angol neve: Selected Topics in Algorithms 1

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

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

Villamosmérnöki Szak

Műszaki Informatika Szak

Választható tárgy
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
TE915029 őszi 2/0/0/v 3 1/1
4. A tantárgy előadója

Név:

Beosztás:

Tanszék, Int.:

Dr. Rónyai Lajos

tanszékvezető egyetemi tanár

Algebra Tanszék
5. A tantárgy az alábbi témakörök ismeretére épít

Algoritmusok elmélete, diszkrét matematika

6. Előtanulmányi rend
Kötelező:
TárgyEredmény( "BMEVIMA2207" , "jegy" , _ ) >= 2

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:

Tematikaütközés miatt a tárgyat csak azok vehetik fel, akik korábban nem hallgatták a következő tárgyakat:

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

A hallgatók megismertetése néhány modern algoritmustervezési technikával, hatékony algoritmussal.

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

Ahogy a tárgy címe is sugallja, válogatást szeretnénk nyújtani a rendkívül gazdag, a számítástudomány élvonalába tartozó ismeretkörből. Az anyag összeállításánál figyelembe vesszük a mindenkori hallgatóink kéréseit is.

Törzsanyag: mintaillesztés szövegben (Knut-Morris-Pratt-, Boyer-Moore-, Rabin-Karp–algo-ritmusok). Sorozatillesztés betűnként (általános módszerek, Ukkonen-algoritmus). Sorozat-illesztés általános hézagmodellel, többszörös illesztés. A szöveg-indexelés alapjai: invertálás, lenyomatok, vektorteres indexelők, az LSI-technika. Randomizált algoritmusok: Schwartz-Zippel és alkalmazásai, egzisztencia-bizonyítások (Erdős-módszer), az IP-nyelvosztály, Karger-Klein-Tarján–algoritmus feszítőfa keresésre. A kommunikációs bonyolultság elemei.

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

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

előadás

10. Követelmények

a. A szorgalmi időszakban:

b. A vizsgaidőszakban: vizsga

  1. Elővizsga: lehetséges
11. Pótlási lehetőségek

vizsgák pótlásának ált. szab. szerint

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

az előadókkal egyeztetett formában

13. Jegyzet, tankönyv, felhasználható irodalom
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

30

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

15

Felkészülés zárthelyire

Házi feladat elkészítése

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

..

Vizsgafelkészülés

45

Összesen

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

Név:

Beosztás:

Tanszék, Int.:

Dr. Rónyai Lajos

tansz. vez. egy. tan.

Algebra Tanszék