..:: Martin Kot ::..
Introduction to theoretical computer science
General Actual Download Projects
 
General facts
Guarantee:  Ing. Zdeněk Sawa, Ph.D.
Number of credits:  6
Hours:  2/2/0/2
Completition:  Exam
Official web-page:  http://www.cs.vsb.cz/sawa/uti/
Lecturers:  , ,
Exercisers:  , , ,
, , ,
,
 
Division of points
Accreditation: 
  • 2x10pts - term written exams
  • 10pts - written essay describing solution of some exercise(s) from a list given during the course
  • 5pts - performance of solution at exercises
  • Bonus 15pts - written essay describing solution of one of given more difficult examples. For each assignemnt only one student can get points.
  • Condition for accreditation is to obtain at least 20 points
Exam: 
  • 65pts - written exam
  • 0pts - optional oral exam - consultation of written exam
 
Annotation
The students obtain some basic knowledge of theoretical CS. The following introductory topics are taught in the subject: basics of logic, theory of automata, formal languages, algorithmic complexity (P and NPc problems), including their practical applications.
 
Time table
7:15
8:00
8:00
8:45
9:00
9:45
9:45
10:30
10:45
11:30
11:30
12:15
12:30
13:15
13:15
14:00
14:15
15:00
15:00
15:45
16:00
16:45
16:45
17:30
17:45
18:30
18:30
19:15
pondělí                    
LB291
K309
Raška Š.
LB289
K309
Raška Š.
úterý    
LB286
K309
Bača R.
LB288
K309
Bača R.
   
LB284
K309
Polikarpov B.
LB295, LB271
K309
Polikarpov B.
   
středa                
LB294, LB270
D210
Číhalová M.
LB287
D209
Dráždilová P.
   
         
Všichni
PorNA1
Sawa Z., Kot M.
 
LB282, LB252
D209
Dráždilová P.
LB285
D210
Číhalová M.
   
čtvrtek    
LB272
K309
Moravec P.
   
LB292
J360
Kuchař Š.
LB293, LB260
J360
Kuchař Š.
       
   
LB283
K308
Dráždilová P.
LB280
K309
Moravec P.
LB290
J358
Kučera T.
LB281, LB251
J358
Kučera T.
       
pátek                            
sobota                            
 
Lectures
Logic
  • Introduction. Basics of set theory, relations and functions.
  • Natural language analysis in predikate logic language.
  • Proofs.
  • Resolution method.
Languages and automata
  • Formal languages. Finite-state automata.
  • Construction of finite-state automata. Nondeterministic finite automata.
  • Algorithm for conversion of nondeterministic automaton to deterministic finite automaton. Regular expressions.
  • Contex-free grammars and languages.
Algorithmic computability and complexity
  • Algorithmical problem. Computational models.
  • Computational complexity, assymptotic notation.
  • Complexity of a problem. Complexity classes. Reductions between problems. Class NPTIME.
  • Algorithmicaly undecidable problems
 
Study literature
Basic
Other
  • M. Chytil: Automaty a gramatiky, SNTL Praha, 1984.
  • John E. Hopcroft a Jeffrey D. Ullman: Formálne jazyky a automaty. Alfa Bratislava 1978.
  • J. Gruska: Foundation of Computing, International Thomson Computer Press 1997.
  • D. Kozen: Automata and Computability, Undergraduate Text in Computer Science, Springer Verlag 1997.
  • M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company 1997.
  • Ding-Zhu Du, Ker-I Ko: Problem Solving in Automata, Languages, and Complexity, Wiley, 2001.
Literatura není povinná, pouze doporučená, na přednáškách a cvičeních se dozvíte vše potřebné. (Toto není recitační kroužek, takže se nemusíte učit nazpaměť pasáže z knih. Lépe řečeno, nazpaměť se ani učit nesmíte, látce je třeba porozumět.)
Pokud máte k dispozici jiné úvodní knihy či skripta pro daný předmět, klidně je můžete používat. Jedna věc však platí pro všechny -- některé věci na přednášce se mohou líšit od literatury (například odchylky v definicích pojmů, které nejsou jednoznačně ustálené) a u zkoušky pak platí to, co bylo na přednášce.