J003 Fundamental Concepts of Computer Science and Some Surprising Discoveries

Fakulta informatiky
jaro 2015
Rozsah
2/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
prof. RNDr. Juraj Hromkovič, CSc. (přednášející), doc. Mgr. Jan Obdržálek, PhD. (zástupce)
RNDr. Jakub Gajarský, Ph.D. (cvičící)
doc. Mgr. Jan Obdržálek, PhD. (cvičící)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: doc. Mgr. Jan Obdržálek, PhD.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
Čt 26. 3. 10:00–11:50 B410, 14:00–15:50 A318, Pá 27. 3. 10:00–11:50 A318, 13:00–14:50 A318, Pá 17. 4. 10:00–11:50 A318, 13:00–14:50 A318, Čt 21. 5. 10:00–11:50 A318, 14:00–15:50 A318, Pá 22. 5. 10:00–11:50 A318, 13:00–14:50 A318
  • Rozvrh seminárních/paralelních skupin:
J003/01: Čt 9. 4. 10:00–11:50 B410, Čt 16. 4. 10:00–11:50 B410, Čt 23. 4. 10:00–11:50 B410, Čt 30. 4. 10:00–11:50 B410, Čt 7. 5. 10:00–11:50 B410, Čt 14. 5. 10:00–11:50 B410, J. Gajarský, J. Obdržálek
Předpoklady
Basic knowledge of the following concepts: basic formal language concepts (alphabets, words, languages), decidable problems, optimisation problems, elementary logic, discrete mathematics (combinatorics, graph theory), elementary probability.
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Osnova
  • 1. The importance of conceptualization in science and the role of mathematics and computer science in the context of development of science.
  • 2. What is information? From Shannon to Kolmogorov and what have we actually achieved (and what not).
  • 3. What is algorithm and how to define the automatic computability bounds. From Turing to quantum computers.
  • 4. What is infinity, and theory of computability as reducibility (or irreducibility) of infinite diversity in problem specification to a finite quantity.
  • 5. How to measure computational complexity of problems.
  • 6. How to define the boundary of efficient computability - and is this bound really robustly definable?
  • 7. Problem sensibility, how to conjure in algorithmics and how to rise above physically unattainable amount of work.
Literatura
    doporučená literatura
  • HROMKOVIČ, Juraj. Theoretical computer science : introduction to automata, computability, complexity, algorithmics, randomization, communication and cryptography. Berlin: Springer, 2004, x, 313. ISBN 3540140158. info
  • HROMKOVIČ, Juraj. Algorithmic adventures : from knowledge to magic. Dordrecht: Springer, 2009, xiii, 363. ISBN 9783540859857. info
  • HROMKOVIČ, Juraj. Design and analysis of randomized algorithms : introduction to design paradigms. Berlin: Springer, 2005, xii, 274. ISBN 3540239499. info
  • HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. 2nd ed. Berlin: Springer, 2003, xii, 544. ISBN 3540441344. info
Výukové metody
In additions to lectures students will be given problems/exercises set to work on. The solutions will be checked for correctness and explained/discussed at the accompanying tutorials.
Metody hodnocení
Final written exam (however completion by colloqium/fulfilling requirements also possible). Handing in solution to problem sets during the semester.
Vyučovací jazyk
Angličtina
Další komentáře
Studijní materiály
Předmět je vyučován jednorázově.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2015/J003