CZV_VT001 Efektivně řešitelné problémy

Pan-university studies
Spring 2001
Extent and Intensity
0/0. Type of Completion: k (colloquium).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Luděk Matyska, CSc.
Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Prerequisites (in Czech)
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í.
Course Enrolment Limitations
The course is only offered to the students of the study fields the course is directly associated with.

The capacity limit for the course is 50 student(s).
Current registration and enrolment status: enrolled: 0/50, only registered: 0/50
fields of study / plans the course is directly associated with
Course objectives (in Czech)
Ú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í
Syllabus (in Czech)
  • - 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
Literature
  • 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. and 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 and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Assessment methods (in Czech)
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.
Language of instruction
Czech
Further comments (probably available only in Czech)
The course can also be completed outside the examination period.
The course is taught only once.
Note related to how often the course is taught: distanční formou.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/cus/spring2001/CZV_VT001