CZV_VT001 Efektivně řešitelné problémy

Celouniverzitní studia
jaro 2001
Rozsah
0/0. Ukončení: k.
Vyučující
prof. RNDr. Luboš Brim, CSc. (přednášející)
prof. RNDr. Ivana Černá, CSc. (přednášející)
Garance
prof. RNDr. Luděk Matyska, CSc.
Fakulta informatiky
Kontaktní osoba: prof. RNDr. Luboš Brim, CSc.
Předpoklady
Kurz Efektívně řešitelné problémy je primárně určen pro učitele předmětu Informatika/Vt a rovněž pro učitele předmětů Matematika a Fyzika, kteří buď informatiku nestudovali nebo ji studovali a chtějí s odstupem času lépe nahlédnout do podstaty konstrukce efektivních algoritmů. Kurz je rovněž vhodný i pro učitele jiných přírodovědných předmětů, kteří chtějí získat základ systematičtějšího vzdělání v informatice. U frekventantů kurzu se předpokládají základní matematické znalosti a výhodou je elementární znalost programování.
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.

Předmět si smí zapsat nejvýše 50 stud.
Momentální stav registrace a zápisu: zapsáno: 0/50, pouze zareg.: 0/50
Mateřské obory/plány
Cíle předmětu
Ústředním pojmem informatiky je pojem algoritmu. Otázky existence/neexistence algoritmů (efektivních výpočetních procedur) pro řešení problémů a důvodů pro jejich případnou neexistenci jsou zásadními otázkami informatiky. Ve své podstatě znamenají klasifikaci problémů podle jejich obtížnost. Jejich zodpovězení vyžaduje rigorozní a systematické studium fundamentálních informatických pojmů, jakými jsou zejména pojem výpočetního modelu a algoritmu. Tyto pojmy se vyznačují až překvapivou stabilitou, na rozdíl od technologických změn. Cílem kurzu je objasnit základní přístupy a metody klasifikace problémů z hlediska možnosti jejich algoritmického řešení a provést základní klasifikaci, poukázat na teoretické a praktické meze využití počítačů a důsledky, které tato omezení mají pro rozvoj informační technologií. Absolventi kurzu by měli: - orientovat se v pojmech rozhodnutelný a částečně rozhodnutelný problém - orientovat se v pojmech efektivní a prakticky nepoužitelný algoritmus - být schopni klasifikovat problémy podle jejich obtížnosti - být schopni používat standardní metody klasifikace problémů - být schopni aplikovat tyto metody na konkrétní problémy - pochopit teoretické a praktické meze využití počítačů a důsledky, které tato omezení mají pro rozvoj informační technologií
Osnova
  • - Problémy a algoritmy - Základní výpočetní modely (Turingovy stroje, stroje se zásobníky, RAM, PRAM) - Klasifikace problémů (rozhodnutelné problémy, nerozhodnutelné a částečně rozhodnutelné problémy, výpočetně těžké a lehké problémy) - Redukce a úplnost v třídách problémů (redukce, polynomiální redukce, NP-úplné problémy, úplné problémy z hlediska rozhodnutelnosti) - Nesekvenční výpočetní modely (paralelní výpočty, pravděpodobnostní algoritmy, aproximativní algoritmy) - Aplikace na konkrétní problémy
Literatura
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
  • BOVET, D. a Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • Theory of Recursive Functions and Effective Computability. Edited by Hartley Rogers. Cambridge: Massachusetts Institute of Technology, 1987, 482 s. ISBN 0262680521. info
  • KFOURY, A. J., Robert N. MOLL a Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Metody hodnocení
Kurz bude probíhat zejména formou distančního vzdělávání po dobu jednoho semestru. V průběhu tohoto semestru jsou plánována 2 až 3 soustředění na FI MU, která budou realizována formou konzultací o studované problematice. Kurz je součástí bloku kurzů, které organizuje Fakulta informatiky MU v Brně v rámci programu Celoživotní vzdělávání učitelů základních a středních škol. V průběhu kurzu budou frekventanti kurzu samostaně řešit zadané problémy, které napomohou lepšímu pochopení problematiky a přispějí ke zvládnutí používaných metod a technik. Kurz bude zakončen písemnou závěrečnou zkouškou, po jejímž úspěšném složení bude studentovi vystaveno osvědčení o absolvování kurzu.
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je vyučován jednorázově.
Poznámka k četnosti výuky: distanční formou.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/cus/jaro2001/CZV_VT001