Recent Courses Taught  
Clelia  DE FELICE Home  
 
Fondamenti di Programmazione

Iteration, Induction and Recursion. Proving Properties of Programs: Loop Invariants. Recursive Functions. Selection Sort. Merge Sort.

The Running Time of Programs. Big-Oh and Approximate Running Time. Solving Recurrence Relations.

The Tree Data Model. Data Structures for Trees. Recursions on Trees. Binary Trees. Binary Search Trees.

The List Data Model. The Linked-List Data Structure. Stacks. Queues.

Automata and regular expressions: basic notions.

References :
1. A. V. Aho, J. D. Ullman, Fondamenti di Informatica (Foundations of Computer Science), Zanichelli, 1994.
2. J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Pub. Co., 2001 (Italian translation: J. Hopcroft, R. Motwani, J. Ullman, Automi, Linguaggi e Calcolabilita`, Addison Wesley Pearson Education Italia s.r.l, 2003).


Programma Fondamenti di Programmazione 2001/02 (Versione pdf)

Programma Fondamenti di Programmazione 2004/05 (Versione pdf)

Teoria della Computazione

Deterministic Finite Automata. Nondeterministic Finite Automata. The Subset Construction. Finite Automata with epsilon-transitions. Regular Expressions and Finite Automata. The Pumping Lemma for Regular Languages. Closure Properties of Regular Languages.

Context-Free Grammars. Parse Trees. Ambiguous grammars. Pushdown Automata: acceptance by final state, acceptance by empty stack. Deterministic Pushdown Automata. The Pumping Lemma for Context-Free Languages. Closure Properties of Context-Free Languages.

Deterministic Turing Machines. Turing Computable Functions. The Halting Problem. Church's Thesis. Primitive Recursive Functions and Partial Recursive Functions. Basic Results. Recursive Sets. Recursively Enumerable Sets. Reducibility. Rice's theorem.

References :
1. G. Ausiello, F. D'Amore, G. Gambosi, Linguaggi Modelli Complessita`, F. Angeli Ed., 2003.
2. P. Degano, Fondamenti di Informatica: calcolabilita` e complessita`, dispense, Universita` di Pisa, 2004.
3. J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Pub. Co., 2001 (Italian translation: J. Hopcroft, R. Motwani, J. Ullman ,Automi, Linguaggi e Calcolabilita`, Addison Wesley Pearson Education Italia s.r.l, 2003).
4. R. I. Soare, Recursively enumerable sets and degrees, Springer Verlag,1988.

Programma Teoria della Computazione 2004/05 (Versione pdf)

Linguaggi di Programmazione

Deterministic Finite Automata. Nondeterministic Finite Automata. The Subset Construction. Finite Automata with epsilon-transitions. Regular Expressions and Finite Automata. The Pumping Lemma for Regular Languages. Closure Properties of Regular Languages. Equivalence and Minimization of Automata.

Context-Free Grammars. Parse Trees. Ambiguous grammars. Pushdown Automata: acceptance by final state, acceptance by empty stack. Deterministic Pushdown Automata. The Pumping Lemma for Context-Free Languages. Closure Properties of Context-Free Languages.

Introduction to Turing Machine: recursively enumerable languages and recursive languages.

Introduction to Compiling: analysis of the source program, the phases of a compiler. Lexical Analysis. Specification of tokens. Recognition of tokens. Syntax Analysis. Top-down parsing. Predictive Parsers. Bottom-up parsing. LR parsers.

References :
1. J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Pub. Co., 2001.
2. A. V. Aho, R. Sethi, J. D. Ullman, Compilers - Principles, Techniques and Tools, Addison-Wesley Pub. Co., 1986.


Programma Linguaggi di Programmazione 2001/02 (Versione pdf)

Metodi Formali per l'Informatica

Turing Machines. Turing Computable Functions. For/While Programs. The Halting Problem. Church's Thesis. Primitive Recursive Functions and Partial Recursive Functions. Basic Results. Recursive Sets. Recursively Enumerable Sets. Reducibility. Rice's theorem.

Semantic description methods. The example language While. Semantics of expressions in While. Operational Semantics: Natural Semantics and Structural Operational Semantics. The semantic function of the statements in While. Equivalence of two Operational Semantics.

Formal models for Molecular Computing. Adleman's algorithm for HHP. Lipton's algorithm for SAT. Splicing Systems. Basics on Variable Length Codes.

References :
1. J. Berstel, D. Perrin, Theory of Codes, Academic Press, New York, 1985.
2. H.R. Nielson, F. Nielson, Semantics with Applications - A Formal Introduction, J. Wiley and Sons, 1999.
3. N. Jones, Computability and Complexity - From a programming perspective, MIT Press, 1997.
4. Ch. H. Papadimitriou, Computational Complexity, Addison Wesley Pub. Co., 1994.
5. G. Paun, G. Rozenberg, A. Salomaa, DNA computing, New Computing Paradigms, Springer-Verlag, 1998.
6. M. Sipser, Introduction to the theory of computation, PWS Publishing Company, 1997.
7. R. I. Soare, Recursively enumerable sets and degrees, Springer Verlag,1988.

Programma Metodi Formali per l'Informatica 2000/2001 (Versione doc)

 
     


Dipartimento di Informatica ed Applicazioni "Renato M.Capocelli" /Università di Salerno