Rendszeroptimalizálás

A tantárgy angol neve: System Optimisation

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

5. évfolyam - Elágazó II.

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VIMA5311 ősz 4/0/0/v 5 1/1
4. A tantárgy előadója

Név:

Beosztás:

Tanszék, Int.:

Dr. Recski András

egyetemi tanár

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

Szeszlér Dávid

egyetemi tanársegéd

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

Wiener Gábor

egyetemi adjunktus

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

A Bevezetés a Számításelméletbe I. és II. , valamint az Algoritmuselmélet tárgyak anyaga.

6. Előtanulmányi rend
Ajánlott:

-

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

A kombinatorikus optimalizálás legfontosabb algoritmusainak, módszereinek, korlátainak ismertetése, valamint betekintés ezek műszaki alkalmazásaiba (megbízható hálózatok tervezése, villamos hálózatok klasszikus elmélete, VLSI tervezés, statika területeken).

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

A lineáris programozás alapfeladata, megoldási módszerek, Farkas-lemma, dualitás, egészértékű programozás. Totális unimodularitás, alkalmazás páros gráfokra, Egerváry algoritmusa, alkalmazás hálózati folyamokra.

Matroidelméleti alapfogalmak (alaphalmaz, függetlenség, bázis, kör, rang), dualitás, minorok, direkt összeg, összeg. Matroidelméleti algoritmusok (mohó algoritmus, matroid partíciós és metszet-algoritmusok, orákulumok). Matroid párosítási probléma. Matroidok és gráfok kapcsolata, vektorreprezentáció, geometriai reprezentáció. Tutte tételei (biz. nélkül).

Közelítő algoritmusok, halmazfedési feladat, Steiner-fák, utazó ügynök probléma, nevezetes heurisztikák az utazó ügynök probléma euklideszi esetére.

Ütemezési feladatok, egygépes ütemezések, listás ütemező algoritmus párhuzamos gépek esetén, Hu algoritmusa, Coffman és Graham algoritmusa .

Alkalmazások a megbízható hálózatok tervezésében, az összefüggőség kiszámítása, Nagamochi és Ibaraki algoritmusa, Karger algoritmusa. Többszörösen összefüggő részgráfok, Khuller és Vishkin algoritmusa, Cheriyan és Thurimella algoritmusa. Az összefüggőség növelése, Plesnik algoritmusa.

Alkalmazások a VLSI hálózatok huzalozásában (Gallai tétele és az egyetlen pontsor huzalozhatósága a Manhattan-modellben, csatornahuzalozás 2 és több rétegen, ˛switchbox˛-huzalozás több rétegen, Frank A. tétele az éldiszjunkt huzalozásra és ennek következményei).

Alkalmazások a villamos hálózatok klasszikus elméletében, hálózatok egyértelmű megoldhatósága, a szabadsági fokok száma. Általánosítás többpólusú lineáris alkatrészeket is tartalmazó hálózatokra. Dualitás.

Alkalmazások a rúdszerkezetek merevségének vizsgálatában, a probléma kitűzése, átfogalmazása lineáris algebrai feltétellé, a merevség definíciója, generikus merevség, Laman tétele, Lovász és Yemini tétele, a 3-dimenziós analógia nehézségei, kapcsolat a poliéderek vetületből való rekonstrukciójával, minimális számú csuklóval való rögzítés. Négyzetrácsok merevítése átlós rudakkal.

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: egy zárthelyi, egy beadandó házi feladat

b. A vizsgaidőszakban: szóbeli vizsga

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

Az elégtelen zárthelyi javítására, vagy a zárthelyi pótlására lehetőséget biztosítunk a szorgalmi időszak végén.

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

Egyéni megbeszélés alapján.

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

Dr. Jordán Tibor - Dr. Recski András –- Szeszlér Dávid: Rendszeroptimalizálás, Typotex, Budapest, 2004

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

Kontakt óra

60

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

15

Felkészülés zárthelyire

15

Házi feladat elkészítése

10

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

..

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

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