Dipartimento di Informatica, Sistemi e Produzione.  Computer Science Department.
Università di Roma Tor Vergata.

Docente: Alberto Pettorossi.

Obiettivo del corso. Il corso si propone di offrire una panoramica sui principali
algoritmi e strutture di dati per l'ordinamento e la ricerca su alberi e grafi.
A partire da questi esempi concreti il corso si propone, inoltre, di:
(i) avviare all'utilizzo di metodologie di soluzione di problemi
basate sulla ricorsione e il backtracking, (ii) mostrare l'uso dell'algebra e
della logica nella programmazione e (iii) presentare criteri di valutazione
della solubilità e della complessità dei problemi.

On-line lecture notes:  click here first.  Exam Exercises: click here.

Programma del corso:
     The topics may be studied in the references indicated in [red].

1. From First Order Logic to Logic Programming (3 ore)
 - First-order predicate calculus: basic notions.
 - Unification (Robinson algorithm).
 - Prolog Programming [PL: Part 0: pages 1-6. Part I: pages 2-5, 9-10].

2. Algorithms on Trees and Graphs (17 ore)
Complexity of algorithms [P1: 7.2, 7.3, 7.4: Theorem 6 only (without proof), 7.5, 7.6].
Trees and Graphs [P1: 4.4.1, 4.4.3, 4.6.1 (Matrix-Tree Theorem optional)].
Minimal Spanning Trees [P4: Chapter 1: 3.0-3.9].
Matrix Multiplication, Transitive closures of graphs, Shortest Paths [P4: Sect. 7, 4.15-4.26].
Reachability in graphs [PE: pages 33-34].
Sorting: - Selection Sort and Binary Insertion; - Merge Sort and Quicksort;
                - Tree Selection and Heapsort; - Topological Sort.
                - Selection in linear time [P4: Chapter 1: pages 1.1-1.11, 2.0-2.10. PE: Chapter 5].
Backtracking and n-queens problem [P4: Chapter 2.2 and 2.3].

3. Parsing  (25 ore)
Relations, Functions, Natural Numbers, Semigroups, Monoids, and
Free Monoids [P1: Sections 1.2, 1.3, 1.6, 4.2].
Turing Computability, Recursive enumerable sets,
and Recursive sets [Chapter 2: pages 1-4, P3: Chapter 4: pages 1-2].
Chomsky Hierarchy and Kuroda Theorem [P2: pages 0.1, 0.2, 3].
Context Free languages and Chomsky normal form [P2: page 5].
Avoiding epsilon-productions, unit-productions, and left-recursion [P2: pages 5.2-5.6].
Regular languages, Regular Expressions, Finite Automata, Kleene's Theorem,
NFA=FA, and Arden rule [P2: pages FA 4.2, 4.3, 7, 8, 9.2, 10.2, 10.2.1, 10.2.2, 10.4].
Left-linear and right-linear finite automata [P2: pages 0.4.1, 0.4.2].
Parsing for regular languages [P3: Chapter 7: last three pages. PE: Sect. 8.1 ].
Parsing for context free languages: - CYK parser, - Burstall-Dijkstra parser
                                           [P2: Chapter 5: pages 1-10, 5.30-31-32. PE: Sect. 8.2 ].

4. Programmazione in C++. Pointers, lists, stacks, trees, and queues.
           Bubblesort, Data1, Data2, Lists1, Lists2, Tree1.
           Iterative_Depth_first_visit, Recursive_Depth_first_visit.

Prerequisiti: Fondamenti di Informatica 1, Fondamenti di Informatica 2, Algebra e Logica.

Modalità di esame: Prova scritta e orale. Programmi da consegnare e domande.

Testi consigliati.
[1] Aho, A.V. and Ullman, J.D.: The Theory of Parsing, Translation and Compiling, Vol. I and II.
      Prentice-Hall, 1972.
[2] T. Cormen et al.: Introduction to Algorithms. MIT Press 1989.
[3] Mendelson, E.: Introduction to Mathematical Logic, Wadsworth & Brooks/Cole
                  Advanced Books & Software, Monterey, California, 1984.
[P1] Pettorossi, A.: Quaderni di Informatica. Parte I, UniTor, 1991.
[P2] Pettorossi, A.: Quaderni di Informatica. Parte II, 2nd Edition, Aracne, 1993.
[P3] Pettorossi, A.: Theory of Computation. Part III, 2nd Edition, Aracne, 1994.
[P4] Pettorossi, A.: Theory of Computation. Part IV, Aracne, 1995.
[PL] Pettorossi, A.: Notes on Predicate Calculus and Logic Programming, Lecture Notes, 1998.
[PE] Pettorossi, A.: Learning Pascal Through Examples. Aracne, 1993.
[C++] http://www.bruceeckel.com/ThinkingInCPP2e.html

Go to the top of the page.

This page should be stored in:  /home/adp/www/ProgramCorsoFondInfo300-01.html