Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Languages, Automata and Computation

Informacje ogólne

Kod przedmiotu: 103A-CSCSN-ISA-ELAC Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Languages, Automata and Computation
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Computer Systems and Networks )-Computer Systems and Networks-B.Sc.-EITI
( Courses in English )--eng.-EITI
( Przedmioty techniczne )---EITI
( Technical Courses )--eng.-EITI
Punkty ECTS i inne: 6.00
Język prowadzenia: angielski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

ELAC

Numer wersji:

1

Skrócony opis:

Wykład obejmuje klasyczną tematykę teoretyczną informatyki od skończonych opisów gramatycznych różnych klas języków formalnych, poprzez modele automatów generujących lub rozpoznających do ilościowej oceny złożoności obliczeniowej problemów algorytmicznych dla różnych modeli obliczeń. Prezentacja zagadnień ma pokazać praktyczne znaczenie teorii i przydatność dobrego rozumienia omawianych koncepcji.

Pełny opis: (tylko po angielsku)

The course is structured along now classical topics of finite grammatical description of infinite languages, automata based abstract devices for generating and/or recognizing them, and assessing computational complexity of algorithmic problems in different models of computation. The style of the coverage will underline practical relevance of the theory and understanding of concepts.

Lecture contents

  • Introduction (4h): Short overview of topics to be covered;
    mathematical refresher: notation, alphabets, sequences, tuples,
    functions and relations, graphs, strings, grammars and formal
    languages, criteria for classifying languages.

  • Regular Languages and Finite Automata (6h): Three equivalent
    methods for specifying regular languages: regular grammars, regular
    expressions, finite automata; algorithmic conversions of
    representations; from RE to automata and back to RE; nondeterminism in
    automata, trading succinctness for determinism, deterministic
    recognizers. Closure properties of regular languages, the pumping
    lemma, some decision problems of regular languages.

  • Context?Free Languages and Push-down Automata (8h): Conceptually
    simplest non-regular language definition using context-free grammar.
    Properties of context-free grammars, language preserving transformation
    of CFGs, canonical forms, Chomski Normal Form, Greibach Normal Form;
    grammar as a generating device, derivation trees, ambiguity in CF
    grammars and languages. Push-down automata (PDA) recognizing CF
    languages, nondeterministic and deterministic PDAs. Pumping lemma for
    CF languages, closure properties, some decision problems of CF
    languages; simplest non-context-free language. Practical aspects of
    using CF grammars in defining programming languages; meta-notations and
    styles implied by parser generating tools.

  • Beyond Context-Free (4h): context-sensitive and general grammars
    and languages; linear bounded automata and Turing machines. Kuroda
    Normal Form for context-sensitive grammars. Some intuitive examples of
    non-context-free languages and their recognition. Parallel rewriting
    systems (Lindenmayer Systems), deterministic context-free L-systems,
    geometric interpretation of L-systems, examples of fractals generated
    by L-systems.

  • Complexity of computation (8h). The Church-Turing thesis,
    undecidable, decidable, intractable, and efficiently computable
    problems; examples. Algorithmic decision problems as language
    recognition problems. Time and space complexity; the notion of
    reducibility, polynomial reducibility and complexity classes P and NP.
    The notion of completness; NP-Complete class, the SAT problem and
    Cook`s theorem. Examples of problems in NPC, some notable reductions of
    problems. Practical complexity with real processing platforms and high
    level languages. Approximation heuristics for intractable problems.


Tutorial contents
Tutorials will offer exercises focused on topics covered during lectures to enhance understanding and exhibit practical relevance of theoretical concepts. In particular, exercises and homework problems concerning transformations of automata and context free grammars will be proposed.
Two midterm assessment tests will be scheduled.


Projects contents
The project will consists of two individual (or tandem) assignments
concerning:

  • Regular language processing / recognition

  • Context-free language manipulation / recognition

  • Attempts to approximate solutions of some hard problems


or a mixture thereof.


Prerequisites
Prerequisite TypePrerequisite NumberCodeName
Required1103A-CTxxx-ISA-EIDMAIntroduction to Discrete Mathematics
Recommended2103B-CTxxx-ISA-EADSAlgorithms & Data Structures
Recommended2103A-CSCSN-ISA-EADSAlgorithms & Data Structures


Similar Courses
CodeNameDiscount ECTS
103B-INxxx-MSP-PTIPodstawy teoretyczne informatyki4

Literatura: (tylko po angielsku)

    1. J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to Automata Theory, Language and Computation, 2nd ed., Addison-Wesley, 2001.

    2. M. Sipser, Introduction to the Theory of Computation, 2nd ed.,
      Course Technology, 2004.

    3. P. Linz, An Introduction to Formal Language and Automata (4th
      ed.), Jones and Bartlett, 2006.

Metody i kryteria oceniania: (tylko po angielsku)

Three assessment components will be taken into account:

  • Two midterms, score up to 30 points

  • Projects, score up to 30 points

  • Final exam, score up to 40 points

The final result is based on the following pattern:

5.0: 91-100 points

4.5: 81-90 points

4.0: 71-80 points

3.5: 61-70 points

3.0: 51-60 points

2.0: 0-50 points

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. zimowy" (w trakcie)

Okres: 2019-10-01 - 2020-02-21
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin, 48 miejsc więcej informacji
Projekt, 15 godzin, 48 miejsc więcej informacji
Wykład, 30 godzin, 48 miejsc więcej informacji
Koordynatorzy: Ilona Bluemke
Prowadzący grup: Ilona Bluemke, Jacek Komorowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. zimowy" (zakończony)

Okres: 2018-10-01 - 2019-02-17
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin, 48 miejsc więcej informacji
Projekt, 15 godzin, 48 miejsc więcej informacji
Wykład, 30 godzin, 48 miejsc więcej informacji
Koordynatorzy: Ilona Bluemke
Prowadzący grup: Ilona Bluemke, Jacek Komorowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2017/2018 - sem. zimowy" (zakończony)

Okres: 2017-10-01 - 2018-02-18
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin, 28 miejsc więcej informacji
Projekt, 15 godzin, 28 miejsc więcej informacji
Wykład, 30 godzin, 28 miejsc więcej informacji
Koordynatorzy: Ilona Bluemke
Prowadzący grup: Ilona Bluemke
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2016/2017 - sem. zimowy" (zakończony)

Okres: 2016-10-01 - 2017-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin, 28 miejsc więcej informacji
Projekt, 15 godzin, 28 miejsc więcej informacji
Wykład, 30 godzin, 28 miejsc więcej informacji
Koordynatorzy: Ilona Bluemke
Prowadzący grup: Ilona Bluemke
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2015/2016 - sem. zimowy" (zakończony)

Okres: 2015-10-01 - 2016-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin, 28 miejsc więcej informacji
Projekt, 15 godzin, 28 miejsc więcej informacji
Wykład, 30 godzin, 28 miejsc więcej informacji
Koordynatorzy: Ilona Bluemke
Prowadzący grup: Ilona Bluemke
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2014/2015 - sem. zimowy" (zakończony)

Okres: 2014-09-29 - 2015-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin, 30 miejsc więcej informacji
Projekt, 15 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Ilona Bluemke
Prowadzący grup: Ilona Bluemke
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.