Salta al contenuto principale della pagina

FOUNDATIONS OF COMPUTER SCIENCE

CODE 80303
ACADEMIC YEAR 2022/2023
CREDITS
  • 6 cfu during the 3nd year of 8759 INFORMATICA (L-31) - GENOVA
  • SCIENTIFIC DISCIPLINARY SECTOR INF/01
    LANGUAGE Italian
    TEACHING LOCATION
  • GENOVA
  • SEMESTER 1° Semester
    TEACHING MATERIALS AULAWEB

    OVERVIEW

    We introduce notions and results from Automata Theory and Computability Theory which are of paramount importance for a computer scientist.

     

    AIMS AND CONTENT

    LEARNING OUTCOMES

    To understand key concepts of Theory of Automata and Theory of Computability, such as expressive power of automata, and decidability and semi-decidability of problems. 

     

    TEACHING METHODS

    Traditional.

    SYLLABUS/CONTENT

    Automata and Languages
    Alphabets, strings, languages
    Deterministic (DFA) and non deterministic (NFA) finite state automata
    DFA minimization, regular expressions
    Closure properties of regular languages, pumping lemma
    Context-free grammars, deterministic and non deterministic push down automata (PDA)
    Closure properties of context-free languages, pumping lemma

    Computability
    Turing machines, accepted languages
    Indecidability, recursive and recursively enumerable languages, universal language and machine, indecidability of the universal language
    Halting problem
    Indecidable problems on Turing machines, Rice theorem, Church thesis

    RECOMMENDED READING/BIBLIOGRAPHY

    Course notes.

    TEACHERS AND EXAM BOARD

    Exam Board

    ELENA ZUCCA (President)

    DAVIDE ANCONA

    RICCARDO BIANCHINI (Substitute)

    FRANCESCO DAGNINO (Substitute)

    GIORGIO DELZANNO (Substitute)

    LESSONS

    Class schedule

    All class schedules are posted on the EasyAcademy portal.

    EXAMS

    Exam schedule

    Date Time Location Type Notes
    13/01/2023 09:00 GENOVA Scritto
    03/02/2023 09:00 GENOVA Scritto
    14/06/2023 09:00 GENOVA Scritto
    27/07/2023 09:00 GENOVA Scritto
    12/09/2023 09:00 GENOVA Scritto