Theoretical Informatics II - Course Overview
Theoretical Informatics II course aims to familiarize students with formal languages, automata, computability, and complexity theories. Recommended literature, coursework details, examination structure, and organization of the course are also provided.
Uploaded on Mar 09, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Theoretical informatics II Aim of the course and its syllabus Recommended literature Coursework Examination Your questions
Theoretical informatics II Lecturer: Josef Hynek Josef.Hynek@uhk.cz Aim of the course: To make the students familiar with selected aspects of theoretical informatics in order to be prepared for their independent research activities in the area of applied informatics. The scope of the course reflects the fact, that some students did not acquire sufficient level of preliminary knowledge in this area during their previous studies and so it is necessary to bring them into line with students who already passed some courses in theoretical informatics.
Syllabus: Theory of formal languages (languages, Chomsky hierarchy, grammars and their utilization). Theory of automata (finite automata, pushdown automata, Turing machines, relationships between various types of automata and grammar, Church-Turing thesis) Theory of computability (decidable problems, universal Turing machine, the halting problem, undecidable problems and their implications, G del theorem, Turing machines with oracle) Theory of complexity (time and space complexity, algorithm analysis, classes of complexity, NP-complexity, approximate solutions to hard problems)
Reading list: Sipser, M.: Introduction to the Theory of Computation Course Technology, 3rd Ed., Centage, Boston, MA, 2014. 1. Cormen, T. H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, (2nd Edition), MIT Press 2001. 2. Goddard, W.: Introducing the Theory of Computation. Barlett, 2008. 3. Jan ar, P., Kot, M., Sawa, Z.: Teoretick informatika. V B Technick univerzita Ostrava, 2007. (in Czech only) 4. Linz, P.: An Introduction to Formal Languages and Automata 6th ed., Jones & Barlett, 2016. 5. Martin, C.: Introduction to Languages and the Theoryof Computation. 4th Ed. McGraw Hill, 2011. 6. Mitchell, M.: Complexity. A Guided Tour. Oxford Press, 2009. 7. Reus, B.: Limits of Computation. From a Programming Perspective. Springer, 2016. 8.
Organization of the course Introductory meeting Reading & independent work of students Consultations if needed Josef.Hynek@uhk.cz in person (prior arrangement is needed) Preparation of your coursework (paper) Examination
Coursework (paper) Topic: focused on specific aspects of theoretical informatics related to the subject of your dissertation (or related to some area of your interest if you are unable to find any relationship to your dissertation) Length: 3000 words approximately Format: common conference/journal paper (Word, PDF) Language: English or Czech
Coursework (paper) Submission: by e-mail (Josef.Hynek@uhk.cz ) Deadline: 17. 1. 2025 (winter term) 6. 6. 2025 (summer term) Thereafter: I will need approximately two weeks to read it and then (if it is ok) you will be invited for oral exam
Examination Examination comprises of two parts: First of all, we will discuss your paper Secondly, your knowledge of theoretical informatics will be assessed in the areas of theory of automata and formal languages theory of computability and theory of complexity The scope is given by the recommended textbook
Theoretical informatics II Your questions?
