Università di Padova

Diploma in Ingegneria Informatica Corso di Fondamenti di Informatica 2 2 Moduli

A.A. 2001/2002

Versione 1.00 19/09/2000

Obiettivi del corso e prerequisiti

Il corso di Fondamenti di Informatica 2, come riassume il titolo stesso, si configura come il naturale approfondimento di quanto affrontato nel corso di Fondamenti del primo anno. Pertanto gli argomenti principali sono, in estrema sintesi, l'introduzione alle strutture di dati, elementari e complesse, la teoria degli algoritmi fondamentali e la misura della loro complessità. A ciò si affiancherà l'approfondimento del linguaggio di programmazione Java e la conseguente pratica d'uso attraverso l'applicazione della teoria sviluppata. Si cercherà inoltre di introdurre una visione più 'professionale' nella risoluzione dei problemi, sfruttando le caratteristiche object-oriented del linguaggio e un approccio di tipo 'progettuale'.

Si è cercato di disegnare un percorso coerente tra i corsi che sviluppano particolarmente la programmazione (FI1, FI2, Sist. Oper., FI3) attorno ad un paradigma comune costituito dal linguaggio Java, in modo che il corso di FI1 sia a carattere introduttivo, quello di FI2 di approfondimento, SO curi gli aspetti relativi alla multiprogrammazione e al software di sistema, FI3 gli argomenti avanzati (programmazione di rete, interfacciamento a database, applicazioni distribuite). Grazie a questa articolazione gli studenti possono sperimentare un linguaggio moderno, evoluto ed object oriented come Java e le sue innumerevoli applicazioni (si pensi solamente alle applicazioni grafiche interattive in World Wide Web), anche se in FI2 l'enfasi maggiore sarà comunque data all'apprendimento della tecnologia di programmazione ad oggetti e alla conoscenza degli algoritmi fondamentali.

L'osservazione delle competenze richieste dal mercato del lavoro ai diplomati informatici indurrebbe a a mantenere una certa attenzione anche per il linguaggio C++, che viene tuttora largamente utilizzato, assieme ai linguaggi 'visuali', per lo sviluppo di applicazioni in ambiente office e industriale. La scelta di limitarsi in questo corso alla sola illustrazione dei principali aspetti che differenziano Java da C++ è dovuta alla pratica impossibilità, per mancanza di tempo, di sviluppare un serio laboratorio per entrambi i linguaggi. Nel corso di SO, soprattutto per lo stretto legame esistente tra UNIX e C, si potrà affrontare alcuni aspetti particolari di questo linguaggio (e, da questo, di C++) nonché del suo ambiente di programmazione.

Diversamente dagli anni iniziali del diploma, nel corso di studi non è presente una parte culturalmente interessante quale lo studio della formalizzazione dei linguaggi di programmazione e della costruzione dei compilatori. Nel corso di FI2 si darà breve cenno di questi argomenti ed in particolare dell'analisi lessicale, come problema di string matching.

Per l'apprendimento della base teorica, lo studente è invitato ad esaminare con attenzione le varie tipologie di strutture dati e di algoritmi suggeriti, tenendo sempre presente l'applicazione pratica dello studio effettuato: a tale scopo, nel caso dei teoremi, lo studente può limitarsi agli enunciati, saltando le dimostrazioni (a meno che non siano assolutamente necessarie per la comprensione); egualmente si faccia per la valutazione della complessità, limitandosi a ricordare il risultato finale (tale risultato è spesso richiesto in sede d'esame per confrontare algoritmi alternativi).

Un prodotto dello sviluppo delle classi che implementano le strutture di dati e gli algoritmi del testo consigliato è una libreria abbastanza ampia e di uso generale. Allo studente è richiesto di esaminare questo materiale da due punti di vista:

1. Trattandosi di una raccolta di programmi completi, la libreria non va intesa solo come un supporto disponibile da usare ma va analizzata a fondo, soprattutto nelle parti che si riveleranno, di volta in volta, più significative; meglio ancora, lo studente è invitato a sviluppare in codice Java i metodi principali, seguendo la traccia e le specifiche del libro, e a confrontare la propria soluzione con quella offerta dalla libreria.
2. Come preparazione della seconda prova intermedia e delle successive prove scritte, lo studente deve aver analizzato le specifiche di interfaccia di tutte le classi fornite e deve essere in grado di identificarle nella documentazione fornita (che lo studente potrà consultare in sede di esame: si vedano le modalità) in modo da saper utilizzare la libreria stessa all'interno di programmi applicativi. Prima di affrontare una delle succitate prove, lo studente è invitato ad eseguire una stampa personale deòl sorgente della libreria stessa.

• consente di stimolare lo studente a svolgere programmi di un certo significato dovendo scrivere non moltissime righe di codice (perché il grosso è disponibile come classi e metodi della libreria);
• aiuta a capire l'importanza di adattarsi alle specifiche anche quando sono fornite da altri;
• aiuta a capire la programmazione object-oriented e quella 'in the large' (grossi progetti).

Riassumendo, gli argomenti principali del corso, che ne costituiscono gli obiettivi irrinunciabili, sono:

1. La programmazione object-oriented e le metodologie di sviluppo del software, in particolare un sottoinsieme UML (Uniform Modeling Language).
2. Il linguaggio Java.
3. Il confronto Java / C++.
4. Interfacce grafiche, API, AWT, applet
5. Valutazione della complessità degli algoritmi.
6. Strutture di dati fondamentali e loro realizzazione: collezione, sequenza, dizionario, albero, grafo.
7. Strutture ad accesso regolato e loro realizzazione: stack, coda, doppia coda, tabella hash.
8. Algoritmi di ordinamento e ricerca.
9. Cenni di analisi lessicale mediante DFA, confronto tra stringhe e l'algoritmo di Knuth-Morris-Pratt.
10. Cenni di analisi sintattica e traduzione automatica.
11. Cenni di multiprogrammazione.

Per quanto riguarda i prerequisiti, abbiamo cercato un più stretto collegamento tra FI1 e FI2, per cui gli argomenti trattati nel corso del primo anno vengono ripresi e ampliati nel corso di FI2. Per evitare inutili perdite di tempo, si dà per scontata la conoscenza già acquisita dei seguenti argomenti:

• strutture di dati elementari (variabili, vettori, matrici, classi);
• introduzione delle strutture di dati complesse (alberi, strutture dinamiche): queste saranno approfondite in FI2;
• sintassi e semantica di base del linguaggio Java (dichiarazione di classi, metodi, strutture di controllo, operatori, eccezioni);
• algoritmi di ricerca (lineare, bisezione) e ordinamento (insertion, bubble, merge, ecc.) principali;
• visite fondamentali di alberi.

Le tecniche acquisite saranno valutate attraverso la realizzazione di un progetto software che verrà assegnato a ciascuno studente (si veda Modalità d'esame).