Warsaw University of Technology - Central Authentication System
You are not logged in | log in
course directory - help

Theoretical Fundamentals of Computer Science

General data

Course ID: 103B-INxxx-MSP-PTI Erasmus code / ISCED: (unknown) / (unknown)
Course title: Theoretical Fundamentals of Computer Science Name in Polish: Podstawy teoretyczne informatyki
Department: The Faculty of Electronics and Information Technology
Course groups: ( Advanced Courses - General )--Ph.D.-EITI
( Advanced Courses )--M.Sc.-EITI
( Technical Courses )---EITI
ECTS credit allocation (and other scores): 4.00
Language: Polish
(in Polish) Jednostka decyzyjna:

(in Polish) 103000 - Wydział Elektroniki i Technik Informacyjnych

(in Polish) Kod wydziałowy:

(in Polish) PTI

(in Polish) Numer wersji:

(in Polish) 2

Short description:

Basic notions of mathematical linguistics. Regular languages and finite automata. Context free languages and push down automata. Context sensitive languages and linear bounded automata. Recursively enumerable languages and Turing machines. Decidable and undecidable problems of mathematical linguistics. Computational complexity. Introduction to theory of translation. Examples of grammars used in another areas of computer science. Elements of first order predicate logics.

Full description: (in Polish)



Treść wykładu
Podstawowe pojęcia lingwistyki matematycznej: słowo, język, operacje na słowach i językach, składnia, semantyka, gramatyka, automat, klasyfikacja Chomsky`ego.

Języki regularne i automaty skończone: gramatyki regularne, analiza i synteza automatów, grafy przejść, determinizm i niedeterminizm, wyrażenia regularne.

Języki bezkontekstowe i automaty ze stosem: gramatyki bezkontekstowe, wyprowadzenia słów i drzewa wywodu, zagadnienia analizy składniowej języków, upraszczanie gramatyk, rodzaje gramatyk i postacie normalne.Języki kontekstowe i automaty liniowo ograniczone.Języki bez ograniczeń i maszyny Turinga.Rozstrzygalne i nierozstrzygalne problemy lingwistyki matematycznej.Podstawy złożoności obliczeniowej: problemy klasy P, NP. i NP-zupełne, przykłady.

Wprowadzenie do teorii translacji: metoda generacyjna i redukcyjna, ekonomiczne metody analizy syntaktycznej, gramatyki LL(k), LR(k), gramatyki z pierwszeństwem i z operatorowym pierwszeństwem.

Przykłady gramatyk wykorzystywanych w innych działach informatyki: rozpoznawaniu obrazów, modelach biologicznych organizmów itd.

Elementy logiki predykatów pierwszego rzędu: model, interpretacja, aksjomaty, reguły wnioskowania, dowodzenie formuł, przykłady zastosowań.


Bibliography: (in Polish)

    1. J.E. Hopcroft, J.D. Ullman: Wprowadzenie do teorii automatów, języków i obliczeń. PWN 1994.


    2. F. Hopgood: Metody kompilacji. PWN 1984.


    3. S. Kowalski, A.W. Mostowski: Teoria automatów i lingwistyka matematyczna. PWN 1979.


    4. H. Kruszyński i inni: Zbiór zadań z teorii układów logicznych. PWN 1976.


    5. P.Misiurewicz, M. Perkowski: Teoria automatów. Materiały pomocnicze do ćwiczeń. Wyd. PW 1976

Classes in period "Winter Semester 2020/2021" (in progress)

Time span: 2020-10-01 - 2021-02-12
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Jacek Komorowski
Group instructors: Jacek Komorowski
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Summer Semester 2019/2020" (past)

Time span: 2020-02-22 - 2020-09-30
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Jacek Komorowski
Group instructors: Jacek Komorowski
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Winter Semester 2019/2020" (past)

Time span: 2019-10-01 - 2020-02-21
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Jacek Komorowski
Group instructors: Paweł Kerntopf, Jacek Komorowski
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Summer Semester 2018/2019" (past)

Time span: 2019-02-18 - 2019-09-30
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Jacek Komorowski
Group instructors: Jacek Komorowski
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Winter Semester 2018/2019" (past)

Time span: 2018-10-01 - 2019-02-17
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Paweł Kerntopf, Jacek Komorowski
Group instructors: Paweł Kerntopf, Jacek Komorowski
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Summer Semester 2017/2018" (past)

Time span: 2018-02-19 - 2018-09-30
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Paweł Kerntopf
Group instructors: Paweł Kerntopf
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Winter Semester 2017/2018" (past)

Time span: 2017-10-01 - 2018-02-18
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Paweł Kerntopf
Group instructors: Paweł Kerntopf
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Summer Semester 2016/2017" (past)

Time span: 2017-02-20 - 2017-09-30
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Paweł Kerntopf
Group instructors: Paweł Kerntopf
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Winter Semester 2016/2017" (past)

Time span: 2016-10-01 - 2017-02-19
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Paweł Kerntopf
Group instructors: Paweł Kerntopf
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Summer Semester 2015/2016" (past)

Time span: 2016-02-23 - 2016-09-30
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 78 places more information
tutorials, 15 hours, 78 places more information
Coordinators: Paweł Kerntopf
Group instructors: Paweł Kerntopf
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Winter Semester 2015/2016" (past)

Time span: 2015-10-01 - 2016-02-22
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Paweł Kerntopf
Group instructors: Paweł Kerntopf
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Summer Semester 2014/2015" (past)

Time span: 2015-02-23 - 2015-09-30
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Paweł Kerntopf
Group instructors: Paweł Kerntopf
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Winter Semester 2014/2015" (past)

Time span: 2014-09-29 - 2015-02-22
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Paweł Kerntopf
Group instructors: Paweł Kerntopf
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Summer Semester 2013/2014" (past)

Time span: 2014-02-24 - 2014-09-28
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Paweł Kerntopf
Group instructors: Paweł Kerntopf
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Winter Semester 2013/2014" (past)

Time span: 2013-10-01 - 2014-02-23
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 60 places more information
tutorials, 15 hours, 60 places more information
Coordinators: Paweł Kerntopf
Group instructors: Paweł Kerntopf
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Summer Semester 2012/2013" (past)

Time span: 2013-02-20 - 2013-09-30
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 84 places more information
tutorials, 15 hours, 84 places more information
Coordinators: Paweł Kerntopf
Group instructors: Paweł Kerntopf
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Classes in period "Winter Semester 2012/2013" (past)

Time span: 2012-10-01 - 2013-02-19
Choosen plan division:


magnify
see course schedule
Type of class: lectures, 30 hours, 90 places more information
tutorials, 15 hours, 90 places more information
Coordinators: Krzysztof Walczak
Group instructors: Krzysztof Walczak
Students list: (inaccessible to you)
Examination: Exam
(in Polish) Jednostka realizująca:

(in Polish) 103200 - Instytut Informatyki

Course descriptions are protected by copyright.
Copyright by Warsaw University of Technology.