Kurzus nemzetközi vendég- és részidős hallgatóknak
- Kar
- Természettudományi Kar
- Szervezet
- TTK Számítógéptudományi Tanszék
- Kód
- bonyel1u0um17em
- Cím
- Bonyolultságelmélet (ea)
- Tervezett félév
- Őszi
- Meghirdetve
- 2024/25/1
- ECTS
- 3
- Nyelv
- hu
- Oktatás célja
- Tudás: a bonyolultságelmélet főbb fogalmainak elsajátítása Képesség: a tanult algoritmusokat összetett feladatok megoldására is használni tudja Attitűd: igény az alkalmazott matematikai tudás gyarapítására, új alkalmazott matematikai ismeretek megszerzésére, kompetenciák elsajátítására, kifejlesztésére. Törekvés a matematikai ismereteinek minél szélesebb körű alkalmazására Autonómia és felelősség: a bonyolultságelmélet témakörében elsajátított alapvető ismeretei felhasználásával képes önállóan megválasztani az alkalmazási problémák megoldására alkalmazható módszereket
- Tantárgy tartalma
- Kommunikációs bonyolultság. Döntési fák, rejtőzködés, Ben-Or tétele. Hierarchia-tételek, Sawitch tétel, orákulumok, a polinomiális hierarchia. A PSPACE-osztály, teljes nyelvek. Véletlenített bonyolultságosztályok. Pszeudovéletlen generátorok. Interaktív protokollok. Shamir tétele: IP=PSPACE. Nehéz problémák közelíthetősége és közelíthetetlensége, a PCP tétel. Alsó becslések Boole-hálózatokon. Párhuzamos algoritmusok aritmetikai problémákra, rendezésre, gráfproblémákra és lineáris algebrai feladatokra. Párhuzamos algoritmusok kisfokú hálózatokon. Kolmogorov-bonyolultság
- Számonkérés és értékelés
- kollokvium
- Ajánlott irodalom
- Lovász László: Algoritmusok Bonyolultsága, egyetemi jegyzet, ELTE 1999. Papadimitriou, Christos H. (1999): Számítási bonyolultság. Novadat Bt., Győr. Ivanyos, G., Rónyai, L., Szabó, R.: Algoritmusok, Budapest, TypoTeX Kiadó, 1998. Cormen, Leiserson, Rivest: Új algoritmusok, Scolar Kiadó, 2003.