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 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
per valutare la solubilità dei problemi e la complessità
degli algoritmi.
On-line lecture notes: see
the download points below.
Esami: martedi` 22.07.03 ore 10 aula 12.
martedi` 09.09.03 ore 10 aula 12. ***
martedi` 23.09.03 ore 10 aula 12. ***
*** Occorre fare la prenotazione nel foglio
predisposto
all'ingresso di Ingegneria dell'Informazione.
IMPORTANTE: Gli studenti che desiderano
sostenere
l'esame negli appelli di settembre 2003 sono
invitati al seminario
didattico-scientifico
sulla Correttezza dei Programmi
che il Prof. Pettorossi terra` in aula 9 n.e.
dalle 11 all 12:30 i giorni 4 e 18 settembre 2003.
Ricevimento studenti: dopo le lezioni o per appuntamento.
Programma
d'esame e domande d'esame.
Programma del corso.
The relevant material may be found in the
references indicated in [red].
1. Algorithms on Trees and Graphs (22
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 (No Matrix-Tree Theorem)].
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].
Dijkstra's Single Source Shortest Path [Download
here].
Reachability in graphs [Download
here].
Binary Search.
Sorting: - Selection Sort and Binary Insertion
- Merge Sort and Quicksort
- Tree Selection and Heapsort
- Topological Sort [P4: Chapter 1: pages
1.1-1.11,
2.0-2.6. Download
here.]
Backtracking and n-queens problem [P4:
Chapter 2.2 and 2.3].
Term unification: Martelli-Montanari algorithm.
[Download
here from: Pettorossi, A. and Proietti, M.: First Order Logic and Logic
Programming. Aracne, 2002].
2. Parsing (23 ore)
Relations, Functions, Natural Numbers,
Semigroups,
Monoids [P1: Sections 1.2, 1.3, 1.6, 4.2].
Chomsky Hierarchy [P2:
pages 0.1, 0.2, 3].
Regular languages, Regular Expressions, Finite
Automata,
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].
Context-free languages and pushdown automata.
Chomsky normal form
[P2: page 5, 5.22].
Avoiding epsilon-productions, unit-productions,
and left-recursion [P2: pages 5.2-5.6].
Parser for regular languages
[P3: Chapter 7: last three pages. Download
here].
Parsers for context free languages:
Cocke-Younger-Kasami,
Chop-Expand.
[P2: Chapter 5: pages 1-10,
5.30-31-32.
Download
here].
3. Programmazione in C++.
Reference: Pettorossi, A.: Programming in C++. Aracne,
2001
or download by clicking on the relevant algorithm.
Preliminary: primes,
pointers,
rationals_complex,
strings,
matrix_product,
arrays_as_pointers.
Recursion: fibonacci,
mutual_recursion,
hanoi_tworecursions,
hanoi_iterative.
Backtracking: dispositions,
permutations,
nqueens.
Classes: pairs,
list_of_int,
list_of_any,
list_module,
list_template,
stacks
of trees,
queue_of_int,
queue_module.
Search: Binary
search, longestcommonsubsequence.
Sorting: bubblesort,
mergesort,
quicksort,
heapsort_on_array.
Trees: minimal_spanning_tree
of undirected graphs,
tree_depth_first_visit1
(iterative), tree_depth_first_visit2
(recursive).
Graphs: graph_depth_first_visit
(or reachability in a graph) (list_module
and graph1_in
files needed).
Theorem
Proving for Propositional Calculus.
Parser
for regular languages.
Parser
for context-free languages.
Prerequisiti: Fondamenti di
Informatica
1, Fondamenti di Informatica 2, Elementi di Algebra e Logica.
Modalità di esame: Prova
scritta e orale.
Testi consigliati.
[P1] Pettorossi, A.: Quaderni di Informatica. Parte I,
UniTor,
1991.
[P2, P3, P4] Pettorossi, A.: Quaderni di Informatica. Parte II.
Theory of Computation III-IV, Aracne, 1995.
Errata-Corrige
==================================================================================
This page should be stored in: pettorossi1:/home/adp/www/ProgramCorsoASD02-03.html