I059 Kolmogorovova složitost

Faculty of Informatics
Spring 1997
Extent and Intensity
2/0. 2 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Jozef Gruska, DrSc. (lecturer)
Guaranteed by
Contact Person: prof. RNDr. Jozef Gruska, DrSc.
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Syllabus
  • Kolmogorov and Chaitin complexity of an object tell the maximal degree of compression of a given object. On the base of these simple and fundamental concepts, several basic approaches to crucial problems of sciene has been worked out, that have a variety of applications in informatics and also outside of it. For example, to randomness, (algorithmic) probability, information, inductive reasoning, theory formation, physics,...
  • Basic concepts and results.
  • Randomness of finite and infinite strings.
  • Algorithmic theory of information.
  • Algorithmic probability
  • Inductive reasoning.
  • Resource-bounded Kolmogorov complexity
  • The incompressibility method
  • Limitations of formal systems
  • Number of wisdom
  • Aplications of Kolmogorov complexity outside of informatics
Language of instruction
Czech
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/spring1997/I059