Studijní program Informatika

Oborová rada doktorského studijního programu Informatika

Aktuální složení rady je na adrese http://mff.cuni.cz/phd/or/i .


4I1 Teoretická informatika

Rada doktorského studijního oboru 4I1

Aktuální složení rady je na adrese http://mff.cuni.cz/phd/rdso/4i1 .

Spolupracující ústavy

Matematický ústav AV ČR, v.v.i.
Žitná 25, 115 67 Praha 1
http://www.cz.math.cas.cz
Ústav informatiky AV ČR, v.v.i.
Pod vodárenskou věží 2, 182 07 Praha 8
http://www.cs.cas.cz/
Ústav teorie informace a automatizace AV ČR, v.v.i.
Pod vodárenskou věží 4/1143, 182 08 Praha 8
http://www.utia.cas.cz/czech-info/
Ústav termomechaniky AV ČR, v.v.i.
Dolejškova 1402/5, 182 00 Praha 8
http://www.it.cas.cz/

Vypsaná témata

Jsou k nahlédnutí v SIS na adrese http://mff.cuni.cz/phd/temata/4i1 .

Poskytovaná výuka

kód Předmět ZS LS
NTIN006 Algebraické algoritmy   2/0 Zk
NTIN088 Algoritmická náhodnost   2/0 Zk
NTIN098 Pokročilé datové struktury   2/0 Zk
NAIL013 Aplikace teorie neuronových sítí   2/0 Zk
NDMI018 Aproximační a online algoritmy   2/2 Z+Zk
NAIL021 Booleovské funkce a jejich aplikace   2/0 Zk
NAIL078 Lambda-kalkulus a funkcionální programování I   2/1 Z+Zk
NAIL079 Lambda-kalkulus a funkcionální programování II   2/1 Z+Zk
NAIL076 Logické programování I   2/0 Zk
NAIL077 Logické programování II   2/0 Zk
NTIN017 Paralelní algoritmy   2/0 Zk
NAIL071 Plánování a rozvrhování   2/0 Zk
NDMI025 Pravděpodobnostní algoritmy   2/2 Z+Zk
NTIN097 Problémy na hyperkrychlích   2/0 Zk
NOPT042 Programování s omezujícími podmínkami   2/2 Z+Zk
NTIN096 Pseudo-Booleovská optimalizace   2/0 Zk
NAIL031 Reprezentace booleovských funkcí   2/0 Zk
NTIN050 Seminář z výpočetní složitosti   0/2 Z 0/2 Z
NDBI031 Statistické metody v systémech pro dobývání znalostí z dat   1/1 Z+Zk
NTIN081 Strukturální složitost   2/0 Zk
NTIN085 Vybrané kapitoly z výpočetní složitosti I   2/1 Z+Zk
NTIN086 Vybrané kapitoly z výpočetní složitosti II   2/1 Z+Zk
NTIN082 Výpočetní složitost   2/0 Zk

Seznam požadavků ke státní doktorské zkoušce

Pro obor 4I1 Teoretická informatika jsou povinná tři témata z uvedených okruhů, z toho jedno téma povinně z okruhů 1. a 2., a téma profilující podle dohody se školitelem:

1. Logika
Výrokový a predikátový počet, syntax a sémantika, jejich vztah. Formální systémy, formální aritmetika, bezespornost a úplnost, Goedelovy věty. Turingovy stroje. Algoritmicky nerozhodnutelné problémy, nerozhodnutelnost predikátové logiky, nerozhodnutelnost bezesporných rozšíření elementární aritmetiky. Nedefinovatelnost pravdy v aritmetice. Věty o rekurzi. Základy teorie modelů.

2. Teorie složitosti
Modely sekvenčních a paralelních počítačů. Booleovské formule a obvody, větvící se programy. Míry složitosti. Nedeterministické, alternující a interaktivní výpočty. Třídy složitosti, redukce a úplné úlohy, polynomiální hierarchie. Výrokové kalkuly a jejich složitost. Dolní odhady pro explicitní funkce a formule. Náhodnost a pseudonáhodnost. Komunikační složitost a její aplikace. Základy teorie informace.

3. Diskrétní matematika
Grafové algoritmy, souvislost grafů, barvení grafů, extremální problémy, Ramseyovy věty, náhodné grafy, náhodné procházky v grafech, lineární programování a dualita, vztah grafů matic a polynomů. Samoopravné kódy.

4. Algoritmy
Deterministické, pravděpodobnostní a paralelní algoritmy. Návrh efektivních algoritmů a jejich analýza. Efektivní datové struktury a jejich analýza. Efektivní algoritmy pro lineární programování a jejich aplikace. Metody pro řešení obtížných úloh: aproximační algoritmy, schémata a heuristické metody. Základní kryptografické protokoly.

5. Umělá inteligence
Reprezentace znalostí, automatické dokazování, rezoluční metoda. Booleovská splnitelnost, splňování omezujících podmínek. Deklarativní programovací jazyky. Prohledávání stavového prostoru, metaheuristiky a jejich příklady a aplikace, lokální prohledávání. Plánování akcí. Práce s neurčitostí, Bayesovské sítě. Strojové učení, metody pro dobývání znalostí. Kognitivní systémy. Multiagentní systémy a teorie her. Neuronové sítě, jejich modely, aplikace a vlastnosti. Evoluční algoritmy.

Doporučená literatura

1. Logika:
Demuth, O., Kryl, R., Kučera, A.: Teorie algoritmů I, II. SPN, Praha, 1989.
Nies, A.: Computability and randomness. Oxford University Press, Oxford, 2009.
Rautenberg W.: A concise introduction to mathematical logic. Springer, 2010.
Štěpánek, P.: Meze formální metody. Text přístupný na http://ktiml.mff.cuni.cz/index.php?… .
Štěpánek, P.: Predikátová logika. Text přístupný na http://ktiml.mff.cuni.cz/index.php?… .
Švejdar, V.: Logika: neúplnost, složitost a nutnost. Academia, Praha, 2002.
2. Teorie složitosti:
Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Text přístupný na http://theory.cs.princeton.edu/complexity/ .
Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation. Addison–Wesley, Reading, MA, 1979.
Hromkovič, J.: Communication Complexity and Parallel Computing. Springer–Verlag, Berlin, 1997.
Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, Cambridge, 1997.
Papadimitriou, C. H.: Computational Complexity. Addison–Wesley, Reading, MA, 1994.
Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston, 1997.
Jukna S.: Boolean Function Complexity: Advances and Frontiers. Springer–Verlag, 2012.
Cover T.M., Thomas, J.A.: Elements of Information Theory. John Wiley & Sons, 2nd edition, 2006.
3. Diskrétní matematika:
Alon, N., Spencer, J.: The Probabilistic Method. Wiley, 2001.
Diestel, R.: Graph Theory. 2nd ed., Springer–Verlag, 2000.
Bollobás, B.: Modern Graph Theory. Corr. ed., Springer–Verlag, 2002.
van Lint, J. H.: Introduction to Coding Theory. 3rd. ed., Springer–Verlag, 1999.
Matoušek, J., Gärtner, B.: Understanding and Using Linear Programming. Springer–Verlag, 2006.
Jukna, S.: Extremal Combinatorics. Springer–Verlag, 2011.
4. Algoritmy:
Kleinberg, J., Tardos, E.: Algorithms Design. Addison–Wesley, Reading, MA, 2005.
Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press, Cambridge, 1995.
Vazirani, V. V.: Approximation Algorithms. Springer–Verlag, 2001.
Williamson, D. P., Shmoys, D. B.: The Design of Approximation Algorithms. Cambridge University Press, 2011.
Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge Univeristy Press, 2005.
Matoušek, J., Gärtner, B.: Understanding and Using Linear Programming. Springer–Verlag, 2006.
5. Umělá inteligence:
Aggarwal, C. C.: Data Mining: The Textbook. Springer–Verlag, 2015.
Eiben, A. E., Smith, J. E.: Introduction to Evolutionary Computing. 2nd ed., Springer, 2007.
Ghallab, M., Nau, D., Traverso, P.: Automated Planning: Theory and Practice. Morgan Kaufmann, 2004.
Haykin, S.: Neural Networks: A Comprehensive Foundation. 3rd ed., Pearson, 2009.
Rossi, F., Beek van, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier, 2006.
Russell, S. J., Norvig, P.: Artificial Intelligence: A Modern Approach. 3rd ed., Pearson, 2009.

4I2 Softwarové systémy

Rada doktorského studijního oboru 4I2

Aktuální složení rady je na adrese http://mff.cuni.cz/phd/rdso/4i2 .

Spolupracující ústavy

Matematický ústav AV ČR, v.v.i.
Žitná 25, 115 67 Praha 1
http://www.cz.math.cas.cz
Ústav informatiky AV ČR, v.v.i.
Pod vodárenskou věží 2, 182 07 Praha 8
http://www.cs.cas.cz/
Ústav teorie informace a automatizace AV ČR, v.v.i.
Pod vodárenskou věží 4/1143, 182 08 Praha 8
http://www.utia.cas.cz/czech-info/

Vypsaná témata

Jsou k nahlédnutí v SIS na adrese http://mff.cuni.cz/phd/temata/4i2 .

Poskytovaná výuka

kód Předmět ZS LS
NSWI132 Analýza programů a verifikace kódu   2/2 Z+Zk
NSWI080 Middleware   2/1 Z+Zk
NSWI101 Modely a verifikace chování systémů   2/2 Z+Zk
NSWI029 Moderní trendy v informatice   0/2 Z 0/2 Z
NDBI033 Netradiční databázové modely, architektury a jazyky   2/0 Zk
NSWI068 Objektové a komponentové systémy   2/2 Z+Zk
NTIN055 Paralelní architektury   2/0 Zk
NPRG042 Programování v paralelním prostředí   2/2 Z+Zk
NSWI103 Řízení projektů Systémová dynamika I   0/2 Z
NSWI104 Řízení firem Systémová dynamika II   0/2 Z
NTIN083 Seminář z datových struktur I   0/2 Z
NTIN021 Seminář z datových struktur II   0/2 Z
NDBI019 Stochastické metody v databázích   2/0 Zk
NDBI016 Transakce   2/0 Zk
NSWI057 Výběrový seminář z distribuovaných a komponentových systémů I   0/4 Z
NSWI058 Výběrový seminář z distribuovaných a komponentových systémů II   0/4 Z

Seznam požadavků ke státní doktorské zkoušce

Tématické celky 1 a 2 jsou povinné. K nim si uchazeč po dohodě se školitelem zvolí z uvedených celků další dva a dále jedno profilující téma podle svého zaměření. Zde bude požadována znalost nejnovějších výsledků podle pokynů školitele. Toto páté (profilující) téma nemusí být z níže uvedeného seznamu, určí je předseda RDSO 4I2 na návrh školitele. Výběr a upřesnění témat pro státní doktorskou zkoušku jednotlivého doktoranda schvaluje RDSO 4I2.

1. Teoretické základy informatiky
Diskrétní matematika: Základy teorie grafů, reprezentace grafů v paměti, algoritmy nad grafy.

Algebra, logika, algoritmy: Vybrané algebraické struktury, univerzální algebry. Predikátový počet. Formální systémy, bezespornost a úplnost, Goedelovy věty. Rozhodnutelnost formálních systémů, teorie modelů. Unifikace. Teorie vyčíslitelnosti, Turingovy stroje a ekvivalentní modely výpočtu. Algoritmy a jejich složitost, NP–úplné problémy. Algoritmicky nerozhodnutelné problémy. Věty o rekurzi.

2. Teoretické základy softwarových systémů
Formální jazyky, gramatiky a automaty. Formální modely a specifikace sémantiky jazyků. Atributové gramatiky. Formální sémantika souběžných systémů, přechodové systémy jako sémantika nízké úrovně; ekvivalence, model checking, modely souběžných systémů, Petriho sítě, algebraické modely, CCS a CSP. Verifikace souběžných systémů v praxi. Metody formálních a algebraických specifikací. Lambda kalkul, typové systémy.

3. Jazyky a překladače:
Přehled konceptů programovacích jazyků (procedurálních i neprocedurálních). Struktura překladače typického procedurálního jazyka. Syntaktická analýza, LL, LR a GLR metody, RRP gramatiky. Atributové gramatiky. Principy implementace jazyků s vnořenou strukturou procedur a objektových jazyků, late binding. Sekvenční a deklarativní mezikódy, základní bloky. Detekce závislostí, SSA mezikódy. Typické vlastnosti moderních procesorů z hlediska generování kódu. Metody alokace registrů. Generování a optimalizace kódu s paralelismem na úrovni instrukcí. Scheduling, list scheduling, trace scheduling, software pipelining.

4. Distribuované systémy
Architektury distribuovaných systémů. Komunikace, zasílání zpráv, RPC, skupinová komunikace, doručovací protokoly. Distribuované synchronizační algoritmy — vzájemné vyloučení procesů, volba koordinátora, detekce globálního stavu, algoritmy pro distribuovaný konsenzus. Distribuované souborové systémy, replikace souborů, správa prostorů jmen. Migrace procesů, vyvažování zátěže. Distribuované sdílení paměti, konzistenční modely, distribuované stránkování.

5. Operační systémy
Architektura počítačů. Koncepty a protokoly počítačových sítí. Koncepce, struktura a realizace operačních systémů. Abstrakce poskytované jádrem operačního systému. Koncepce mikrojádra, abstrakce a techniky pro správu paměti a procesů mimo jádro. Synchronizace paralelních procesů a vhodné synchronizační nástroje a jejich implementace včetně multiprocesorových a paralelních systémů. Virtualizace paměti při rozsáhlých adresových prostorech. Síťové a distribuované systémy souborů, speciální systémy souborů pro zvláštní média, systémy souborů s malou režií, s velkou spolehlivostí, transakční systémy souborů, žurnálové systémy souborů.

6. Databázové systémy
Konceptuální modely. Relační model dat — teorie závislostí, dotazovací jazyky — jejich vyjadřovací síla a složitost, neúplné informace, složité objekty. Logika jako databázový jazyk: Datalog a jeho sémantika, deduktivní databáze. Modely objektových databází, objektové dotazovací jazyky, teorie typů. Implementační problémy databází — datové struktury vhodné pro indexaci, transakční modely, optimalizační problémy. Nové databázové architektury: datové sklady, multidimenzionální databáze, databáze a Web, XML databáze.

7. Objektové systémy
Koncepty jazyků založených na třídách (dědičnost a delegování, subsumption, typové informace, kovariance, kontravariance, typ self, rozlišování podtříd a podtypů, parametrizace typů). Koncepty jazyků bez tříd (prototypování a klonování, delegování, dynamická dědičnost). Koncept \uv{mixin}. Aspektově orientované programování. Objektové modely pro distribuovaná prostředí. Komponentové modely. Protokoly chování objektů a komponent. Objektové modelování a návrh, principy podpůrných nástrojů. Vývoj založený na modelech. Implementační techniky konstrukcí objektových jazyků.

8. Techniky síťových aplikací
Architektura síťových aplikaci, klient–server a vícestupňové (n–tier) architektury, federace služeb, agenti. Komunikační middleware, standardy, rozhraní. Technologie pro klient–server a vícestupňové (n–tier) aplikace, applety, servlety, transakční middleware, aplikační servery. Platformy pro mobilní výpočty. Ad hoc a senzorové sítě. Prostředky interoperability, datové formáty, protokoly. Bezpečnost, kryptografické techniky pro šifrování a autentizaci.

9. Softwarové inženýrství
Předmět SW inženýrství, příčiny úspěchu a neúspěchu SW projektů. Strategické cíle informačních systémů, zájmové skupiny. Sociální důsledky používání informačních technologií. Základy počítačové ergonomie (RSI). Příprava projektu, analýza rizik, marketing a principy vyjednávání. Business process reingeneering, outsourcing. Techniky zjišťování požadavků. Oponentury při vývoji SW. SW prototypy. Procesy používané při vývoji softwaru. Softwarové metriky. Odhady SW metrik (COCOMO, Function Points). Principy řízení projektů a organizace týmů. SW architektury, middleware, XML. Diagramy pro specifikaci a návrh SW. Notace a diagramy pro dokumentaci SW artefaktů, modelování SW. Testování a řízení konfigurace. Předání SW díla a jeho údržba. SW dokumentace. Hodnocení SW. Techniky vývoje uživatelského rozhraní.

Doporučená literatura

1. Teoretické základy informatiky
Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C.: Introduction to Algorithms. 2nd ed. MIT Press, 2001.
Demuth. O., Kryl, R., Kučera, A.: Teorie algoritmů I, II. SPN, Praha, 1989.
Garey, M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP–completeness. W. H. Freeman, San Francisco, 1978.
Hopcroft, J. E., Motwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation. 3rd ed. Addison–Wesley, 2007.
McKenzie, R. N., McNulty, G. F., Taylor, W. F.: Algebras, Lattices, Varieties. Advanced Books and Software, Wadsworth and Brooks/Cole, Monterey, 1987.
Mehlhorn, K.: Data Structures and Algorithms 2: Graph Algorithms and NP–completeness. EATCS – monograph, Springer–Verlag, 1984.
Soare, R. I.: Recursively enumerable sets and degrees. Springer–Verlag, 1987.
Tarjan, R. E.: Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, 1983.
2. Teoretické základy softwarových systémů
Emerson, E. A.: Temporal and Modal Logic. Volume B of Handbook of TCS, Elsevier, 1990, p. 995–1072.
Esparza, J.: Decidability and Complexity of Petri Net Problems – an Introduction. Lectures on Petri Nets I: Basic Models. Advances in Petri Nets, LNCS 1491, Springer–Verlag, 1988, p. 374–428.
McMillan, K.: Symbolic Model–Checking. Kluwer, 1993.
Milner, R.: Communication and Concurrency. Prentice Hall, 1995.
Peterson, J. L.: Petri Net Theory and the Modelling of Systems. Prentice Hall, 1981.
Vardi, M.: An Automata–Theoretic Approach to LTL. Logics for Concurrency, LNCS 1043, Springer–Verlag, 1996, p. 238–263.
Clarke, E. M., Grumberg, O., Peled, D. A.: Model Checking. The MIT Press, 1999, ISBN 978–0262 032 704.
Nielson, F., Nielson, H. R., Hankin, C.: Principles of Program Analysis. Springer, 2004, ISBN 978–3540 654 100.
3. Jazyky a překladače
Grune, D., Bal, H. E., Jacobs, C. J. H., Langendoen, K. G.: Modern Compiler Design. J. Wiley, 2000.
Aho, A. V., Lam, M. S., Sethi, R., Ullman, J. D.: Compilers: Principles, Techniques, and Tools (2nd Edition). Addison Wesley, 2006, ISBN 978–0321 486 813.
Grune, D., van Reeuwijk, K., Bal, H., Jacobs, C., Langendoen, K.: Modern Compiler Design. Springer, 2012, ISBN 978–1461 446 989.
Muchnick, S.: Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997, ISBN 978–1558 603 202.
Allen, R., Kennedy, K.: Optimizing Compilers for Modern Architectures: A Dependence–Based Approach. Morgan Kaufmann, 2001, ISBN 978–1558 602 861.
Shen, J. P., Lipasti, M. H.: Modern Processor Design: Fundamentals of Superscalar Processors. Waveland Press, 2013, ISBN 978–1478 607 830.
4. Distribuované systémy
Attiya, H., Welch, R.: Distributed Computing — Fundamentals, Simulations and Advanced Topics. 2nd ed. Wiley Interscience, 2004.
Mullender, S.: Distributed Systems. 2nd ed. Addison–Wesley, 1993.
Tanenbaum, A.: Distributed Operating Systems. Prentice Hall, 1994.
Tanenbaum, A.: Distributed Systems: Principles and Paradigms. 2nd ed. Prentice Hall, 2006.
Coulouris, G., Dollimore, J., Kindberg, T., Blair, G.: Distributed Systems: Concepts and Design (5th Edition). Pearson, 2011, ISBN 978–0132 143 011.
Fokkink, W.: Distributed Algorithms: An Intuitive Approach. The MIT Press, 2013, ISBN 978–0262 026 772.
5. Operační systémy
Boykin, J., Kirschen, D., Langerman, A., LoVerso, S.: Programming under Mach. Addison–Wesley, 1993.
Chow, R., Johnson, T.: Distributed Operating Systems and Algorithms. Addison–Wesley, 1997.
Schimmel, C.: Unix Systems for Modern Architectures. Addison–Wesley, 1994.
Stallings, W.: Operating Systems, Internals and Design Principles. 6th ed. Prentice Hall, 2008.
Vahalia, U.: Unix Internals. 2nd ed. The new Frontiers, Prentice Hall, 2001.
Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming (Revised Reprint). Morgan Kaufmann, 2012, ISBN 978–0123 973 375.
Love, R.: Linux Kernel Development (3rd Edition). Addison-Wesley, 2010, ISBN 978–0672 329 463.
Russinovich, M., Solomon, D., Ionescu, A.: Windows Internals (6th Edition). Microsoft Press, 2012, ISBN 978–0735 648 739 a 978–0735 665 873.
6. Databázové systémy
Abiteboul, S., Buneman, P., Suciu, D.: Data on the web: from relations to semistructured data and XML. Morgan Kaufmann, San Francisco, 2000.
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison–Wesley, 1995.
Atzeni, P., DeAntonellis, V.: Relational Database Theory. Benjamin & Cummings Publ. Co., Menlo Park, California, 1993.
Atzeni, P.: Database systems: concepts, languages and architectures. McGraw–Hill, London, 1999.
Garcia–Molina, H., Ullman, J., Widom, J.: Database System Implementation. Prentice Hall, 2000.
Gray, J., Reuter, A.: Transaction processing: concepts and techniques. Kaufmann, San Mateo, 1993.
Thalheim, B.: Entity–Relationship Modeling Foundations of Database Technology. Springer–Verlag, 2000.
Ullman, J. D.: Principles of Database and Knowledge–Base Systems. Volume I. Computer Science Press, 1988.
Ullman, J. D.: Principles of Database and Knowledge–Base Systems. Volume II. Computer Science Press, 1989.
Silberschatz, A. H., Korth, H. F., Sudarashan, S.: Database System Concepts (6th Edition). McGraw-Hill, 2010, ISBN 978–0073 523 323.
Garcia-Molina, H., Ullman, J.D., Widom, J.: Database Systems: The Complete Book (2nd Edition). Pearson, 2008, ISBN 978–0131 873 254.
Sakr, S., Pardede, E.: Graph Data Management: Techniques and Applications. IGI Global, 2012, ISBN 978–1613 500 538.
Sakr, S., Gaber, M.: Large Scale and Big Data: Processing and Management. CRC Press, 2014, ISBN 978–1466 581 500.
7. Objektové systémy
Abadi, M., Cardelli, L.: A theory of Objects. Corrected ed. Springer–Verlag, 1998.
Eliens, A.: Principles of Object–Oriented Software Development. 2nd ed. Addison–Wesley, 2000.
Leavens, G. T., Sitaraman, M. (eds.): Foundations of Component–based Systems. Cambridge University Press, Cambridge, 2000.
Miles, R.: AspectJ Cookbook. O'Reilly, 2004.
Pierce, B.: Types and Programming Languages. MIT Press, 2002.
Plášil, F., Stahl, M.: An Architectural view of distributed objects and components in CORBA, Java RMI and COM/DCOM. Software Concepts andvTools, vol. 19, no. 1, Springer–Verlag, 1998.
Rausch, A. et al.: The Common Component Modeling Example: Comparing Software Component Models. Springer–Verlag, 2008.
Stahl, T., Volter, M.: Model–driven Software Development. J. Wiley & Sons, 2006.
Szyperski, C.: Component Software: Beyond Object–Oriented Programming. 2nd ed. Addison–Wesley, 2002.
Tate, B. A.: Seven Languages in Seven Weeks: A Pragmatic Guide to Learning Programming Languages. The Pragmatic Bookshelf, 2010, ISBN 978–1934 356 593.
Fogus, M., Houser, C.: Joy of Closure. Manning Publications, 2011.
Koenig, D., Glover, A., King, P., Laforge, G., Skeet, J.: Groovy in Action. Manning Publications, 2007.< /I>
Brown, G. T.: Ruby Best Practices. O'Reilly Media, 2009.
Odersky, M., Spoon, L., Venners, B.: Programming in Scala (2nd Edition). Artima, 2010.
Flanagan, D.: JavaScript: The Definitive Guide. O'Reilly Media, 2011.
Ghosh, D.: DSLs in Action. Manning Publications, 2010.
8. Techniky síťových aplikací
Attiya, H., Welch, R.: Distributed Computing — Fundamentals, Simulations and Advanced Topics. 2nd ed. Wiley Interscience, 2004.
Baker, S.: CORBA Distributed Objects, Using Orbix. Addison–Wesley, 1997.
Krakowiak, S. et al: Advances in Distributed Computing: From Algorithms to Systems. Springer–Verlag, 2000.
Microsoft: Microsoft .NET Architecture. Text přístupný na http://www.microsoft.com .
OASIS: Web Service Standard Specifications. http://www.oasis-open.org .
Object Management Group: Common Object Request Broker Architecture. Text přístupný na http://www.omg.org .
Orfali, R. et al: Client/Server Survival Guide. 3rd ed. J. Wiley & Sons, 1999.
Pfleeger, Ch.: Security In Computing. 4th ed. Prentice Hall, 2006.
Sun Microsystems: Enterprise Java. Text přístupný na http://www.sun.com .
Woolf, B., Hohpe, G.: Enterprise Integration Patterns: Designing, Building, and Deploying Messaging Solutions. TBS, 2003, ISBN 978–8131 725 085.
9. Softwarové inženýrství
Adair, J.: Vytváření efektivních týmů. Management Press, Praha, 1994.
Arlow, J., Neustadt, I.: UML 2 a unifikovaný proces vývoje aplikací. Computer Press, 2007.
Fowler, M.: UML Distilled: A Brief Guide to the Standard Object Modeling Language. 3rd ed. Addison–Wesley, 2003.
Hall, E. M.: Managing Risks — Methods for Software Systems Development. Addison–Wesley, 1998.
Jarvis, A., Kehoe, R.: A Tool for Software Products and Process Improvement. Springer–Verlag, 1996.
Koubek, J.: Řízení lidských zdrojů — Základy moderní personalistiky. Management Press, Praha, 1999.
Král, J.: Informační systémy. Science Veletiny, 1998.
Landauer, T. K.: The Trouble with Computers. MIT Press, 1995.
Larman, C.: Applying UML and Patterns: An Introduction to Object–Oriented Analysis and Design and Iterative Development. 3rd ed. Prentice Hall, 2007.
Lax, D. A., Sebenius, J. K.: Manažer jako vyjednavač. Victoria Publ., Praha, 1994.
Moore, J. W.: Software Engineering Standards — A User Road Map. IEEE, Los Alamitos, Ca., 1998.
Nielsen, J.: Usability Engineering. Academic Press, 1995.
Pressman, R. S.: Software Engineering — A Practiticioner Approach. 6th ed. McGraw–Hill, 2004.
Sommerville, I.: Software Engineering. 8th ed. Addison–Wesley, 2008.
Steward, C. J., Steward, C.: Interviewing Principles and Practices. Oracle Co., Berkshire, 1994.
Bourque, P., Fairley, R. E.: Guide to the Software Engineering Body of Knowledge (Version 3.0). IEEE Computer Society, 2014.

4I3 Matematická lingvistika

Rada doktorského studijního oboru 4I3

Aktuální složení rady je na adrese http://mff.cuni.cz/phd/rdso/4i3 .

Spolupracující ústavy

Matematický ústav AV ČR, v.v.i.
Žitná 25, 115 67 Praha 1
http://www.cz.math.cas.cz

Vypsaná témata

Jsou k nahlédnutí v SIS na adrese http://mff.cuni.cz/phd/temata/4i3 .

Poskytovaná výuka

kód Předmět ZS LS
NPFL004 Seminář z formální lingvistiky   0/2 Z 0/2 Z
NPFL006 Úvod do formální lingvistiky   2/0 Zk
NPFL024 Syntaktická analýza češtiny   0/2 Z
NPFL015 Metody automatizovaného překladu   0/2 Z
NPFL054 Úvod do strojového učení   2/2 Z+Zk
NPFL067 Statistické metody zpracování přirozených jazyků I   2/2 Z+Zk
NPFL068 Statistické metody zpracování přirozených jazyků II   2/2 Z+Zk
NPFL073 Matematické metody v lingvistice   0/2 Z
NPFL070 Zdroje lingvistických dat   1/2 KZ
NPFL083 Lingvistická teorie a gramatické formalismy   2/2 Z+Zk
NPFL079 Algoritmy rozpoznávání mluvené řeči   2/2 Z+Zk
NPFL087 Statistický strojový překlad   2/2 Z+Zk
NPFL075 Pražský závislostní korpus   2/2 Z+Zk
NPFL094 Morfologická a syntaktická analýza   2/0 KZ
NPFL095 Moderní metody v počítačové lingvistice   0/2 Z
NPFL110 Moderní metody v počítačové lingvistice II   0/2 Z
NPFL097 Vybrané problémy ve strojovém učení   0/2 Z
NPFL098 Automatické zpracování textových dat   2/2 Z+Zk
NPFL099 Statistické dialogové systémy   2/1 Z+Zk
NPFL100 Variabilita jazyků v čase a prostoru   1/1 Z
NPFL103 Vyhledávání informací   2/2 Z+Zk
NPFL104 Metody strojového učení   1/2 Z+Zk
NPFL106 Obecná lingvistika   1/1 KZ
NPFL108 Bayesovská inference   2/1 Z(+Zk)
NPFL109 Číslicové zpracování zvukových signálů   2/2 Z+Zk

Seznam požadavků ke státní doktorské zkoušce

Zkouška se skládá ze dvou částí. Téma první části stanoví uchazeč po dohodě se školitelem v návaznosti na zadanou doktorskou disertační práci. Ve druhé části jsou kladeny otázky ze tří okruhů. Okruh 1 je povinný a ze zbývajících okruhů 2 až 5 uchazeč volí dva.

1. Základní přístupy k počítačovému zpracování přirozeného jazyka
Typy úloh v počítačovém zpracování přirozeného jazyka, matematické a lingvistické základy. Lingvistická data, korpusy, anotace. Návrh a vyhodnocení lingvistických experimentů, evaluační metriky. Základy teorie grafů. Systém rovin popisu jazyka. Obecná lingvistika, jazyková typologie. Morfologie a syntax přirozeného jazyka. Automaty a gramatiky, složková syntax, Chomského hierarchie. Závislostní syntax, vlastnosti závislostních stromů. Jazykové modelování.

2. Formální lingvistika
Strukturní lingvistika a její zdroje. Formální popis přirozeného jazyka. Závislostní přístupy. Funkční generativní popis. Pražský závislostní korpus. Model ,,smysl—text''. Vývoj Chomského teorie gramatiky. Další základní gramatické formalismy (HPSG, LFG, kategoriální gramatiky, (L)TAG). Fonetika. Fonologie. Morfologie. Syntax. Počítačová lexikografie. Aktuální členění věty; informační struktura, diskurz. Koreference.

3. Statistické metody a strojové učení v počítačové lingvistice
Pravděpodobnostní modelování jazyka. Metody řízeného učení pro klasifikaci a regresi. Lineární a nelineární metody. Support Vector Machines a kernelové funkce. Logistická regrese. Rozhodovací stromy. Metody neřízeného učení. Jazykové modely a modely kanálu. Vyhlazování modelů. Skryté Markovovy modely (algoritmy Baum–Welch, Forward–Backward, Viterbi). Algoritmy pro statistický tagging. Algoritmy pro složkový a závislostní statistický parsing. Statistický strojový překlad. Základy neuronových sítí pro využití v počítačovém zpracování jazyka. Testy signifikance.

4. Aplikace metod pro zpracování textu
Typy jazykových korpusů a jejich vlastnosti. Nástroje pro vyhledávání v jazykových korpusech. Víceznačnost v jazyce a metody jejího řešení v NLP. Kontrola překlepů, kontrola gramatické správnosti. Strojový překlad. Počítačem podporovaný překlad. Vyhodnocování kvality překladu. Vyhledávání informací, vyhledávací modely. Rozšiřování dotazů. Shlukování dokumentů. Vyhledávání na webu. Hledání duplicit a detekce plagiátorství. Evaluace vyhledávání informací. Postojová analýza.

5. Aplikace metod pro zpracování mluvené řeči
Metody zpracování řečového signálu. HMM modelování akustiky fonému. Implementace Baum-Welch a Viterbi algoritmu pro rozpoznáváni řeči. Adaptační techniky. Sumarizace řečových nahrávek. Vyhledávání témat a slov v řečových korpusech. Rozpoznávání mluvčího. Generování promluvy. Metody syntézy řeči. Zpracování textu pro syntézu řeči, prozodie. Základní komponenty dialogového systému. Porozumění mluvené řeči. Stav dialogu, řízení dialogu. Hodnocení kvality dialogových systémů.

Doporučená literatura

1. Základní přístupy k počítačovému zpracování přirozeného jazyka
Allen, J.: Natural Language Understanding. The Benjamins/Cummings Publishing Company, Inc., Rewood City, 1994.
Hajičová, E., Sgall, P., Panevová, J.: Úvod do teoretické a počítačové lingvistiky. Svazek 1 Teoretická lingvistika. Karolinum, Praha, 2002.
Hopcroft, J. E., Rajeev, M., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation. 3rd ed. Adison Wesley, 2006.
Chytil, M: Automaty a gramatiky. SNTL, Praha, 1984.
Nešetřil, J.: Teorie grafů. SNTL, Praha, 1979.
Partee, B. H., Meulenter, A., Wall, R.: Mathematical Methods in Linguistics. corrected 1st ed. Kluwer, Dordrecht, 1993.
Peregrin, J.: Úvod do teoretické sémantiky. FF MU, Brno, 1994.
Skalička, V.: Typ češtiny. Souborné dílo V. Skaličky, díl II. Karolinum, Praha, 2004, s. 475–536.
Štěpánek, P.: Predikátová logika. Text přístupný na http://ktiml.mff.cuni.cz/index.php?… .
2. Formální lingvistika
Abeillé, A., Rambow, O. (eds.): Tree Adjoining Grammar: An Overview. Tree Adjoining Grammars. Formalisms, Linguistic Analysis and Processing. The University of Chicago Press, 2000.
Čermák, F.: Jazyk a jazykověda. 3. vydání. Karolinum, 1997.
Černý, J.: Dějiny lingvistiky. Votobia, Olomouc, 1997.
Chomsky, N.: Syntaktické struktury. Academia, Praha, 1966.
Kahane, S.: The Meaning–Text Theory. In Agel, V. et al (eds.) Dependency and Valency. An International Handbook of Contemporary Research. De Gruyter, Berlin, 2004, p. 546–569.
Lopatková, M., Plátek, M., Sgall, P.: Towards a Formal Model for Functional Generative Description: Analysis by Reduction and Restarting Automata. The Prague Bulletin of Mathematical Linguistics 87, 2007, p. 7–26.
Mathesius, M.: Jazyk, kultura a slovesnost. Odeon, Praha, 1982.
Mel'chuk, I. A.: Dependency Syntax: Theory and Practice. State University of New York, Albany, 1988.
Panevová, J.: Formy a funkce ve stavbě české věty. Academia, Praha, 1980.
Saussure de, F.: Kurs obecné lingvistiky. Odeon, Praha, 1989.
Sgall, P.: Language in Its Multifarious Aspects. Karolinum, Praha, 2006.
Steedman, M.: The Syntactic Process (Language, Speech and Communication). The MIT Press, 2001.
Šmilauer, V.: Novočeská skladba. SPN, Praha, 1966.
3. Statistické metody a strojové učení v počítačové lingvistice
Alpaydin, E.: Introduction to Machine Learning. MIT Press, 2004.
Bishop, C.: Pattern Recognition and Machine Learning. Springer, 2007.
Duda, R. O., Hart, P. E.: Pattern Classification 2nd ed. Wiley–Interscience, 2000.
Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference and Prediction. Springer, 2001.
Koehn, P.: Statistical Machine Translation. Cambridge University Press New York, 2010.
Kübler, S., McDonald, R., Nivre, J.: Dependency Parsing. Morgan and Claypool Publishers, 2009
Manning C. D., Schuetze, H.: Foundations of Statistical Natural Language Processing. MIT Press, Cambridge, 1999.
Ripley, B. D.: Pattern Recognition and Neural Networks. Cambridge University Press, Cambridge, 1996.
Venables, W. N., Ripley, B. D.: Modern Applied Statistics with S. 4th ed. Springer, 2003.
4. Aplikace metod pro zpracování textu
Aggarwal, C., Zhai, C.: Mining Text Data. Springer, 2012
Cruse, D. A.: Lexical Semantics. Cambridge University Press, Cambridge, 1986.
Čermák F., Blatná R. (eds.): Korpusová lingvistika: Stav a modelové přístupy. Nakl. Lidové noviny, Praha, 2006.
Čermák, F., Klímová, J., Petkevič, V. (eds.): Studie z korpusové lingvistiky. AUC – Philologica 3–4. Karolinum, Praha, 2000.
Hajič, J.: Disambiguation of Rich Inflection: Computational Morphology of Czech. Karolinum, Praha, 2004.
Manning, C., Raghavan, P., Schuetze, H.: Introduction to Information Retrieval. Cambridge University Press, 2008.
Těšitelová, M.: Otázky lexikální statistiky. Academia, Praha, 1974.
5. Aplikace metod pro zpracování mluvené řeči
Jelinek, F.: Statistical Methods for Speech Recognition. MIT Press, 1997.
Lemon, O., Pietquin, O.: Data-Driven Methods for Adaptive Spoken Dialogue Systems: Computational Learning for Conversational Interfaces. Springer, Springer New York, 2012.
Pieraccini, R., Suendermann, D.: Data-Driven Methods in Industrial Spoken Dialog Systems. In Data-Driven Methods for Adaptive Spoken Dialogue Systems (pp. 151–171). Springer New York, 2012.
Psutka, J., Müller, L., Matoušek, J., Radová, V.: Mluvíme s počítačem česky. Academia, 2006.
Rabiner, L., & Juang, B. H.: Fundamentals of speech recognition. Prentice-Hall, 1993.
Yu, D., Deng, L.: Automatic Speech Recognition: A Deep Learning Approach. Signals and Communication Technology, Springer London, 2014.

4I4 Diskrétní modely a algoritmy

Rada doktorského studijního oboru 4I4

Aktuální složení rady je na adrese http://mff.cuni.cz/phd/rdso/4i4 .

Spolupracující ústavy

Matematický ústav AV ČR, v.v.i.
Žitná 25, 115 67 Praha 1
http://www.cz.math.cas.cz

Vypsaná témata

Jsou k nahlédnutí v SIS na adrese http://mff.cuni.cz/phd/temata/4i4 .

Poskytovaná výuka

kód Předmět ZS LS
NTIN022 Pravděpodobnostní techniky   2/2 Z+Zk
NDMI035 Geometrické reprezentace grafů II   2/0 Zk
NDMI009 Kombinatorická a výpočetní geometrie I   2/2 Z+Zk
NDMI013 Kombinatorická a výpočetní geometrie II   2/2 Z+Zk
NDMI041 Kombinatorický seminář pro pokročilé   0/3 Z 0/3 Z
NDMI028 Aplikace lineární algebry v kombinatorice   2/2 Z+Zk
NDMI036 Kombinatorické struktury   2/0 Zk
NDMI015 Kombinatorické počítání   2/0 Zk
NDMI042 Grafy a homomorfismy   2/0 Zk
NDMI070 Vybrané kapitoly z teorie grafů   2/0 Zk 2/0 Zk
NDMI045 Analytická a kombinatorická teorie čísel   2/0 Zk
NDMI066 Algebraická teorie čísel   2/0 Zk
NDMI058 Toky a cykly v grafech   2/0 Zk
NDMI055 Vybrané kapitoly z kombinatoriky I   2/0 Zk
NDMI056 Vybrané kapitoly z kombinatoriky II   2/0 Zk

Seznam požadavků ke státní doktorské zkoušce

Uchazeč si zvolí 4 z povinných témat, a to 2 témata z okruhů 1., 2., 3. a 2 témata z okruhů 4.–10. Po dohodě se školitelem bude stanoveno volitelné téma, které může být také jedno z témat 4.–10.

1. Diskrétní matematika
Základy teorie grafů, reprezentace grafů, grafové algoritmy. Lineární algebra. Základy obecné topologie. Vybrané algebraické struktury, univerzální algebra. Kombinatorická teorie pravděpodobnosti.

2. Logika
Úvod do teorie modelů, algebraické specifikace programů. Výrokový a predikátový počet, syntax a sémantika, jejich vztah. Formální systémy, bezespornost a úplnost, Gödelovy věty.

3. Vyčíslitelnost a složitost
Turingovy stroje a ekvivalentní modely. Algoritmy a jejich složitost. NP–úplnost a NP–úplné problémy. Algoritmicky nerozhodnutelné problémy. Věty o rekurzi.

4. Kombinatorická optimalizace
Polyedrální kombinatorika. Lineární programování, dualita. Celočíselné programování. Kombinatorické algoritmy.

5. Kombinatorika
Pokročilá kombinatorika, problémy výběru. Ramseyova teorie a teorie rozkladů. Extremální teorie. Pokročilá teorie grafů.

6. Algebraická kombinatorika
Enumerace. Metody lineární algebry, vlastní čísla, aplikace. Teorie matroidů.

7. Teorie struktur
Kategorické a strukturální otázky kombinatorických objektů.

8. Pravděpodobnostní metoda
Nekonstruktivní metody v kombinatorice, pravděpodobnostní algoritmy. Náhodné grafy.

9. Topologické metody
Obecná a algebraická topologie. Topologické metody v informatice.

10. Diskrétní geometrie
Kombinatorika geometrických konfigurací v euklidovských prostorech. Výpočetní geometrie. Geometrické reprezentace grafů.

Doporučená literatura

1. Diskrétní matematika
Bollobás, B.: Graph theory, An introductory course. Graduate Text in Mathematics 63, Springer–Verlag, New York, 1979.
Bollobás, B.: Modern graph theory. Graduate Text in Mathematics 184, Springer–Verlag, New York, 1998.
Hell, P., Nešetřil, J.: Graphs and homomorphisms. Oxford University Press, Oxford, 2004.
Matoušek, J., Nešetřil, J.: Invitation to discrete mathematics. Oxford University Press, Oxford, 2008.
Diestel, R.: Graph Theory. Springer-Verlag 2010.
2. Logika
Handbook of Logic in Computer Science. Clarendon Press, Oxford, 1992.
Shoenfield, J. R.: Mathematical logic. Addison–Wesley, Reading, 1967.
3. Vyčíslitelnost a složitost
Garey, M. R., Johnson, D. S.: Computers and Intractability, A guide to the theory of NP–completness. W. H. Freeman, San Francisco, 1979.
Papadimitriou, C. H.: Computational Complexity. Addison–Wesley, Reading, 1994.
Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston, 1997.
Shmoys, D. B. , Williamson, D. P.: The Design of Approximation Algorithms. Cambridge University Press 2011.
4. Kombinatorická optimalizace
Cook, W. J., Cunnigham, W. H., Pulleyblank, W. R., Schrijver, A.: Combinatorial optimization. Wiley, New York, 1998.
Schrijver, A.: Theory of linear and integer programming. Wiley, New York, 1998.
Schrijver, A.: Combinatorial Optimization, Polyhedra and Efficiency. Springer- Verlag 2003.
5. Kombinatorika
Bollobás, B.: Modern graph theory. Graduate Text in Mathematics 184, Springer–Verlag, New York, 1997.
Graham, R. L., Spencer, J., Rothschild, B.: Ramsey Theory. Wiley, New York, 1990.
Hall, M.: Combinatorial Theory. Wiley, New York, 1986.
Lint van, J. H., Wilson, R. H.: A course in combinatorics. Cambridge University Press, Cambridge, 1992.
Nešetřil, J., Ossona de Mendez, P.: Sparsity, Graphs, Structures, and Algorithms. Springer-Verlag 2012.
6. Algebraická kombinatorika
Biggs, N. L.: Algebraic graph theory. Cambridge University Press, Cambridge 1994.
Cvetkovic, D. M., Doob, M., Sachs, H.: Spectra of graphs, Theory and applications. J. A. Barth Verlag, Leipzig, 1995.
Oxley, J.: Matroid theory. Oxford University Press, Oxford, 1992.
7. Teorie struktur
Adámek, J., Herrlich, H., Strecker, G. E.: Abstract and Concrete Categories. Wiley, New York, 1990.
MacLane, S.: Categories for the working mathematician. Graduate Texts in Mathematics 5, Springer–Verlag, New York, 1971.
8. Pravděpodobnostní metoda
Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York, 2000.
Grimmet, G. R., Stirzaker, D. R.: Probability and random processes: Problems and solutions. Claredon Press, Oxford, 1992.
Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press, Cambridge, 1995.
9. Topologické metody
Handbook of Logic in Computer Science. Claredon Press, Oxford, 1992.
Johnstone, P. T.: Stone spaces. Cambridge University Press, Cambridge, 1982.
Kelly, J.: General Topology. Van Nostrand, New York, 1955.
Pultr, A.: Podprostory eukleidovských prostorů. SNTL, Praha, 1984.
Matoušek, J.: Using the Borsuk-Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry, Springer 2003.
de Longueville, M.: A Course in Topological Combinatorics. Springer 2013.
Hatcher, A.: Algebraic Topology. Cambridge University Press 2001.
Munkres, J.R.: Elements of Algebraic Topology. Westview Press 1996.
10. Diskrétní geometrie
Berg de, M., Kreveld van, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and applications. Springer–Verlag, Berlin, 2000.
Pach, J., Agarwal, P.: Combinatorial Geometry. Cambridge University Press, Cambridge, 1995.
Matoušek, J.: Lectures on Discrete Geometry. Springer 2002.

4I5 Počítačová grafika a analýza obrazu

Rada doktorského studijního oboru 4I5

Aktuální složení rady je na adrese http://mff.cuni.cz/phd/rdso/4i5 .

Spolupracující ústavy

Ústav teorie informace a automatizace AV ČR, v.v.i.
Pod Vodárenskou věží 4, 182 08 Praha 8
http://www.utia.cas.cz/

Vypsaná témata

Jsou k nahlédnutí v SIS na adrese http://mff.cuni.cz/phd/temata/4i5 .

Poskytovaná výuka

kód Předmět ZS LS
NMNM331 Analýza maticových výpočtů 1   2/2 Z+Zk
NMNM332 Analýza maticových výpočtů 2   2/2 Z+Zk
NPGR016 Aplikovaná výpočetní geometrie   2/1 Z+Zk
NNUM103 Fourierova analýza a wavelety   2/0 Zk
NPGR020 Geometrie pro počítačovou grafiku   2/0 Zk
NPGR030 Optika pro počítačovou grafiku   2/0 Zk
NPGR010 Počítačová grafika III   2/2 Z+Zk
NPGR024 Seminář z vědecké práce   0/2 Z
NPGR028 High Performance Ray Tracing   2/0 Zk
NPGR013 Speciální funkce a transformace ve zpracování obrazu   2/0 Zk
NPGR005 Speciální seminář z počítačové grafiky   0/2 Z 0/2 Z
NPGR022 Speciální seminář ze zpracování obrazu   0/2 Z
NPGR027 Shading Languages   2/1 Z+Zk
NPGR026 Predictive Image Synthesis Technologies   2/2 Z+Zk
NNUM102 Teorie spline funkcí a waveletů pro doktorandy   2/0 Zk
NPGR025 Introduction to Colour Science   2/0 Zk
NPGR029 Variační metody ve zpracování obrazu   2/0 Zk
NPGR023 Visualizace   2/1 Z+Zk

Seznam požadavků ke státní doktorské zkoušce

Tématické okruhy 1 – 4 jsou povinně volitelné v tom smyslu, že student je povinen složit zkoušku z alespoň jednoho z okruhů 1 a 2 a zároveň alespoň jednoho z okruhů 3 a 4. K nim si uchazeč zvolí jedno téma profilující z (dosud nezvolených) okruhů 1 – 7 anebo jiné podle dohody se školitelem. Student by měl složit státní doktorskou zkoušku do konce druhého ročníku studia.

Povinně volitelné okruhy (alespoň jeden okruh z 1 a 2; alespoň jeden okruh z 3 a 4)

1. Teoretické základy informatiky
Diskrétní matematika: Základy teorie grafů, reprezentace grafů v paměti, algoritmy nad grafy.

Logika, algoritmy: Vybrané algebraické struktury. Predikátový počet. Formální systémy, bezespornost a úplnost, Goedelovy věty. Teorie vyčíslitelnosti, Turingovy stroje a ekvivalentní modely výpočtu. Algoritmy a jejich složitost, NP-úplné problémy. Algoritmicky nerozhodnutelné problémy. Věty o rekursi.

2. Matematické metody pro grafiku a zpracování obrazu
Maticové výpočty: Schurova věta, význam ortogonality a normality, rozklady matic, metody pro řešení soustav lineárních rovnic, singulární rozklad, úlohy nejmenších čtverců, částečný problém vlastních čísel, nelinearita a numerická nestabilita v maticových výpočtech.

Spliny: teorie polynomiálních splinů, interpolační a zhlazující spliny, racionální spliny.

Wavelety: teorie multirozkladu, aplikace, algoritmy, biortogonální wavelety, vícerozměrné wavelety, balíčky waveletů,  ,,lifting scheme", spojitá waveletová transformace; Mallatova konstrukce multirozkladu; wavelety s kompaktním nosičem; příklady waveletů

Fourierova transformace v L1®; Wienerova teorie Fourierovy transformace v L2®; Paleyova-Wienerova věta a Heisenbergova nerovnost.

Základy variačního počtu (Euler-Lagrangeovy rovnice, brachistochrona, Lagrangeova funce, funkce s omezenou variací)

Základy numerických metody řešení (parciální diferenciální rovnice, metoda konečných prvků, metoda konečných diferencí, metoda největšího spádu, konjugovaných gradientů, kvadratické programování)

3. Základy počítačové grafiky
Základy 2D grafiky: vidění a barvy, kolorimetrie a barevné prostory, měření a reprodukce barev, rastrová grafika, operace s rastrovým obrazem, rastrové kreslení, anti-aliasing, datové struktury pro 2D vyhledávání, komprese obrazu a videa, HDR fotografie, mapování odstínů.

Základy 3D grafiky: transformace, reprezentace 3D scén, úroveň detailu, parametrické křivky a plochy, viditelnost, stínování, textury, hardwarově akcelerovaná grafika, stínovací programy, základy CUDA/OpenCL.

Základy realistické syntézy obrazu: Rekurzivní sledování paprsku a metody jeho urychlení, datové struktury, distribuované (rozprostřené) sledování paprsku, základy radiační metody, zobrazovací rovnice a její řešení pomocí Monte Carlo metod.

Základy vizualizace dat: objemová data, počítačová tomografie a magnetická rezonance, výpočet izoploch, přímé zobrazování objemu, model šíření světla v 3D médiu, vizualizace vektorových polí a tenzorů vyšších řádů

4. Základy analýzy obrazu
Digitalizace obrazu, vzorkování a kvantování spojitých funkcí, Shannonův teorém. Základní operace s obrazy, histogram, změny kontrastu, odstranění šumu, zaostření obrazu. Lineární filtrace v prostorové a frekvenční oblasti, konvoluce, Fourierova transformace. Detekce hran a rohů. Degradace obrazu a její modelování, odstranění základních typů degradací (rozmazání pohybem a defokusací), inverzní a Wienerův filtr, odhady PSF, slepá a vícekanálová dekonvoluce, variační přístup. Segmentace obrazu, klasické i variační přístupy (prahování, region growing, Mumford-Shah funkcionál, active contours, level sets). Registrace (matching) obrazů. Invarianty pro popis a rozpoznávání 2-D objektů (obecné principy, vizuální příznaky, momenty, Fourierovy deskriptory, diferenciální příznaky, momentové invarianty). Teorie příznakového rozpoznávání, klasifikátory s učením a bez učení, NN-klasifikátor, lineární klasifikátor, SVM klasifikátory, Bayesův klasifikátor. Příklady použití v analýze obrazu. Shluková analýza v prostoru příznaků, iterační a hierarchické metody. Redukce dimenzionality příznakového prostoru, PCT, suboptimální metody pro výběr příznaků. 2D waveletová transformace (WT) – matematické základy. Použití WT pro detekci hran a význačných bodů v obrazu, potlačení šumu, registraci obrazu a fúze obrazu. Komprese obrazu pomocí WT.

Volitelné okruhy

5. Počítačová geometrie
Aplikovaná výpočetní geometrie: definice, vlastnosti a algoritmy pro geometrické vyhledávání, konvexní obálky, Voronoi diagramy, jejich aplikace a zobecnění, triangulace v 2D a 3D a jejich aplikace, střední osa, rekonstrukce povrchu, průsečíky a průniky geometrických objektů.

Geometrie pro počítačovou grafiku: Grupa projektivních, afinních a eukleidovských transformací. Reprezentace těchto grup pomocí matic. Projektivní prostor, homogenní souřadnice. Sférická geometrie. Využití kvaternionů a duálních kvaternionů při popisu eukleidovského pohybu.

Křivky a plochy v počítačové grafice: Prostor spline funkcí, Hermitovy spliny, kubické spliny, Bézierovy křivky a plochy, B-spline křivky a plochy, racionální křivky a plochy, NURBS, speciální plochy, geometrická spojitost.

6. Syntéza realistického obrazu
Radiometrické a fotometrické veličiny, zobrazovací rovnice, důležitost, dualita transportu světla a důležitosti, operátorové vyjádření transportu světla a důležitosti. Monte Carlo kvadratura, nestranné Monte Carlo metody pro řešení zobrazovací rovnice (sledování cest, sledování světla). Kombinované estimátory a aplikace: přímé osvětlení, obousměrné sledování cest. Metropolis-Hastings metoda vzorkování, Metropolis light transport. Přibližné metody řešení zobrazovací rovnice: (progresivní) mapování fotonů, (ir)radiance caching, okamžitá radiozita, lightcuts. Radianční metoda, adaptivní zjemňování, hierarchická radiozita, stochastická radiozita. Zobrazování participujících médií: rovnice transportu světla, algoritmy pro zobrazování médií, speciální techniky pro mraky a atmosféru, průsvitné materiály, BSSRDF. Předpočítaný přenos radiance: matice přenosu světla, kompresní techniky (výběr vhodné báze, SVD, PCA, local PCA). Reyes architektura, standard RenderMan, princip stínovacích jazyků v RenderMan a OpenGL. Prediktivní syntéza obrazu: regulace chyby v rendering pipeline, psycho-fyzikálně věrné mapování odstínů, simulace pokročilých optických jevů (polarizace, difrakce), fluorescenční materiály, fyzikální věrnost konstruktů stínovacích jazyků.

7. Invarianty pro rozpoznávání
Geometrické momenty, definice a základní vlastnosti, normalizace. Komplexní momenty. Momentové invarianty vzhledem k otáčení a měřítku obrazu, úplnost, nezávislost, konstrukce báze. Momentové invarianty vzhledem k afinní transformaci obrazu, metoda grafů. Momentové invarianty vzhledem ke konvoluci, N-fold symetrická jádra, nulprostor a diskriminabilita. Kombinované invarianty. Momentový matching. Ortogonální momenty (Legendrovy momenty, Fourier-Mellin momenty, Zernikovy momenty). Diskrétní momenty a algoritmy pro jejich výpočet.

Doporučená literatura

1. Teoretické základy informatiky
K. Mehlhorn:  Data Structures and Algorithms 2: Graph Algorithms and NP–completeness. EATCS – monograph, Springer–Verlag 1984.
R. E. Tarjan:  Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia 1983.
J. E. Hopcroft, J. D. Ullman:  Introduction to Automata Theory, Languages, and Computation. Addison–Wesley Publ. Company 1979.
M. R. Garey, D. S. Johnson:  Computers and Intractability: A Guide to the Theory of NP–completeness. Freeman, San Francisco 1978.
O. Demuth, R. Kryl, A. Kučera:  Teorie algoritmů I, II. SPN Praha 1989.
R. I. Soare: Recursively enumerable sets and degrees. Springer–Verlag, Berlin, Heidelberg, New York 1987
2. Matematické metody pro grafiku a zpracování obrazu
Duintjer Tebbens, J., Hnětynková, I., Plešinger, M., Strakoš, Z., Tichý, P.: Analýza metod pro maticové výpočty I. Skripta MFF UK, 2011.
Watkins, D.S.: Fundamentals of Matrix Computations. J. Wiley & Sons, New York, Third edition 2010.
Golub, G.H., Van Loan, C.F.: Matrix Computations (Third edition). J. Hopkins Univ. Press, Baltimore, 1996
Najzar K.: Základy teorie waveletů. Skripta, Nakl. Karolinum 2004.
Najzar K.: Základy teorie splinů. Skripta, 2006.
Micula Ch. and Micula S.: Handbook of splines. 1999.
Resnikoff H. L., Wells R. O., Jr..: Wavelets analysis. Springer 1998.
Andreas Antoniou and Wu-Sheng Lu: Practical Optimization: Algorithms and Engineering Applications. Springer, 2007.
3. Základy počítačové grafiky
Shirley P., Ashikhmin M., Marschner S.: Fundamentals of Computer Graphics. A K Peters, 3rd Revised edition, 2009.
Shirley P., Morley R. K.: Realistic Ray Tracing. A K Peters, 2nd Revised edition, 2003.
4. Základy analýzy obrazu
Pratt W. K.: Digital Image Processing (3rd ed.). John Wiley, New York, 2001
Gonzales R. C., Woods R. E.: Digital Image Processing (2nd ed.). Prentice Hall, 2002
Zitová B., Flusser J.: Image registration methods: a survey. Image and Vision Computing, 21 (2003), 11, pp. 977–1000
Duda R.O. et al.: Pattern Classification, (2nd ed.). John Wiley, New York, 2001
Flusser J., Suk T. and Zitová B.: Moments and Moment Invariants in Pattern Recognition. Wiley & Sons Ltd., 2009.
5. Počítačová geometrie
O' Rourke, Joseph: Computational Geometry in C. Cambridge University Press, 1.vydání, 1994 nebo 2.vydání, 2000.
de Berg, Mark, van Kreveld, Marc, Overmars, Mark, Schwarzkopf, Otfried: Computational Geometry, Algorithms and Applications. Springer Verlag, 1.vydání, 1997 nebo 2.vydání, 2001.
M. Lávička: KMA/G2 Geometrie 2. Pomocný učební text, ZČU Plzeň, 2006
Jirí Žára a kol: Moderní počítačová grafika. Computer Press, 1998
František Ježek: Geometrické a počítačové modelování. Plzeň 2009
6. Syntéza realistického obrazu
Dutre P., Bala K., Bekaert P.: Advanced Global Illumination. A k Peters, 2nd edition, 2006.
Glassner A.: Principles of Digital Image Synthesis. Addison- Wesley, 1995.
Jensen H.W.: Realistic Image Synthesis Using Photon Mapping. A K Peters, 2001.
Pharr M., Humphreys G.: Physically Based Rendering: From Theory To Implementation. Morgan Kaufmann; 2nd edition, 2010.
Veach E.: Robust Monte Carlo Methods for Light Transport Simulation. Ph.D. dissertation, Stanford University, 1997.
7. Invarianty pro rozpoznávání
J. Flusser, T. Suk and B. Zitová: Moments and Moment Invariants in Pattern Recognition. Wiley & Sons Ltd., 2009.

© 2013–2017 Univerzita Karlova, Matematicko-fyzikální fakulta. Design noBrother.
Za obsah odpovídá Studijní oddělení.