Modern Theoretical Computer Science

• 39 hrs lectures
• 13 hrs projects

• 60 pts final exam (written part)
• 40 pts projects

Thorough grasp of concepts and results achieved in modern theoretical computer science.

To give an in-depth overview of modern theoretical computer science. Most importantly, to present the latest research in the area of automata, formal languages, formal models, computability, complexity, and translation.

Formal languages.

• Copy of lectures
• Meduna, A.: Automata and Languages. London, Springer, 2000
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Boston, Addison-Wesley, 2001
• many very recent papers, scientific reports, and books

• Introduction.
• Regulated formal models: principles.
• Matrix grammars.
• Parallel grammars.
• Random-context grammars.
• Left versions of regulated grammars.
• Hierarchy of Language Families Resulting from Regulated Grammars.
• CD Grammar Systems.
• PC Grammar Systems.
• L systems.
• Semi-parallel formal models; multi-grammars.
• Scattered context grammars.
• New versions of classical automata.
• Current trends; summary.

• An essay based on selected scientific studies dealing with the teoretical computer science area related to the student's dissertation

1. Paper during the semester:

• 
  40 points = 30 for essay + 10 for presentation.
• 
  The topic has to be related to the topic of the course, approved by both guarantee (Prof. Meduna) and the supervisor.
• 
  The paper has to be submitted by Monday of the week of presentation. Send it by email to meduna@fit.vutbr.cz, with a subject "TID-paper". Attention! If the paper is sent on Tuesday of the week of presentation, loss of 5 points follows. Any later sening will be discussed individually.
• 
  After the presentation, the paper can be improved and re-submit.

2. Oral exam consists of two questions, 30 points each.