Kurzus nemzetközi vendég- és részidős hallgatóknak

Kar

Informatikai Kar

Szervezet

IK Algoritmusok és Alkalmazásaik Tanszék

Kód

IPM-22feszAAG

Cím

Speciális algoritmusok Gy.

Tervezett félév

Őszi

Meghirdetve

2024/25/1

ECTS

3

Nyelv

en

Oktatás célja

tudás: Rendelkezik a szükséges matematikai és folyamatirányítási ismeretekkel, különösen a következő területeken: rendszer és irányításelmélet, numerikus módszerek, optimalizálási módszerek. Magas szinten, részleteiben ismeri, érti az informatikai szakterület szakmai szókincsét, kifejezési és fogalmazási sajátosságait angol nyelven. képesség: Képes komplex szakmai problémák formalizálására, a szükséges elvi és gyakorlati háttér feltárására és a probléma megoldására. Képes kezdeményező együttműködésre, projekt- (csoport-) munkára. Magas szinten képes a szakterület szakmai szókincsével angolul írásban és szóban megnyilvánulni, vitában részt venni, jelentést készíteni, tudományos, műszaki szakmai anyagokat (könyv, cikk stb.) feldolgozni és alkotó módon hasznosítani. Képes a szakmai információforrások professzionális használatára, a megoldandó problémához szükséges ismeretanyag kinyerésére, annak kritikai értelmezésére, értékelésére. Képes szakmai irányítás mellett önálló tudományos kutatómunkát végezni, felkészülni tanulmányainak posztgraduális képzés keretében történő folytatására. attitűd: Figyelemmel kíséri a képesítésével, informatikai szakterületével kapcsolatos szakmai, technológiai fejlődést. Elkötelezett az önvizsgálaton alapuló kritikai visszacsatolás és értékelés iránt. Elkötelezett az élethosszig tartó tanulás iránt, nyitott új informatikai szakmai kompetenciák elsajátítására. Elfogadja és munkatársaival is betartatja a munka- és szervezeti kultúra, továbbá az informatikai tudományos kutatás etikai elveit. Saját tudását megosztja, fontosnak tartja az informatikai szakmai eredmények közvetítését. Elkötelezett a minőségi követelmények betartatására és informatikai eszközökkel történő elemzésére. Nyitott a kezdeményező együttműködésre, az informatikai és más szakterületek szakembereivel. autonómia, felelősség: Informatikai tevékenysége során hozott szakmai döntéseiért felelősséget vállal. Felelősséget vállal a határidők betartására és betartatására. Felelősséget vállal a saját és az irányítása alatt dolgozó, illetve a vele együtt (egy projektben) tevékenykedő munkatársai munkájáért.

Tantárgy tartalma

Hálózatok és folyamok. Ford-Fulkerson algoritmus. Maximális folyam - minimális vágás tétel. Egészértékű folyamok. Edmonds-Karp heurisztikák. Maximális párosítás páros gráfokban. König-Hall tétel. Élidegen utak. Legsűrűbb feszített részgráfok. Hálózati folyamok alsó korlátokkal. Minimális és maximális vágás. Karger randomizált minimális vágás algoritmusa. Maximális vágás lokális kereséssel. Közelítő algoritmusok. Minimális összsúlyú éllefogó csúcshalmaz. Élidegen utak rögzített végpontokkal. Lehetetlenségi tételek.

Számonkérés és értékelés

Félévközi zárthelyik

Irodalomjegyzék

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. Fourth Edition. The MIT Press, 2022. J. Kleinberg, É. Tardos: Algorithm Design. Addison Wesley, 2006.

Kurzus szakjai