|
Széchenyi
István Egyetem |
Matematika és Számítástudomány Tanszék |
||||||||
|
Algoritmusok tervezése (NGB_SZ011_1) |
|||||||||
|
2010/2011 tanév II. félév |
|||||||||
|
Szakok: minden BSc-s szak, ahol a tárgyat tanulják |
|||||||||
|
Tantárgyfelelős: |
dr. Szörényi Miklós |
Oktató: |
Pukler Antal |
Tematika: |
Pukler Antal |
||||
|
Előtanulmányi
feltételek: |
(NGB_IN001_3) NGB_MA007_1 |
||||||||
|
Heti óraszámok: |
3 kontaktóra |
konzultáció |
2 önálló munka |
||||||
|
A félévzárás
módja: |
Vizsga |
Kreditérték: |
4 kreditpont |
||||||
|
A tananyag ütemezése |
|
|
Hetek |
Tananyagrész |
|
1. |
A követelmények ismertetése. Az algoritmus fogalma. Algoritmusok hatékonysága. Ismert egyszerű algoritmusok elemzése hatékonyság szempontjából. |
|
2. |
Rendező algoritmusok hatékonysága, átlagos- és legrosszabbeset-hatékonyság. Rendezés lineáris időben. |
|
3. |
Gráfok, fák. Gráfok, fák bejárása, kereső algoritmusok. (Mélységi, szélességi és egyenletes bejárás, keresés.) Utak a gráfban. |
|
4. |
A minimális és a maximális út keresése. |
|
5. |
Hálózatok, folyamhálózatok, vágások. Maximális folyam, minimális vágás. |
|
6. |
Optimumkeresés véges, diszkrét halmazokon. A megoldásfa. Leszámlálási algoritmusok. |
|
7. |
Leszámlálási algoritmusok: a B&B algoritmus. |
|
8. |
Leszámlálási algoritmusok: B&T algoritmus. Maximálisút-keresés B&T algoritmussal. |
|
9. |
Heurisztikus algoritmusok elvi működése. Néhány egyszerű feladat megoldása heurisztikával. |
|
10. |
Euler-körök gráfokban. A postás-probléma. |
|
11. |
Hozzárendelési feladat és a magyar-módszer. |
|
12. |
Hamilton-körök gráfokban. Az utazó ügynök probléma és megoldása B&B módszerrel. |
|
13. |
Az utazó ügynök probléma heurisztikus megoldási módszerei. |
|
14. |
Összefoglalás |
|
Félévközi követelmények |
|
|
Zárthelyik |
|
|
Oktatási hét |
Témakör, a lebonyolítás, az értékelés és a pótlás módja |
|
9. és 14. |
dolgozatírás |
|
A félévzárás módja, a tantárgyi jegy kialakításának szempontjai |
|
Az aláírás megszerzésének feltétele mindkét dolgozat megírása! (Ha valamelyik dolgozatot nem tudja valaki megírni, megfelelő igazolással megírottnak tekintendő.) A vizsgán öt kérdésre kell válaszolni, írásban. Két kérdés egy-egy - a félév során megismert - feladat leírása, két kérdés egy-egy algoritmus leírása, egy kérdés egy feladathoz algoritmuskészítés. A vizsga minimumfeltétele: a két feladat hibátlan ismertetése. |
|
Irodalom |
|
Kötelező irodalom |
|
Imreh Balázs - Imreh Csanád: Kombinatorikus optimalizálás |
|
Ajánlott irodalom |
|
Thomas et al: Algoritmusok (Új algoritmusok) |
Győr, 2010. február 10.
|
Tanszékvezető |
|
Tantárgyfelelős |
|
Oktató |
|
Hallgatói képviselő |