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.
Esami: 10.09.02 ore 9:00 aula 4 nuovi edifici.
               25.09.02 ore 14:00 aula 3 nuovi edifici.
              Occorre fare la prenotazione.

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

1. From First Order Logic to Logic Programming (6 ore)
 - First-order predicate calculus. Unification.
      [PL: pages 3-4, 6-7, 11-20] [PL: pages 25-37 (basic concepts)].

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 [PC++: pages 45-46].
Sorting: - Selection Sort and Binary Insertion; - Merge Sort and Quicksort;
                - Tree Selection and Heapsort; - Topological Sort (optional).
                - Selection in linear time  (optional)
[P4: Chapter 1: pages 1.1-1.11, 2.0-2.10. PC++: Chapter 3].
Backtracking and n-queens problem [P4: Chapter 2.2 and 2.3].

3. Parsing  (22 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
 [P3: Chapter 2: pages 1-4, P3: Chapter 4: pages 1-2].
Chomsky Hierarchy[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 (optional)  [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 regular grammars (optional) [P2: pages 0.4.1, 0.4.2].
Parsing for regular languages (optional) [P3: Chapter 7: last three pages. PC++: Sect. 7.1 ].
Parsing for context free languages: - CYK parser, - Burstall-Dijkstra parser
                                           [P2: Chapter 5: pages 1-10, 5.30-31-32. PC++: Sect. 7.2 ].

4. Programmazione in C++.
Preliminary: primes, pointers, complex, rationals_complex, strings,
           matrix_product, arrays_as_pointers.
Recursion and backtracking: fibonacci, mutual_recursion,
           hanoi_tworecursions, hanoi_onerecursion, hanoi_iterative,
           dispositions, combinations, permutations, anagrams, nqueens, powerset.
Classes: pairs, list_of_int, list of_pairs_of_int,   list_of_any, list_module, list_template,
           stacks of trees, trees, queue_of_int, queue_module.
Longestcommonsubsequence. Binary search.
Sorting: bubblesort, mergesort, quicksort, heapsort_array, heapsort_tree,
        topologicalsort    (list_module and partialorder_in files needed).
Trees: minimal_spanning_tree (undirected),
             tree_depth_first_visit1  (iterative),   tree_depth_first_visit2   (recursive),
        tree_breadth_first_visit(iterative)    (queue_module needed).
Graphs: graph_depth_first_visit (or reachability in a graph)  (list_module and graph1_in  files needed),
        spanning_forest(directed)    (graph2_in  file needed),
        spanning_forest(undirected)    (graph2_in file needed).
Propositional Calculus Theorem Proving.
Formal Differentiation (optional).
Parsing for regular languages (optional).
Parsing for context-free languages: cfparser.

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] T. Cormen et al.: Introduction to Algorithms. MIT Press 1989.
[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.: First Order Predicate Calculus and Logic Programming, Lecture Notes, 2001.
[PC++] Pettorossi, A.: Programming in C++. Aracne, 2001.
[C++] http://www.bruceeckel.com/ThinkingInCPP2e.html
Go to the top of the page.

This page should be stored in:  pettorossi1:/home/adp/www/ProgramCorsoASD01-02.html