FOUNDATIONS OF COMPUTER SCIENCE
Learning outcomes of the course unit
Provide the basic elements and formal tools for studying problems that can and cannot be dealt with using a computer.
Prerequisites
Mathematical analysis 1, Fundamentals of programming.
Course contents summary
Introductory notes on the algorithm concept, on the representation
of information, and on computer architecture.
Formal languages.
Regular expressions.
Finite state automata.
Generative grammars.
Context-free languages.
Turing machines.
Computable and non-computable functions.
Recommended readings
A. Dovier, R. Giacobazzi. Fondamenti dell'Informatica: Linguaggi Formali e Calcolabilita.
A. M. Pitts. Regular Languages and Finite Automata.
I. Mastroeni. Collection of exercises for the ``Fundamentals of Computer Science: Linguaggi Formali e Calcolabilita''.
U. Solitro. Linguaggi Formali, Computabilità e Complessità: Esercizi risolti, 2006.
A. Pettorossi. Automata Theory and Formal Languages, Aracne Editrice, 2006. ISBN: 88-548-0889-X.
A. Pettorossi. Elements of Computability, Decidability, and Complexity, Aracne Editrice, 2006. ISBN: 88-548-0682-X.
