J003 Fundamental Concepts of Computer Science and Some Surprising Discoveries

Faculty of Informatics
Spring 2015
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Juraj Hromkovič, CSc. (lecturer), doc. Mgr. Jan Obdržálek, PhD. (deputy)
RNDr. Jakub Gajarský, Ph.D. (seminar tutor)
doc. Mgr. Jan Obdržálek, PhD. (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: doc. Mgr. Jan Obdržálek, PhD.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Thu 26. 3. 10:00–11:50 B410, 14:00–15:50 A318, Fri 27. 3. 10:00–11:50 A318, 13:00–14:50 A318, Fri 17. 4. 10:00–11:50 A318, 13:00–14:50 A318, Thu 21. 5. 10:00–11:50 A318, 14:00–15:50 A318, Fri 22. 5. 10:00–11:50 A318, 13:00–14:50 A318
  • Timetable of Seminar Groups:
J003/01: Thu 9. 4. 10:00–11:50 B410, Thu 16. 4. 10:00–11:50 B410, Thu 23. 4. 10:00–11:50 B410, Thu 30. 4. 10:00–11:50 B410, Thu 7. 5. 10:00–11:50 B410, Thu 14. 5. 10:00–11:50 B410, J. Gajarský, J. Obdržálek
Prerequisites
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.
Course Enrolment Limitations
The course is offered to students of any study field.
Syllabus
  • 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.
Literature
    recommended literature
  • 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
Teaching methods (in Czech)
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.
Assessment methods (in Czech)
Final written exam (however completion by colloqium/fulfilling requirements also possible). Handing in solution to problem sets during the semester.
Language of instruction
English
Further Comments
Study Materials
The course is taught only once.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/spring2015/J003