Corso di Laurea in Informatica - UniversitÓ degli Studi di Bari

 Laboratorio del Corso (A) di
 Algoritmi e Strutture Dati


E-mailDiarioMaterialeProgrammaEsami

Orario Esercitazioni A.A. 2003/04

Martedý 11-13 ricevimento stanza 525, 5░ piano, DIB
Giovedý 9-11 laboratorio laboratori 3░ piano DIB
Giovedý 10-12 esercitazione (*) aula IV-Palazzo delle Aule
(*) Le esercitazioni in aula non hanno cadenza fissa ma sono concordate in base alle esigenze del corso

Ultime Notizie

NB A partire dagli appelli di giugno05, per le prenotazioni rivolgersi ai docenti che hanno curato le esercitazioni (dott. Buono e Ferilli)
[31/01] Turni per la prova del 2/2/05
[02/07] Durante le prossime prove sarÓ data la possibilitÓ di utilizzare le proprie realizzazioni (in formato cartaceo, ottico, magnetico). Si ricorda che Ŕ anche consentito portare anche il proprio manuale (C o) C++.

Diario

[06/10] Inizio Corso: Organizzazione e Introduzione; Dal C al C++: Funzioni e Puntatori
[08/10] Aritmetica dei Puntatori; Array e puntatopri; Puntatori a funzione
[23/10] Argomenti avanzati Pascal e C/C++: puntatori e allocazione dinamica; Compilazione separata: unit e header
[27/10] Le classi: Introduzione; visibilitÓ public e private; costruttori e disttuttori
[30/10] Laboratorio: prova delle realizzazioni nei linguaggi noti. Esercizio sulle liste
[03/11] Esecitazione per la prova in itinere
[04/11] I prova in itinere
[06/11] Laboratorio: implementazione str. dati. Esercizio con liste e pile.
[13/11] Laboratorio: implementazione str. dati.
[13/11] C++: Classi e il qualificatore const, funzioni e classi friend, il puntatore this
[20/11] Laboratorio: implementazione str. dati. (lineari)
[27/11] Laboratorio: implementazione str. dati. (alberi)
[04/12] Laboratorio: implementazione str. dati. (grafi)
[11/12] Seminario: Classi e Funzioni template. La Standard Template Library del C++. EreditarietÓ

Materiale del Corso

Testi

H.M. Deitel, P. J. Deitel, C++ Fondamenti di programmazione, Apogeo (da cui sono tratte le slide)

Consigliati:

  • C. Horstmann, Fondamenti di C++, McGraw-Hill (introduttivo)
  • Lippman-Lajole, C++, corso di programmazione, Addison Wesley (molto completo)
  • B. Eckel. Thinking in C++ (disponibile online)
  • B. Stroupstrup, Il Linguaggio C++, Addison-Wesley (dall'inventore del linguaggio: molto tecnico)
  • S. Oualline, C++ - Corso di programmazione, Jackson libri (meno completo ed aggiornato)

Esami

Calendario

Gli esami sono riservati ai frequentanti 2001/02 (quinquennale) e 2002-03 (triennale).

Prenotazione

entro 3 gg. lavorativi prima della data dell'appello, lasciare cognome, nome e matricola presso la stanza del docente oppure attraverso il form che invia mail e conserva un log delle prenotazioni (si sconsiglia l'email per mancanza della garanzia di ricezione in tempo utile)

Date

Calendario Ufficiale Appelli presso il sito del Corso di Laurea
Le date delle prove di lab. per i vari appelli sono anche affisse sulle bacheche del Laboratorio SILAD (III piano).
Date (suscettibili di variazioni):
  • 10 febbraio 2004
Tutti alle ore 11-13 presso il SILAD (salvo diverso avviso)

ModalitÓ d'esame (a.a. 2003/04)

Come prerequisito, sarÓ richiesta la presentazione delle realizzazioni in C++ (in C per l'a.a. 2001/02) di tutte le strutture dati astratte presentate durante le lezioni di ASD, prodotte seguendo le specifiche fornite.

La prova di laboratorio consiste nella implementazione di un algoritmo che ne fa uso di una struttura dati astratta.
Durante la prova Ŕ consentito utilizzare le realizzazioni implementate in laboratorio (formato cartaceo, magnetico e ottico) nonchŔ il proprio manuale del linguaggio C/C++
Sorgenti ed eseguibili prodotti durante la prova saranno verificati, solo se funzionanti, al termine della prova stessa.

Il superamento della prova di lab. ha validitÓ per gli appelli entro i 90 gg. successivi (salvo diverso accordo)

Programma esercitazioni A.A. 2002/03

Introduzione
C e C++: un po' di storia, Risorse WWW su C++, Ambiente di sviluppo, Semplici programmi, Convenzioni per i file header e i namespaces

Le funzioni
I componenti di un programma in C++, Librerie, Definizioni e prototipi, Header, Le informazioni di memorizzazione, Le regole di visibilitÓ, Le funzioni inline, Passaggio di parametri di funzione e riferimenti, Gli argomenti di default, Scope, L'overloading delle funzioni generiche

Puntatori
Come si dichiarano e si inizializzano i puntatori , Operatori, chiamata per riferimento, Privilegi di accesso e passaggio dei parametri, I puntatori a funzione, Puntatori di manipolazione manipolazione di stringhe

Le classi e ADT
Strutture e classi, VisibilitÓ e accesso ai membri di una struttura, La separazione di interfaccia e implementazione, Le funzioni di accesso e di utilitÓ, I costruttori, I distruttori, L'assegnamento tra oggetti

Realizzazione C++ di ADT
Lista (vettori, corsori, puntatori), Pila, Coda, Albero binario, Albero n-ario, Tavola Hash, Grafo

Le classi: seconda parte
Gli oggetti e le funzioni membro costanti , Composizione, Funzioni e Classi friend , Il puntatore this , Gli operatori new e delete , Astrazione dei dati e information hiding , Container, iterator e proxy

Overloading degli operatori
L'overloading degli operatori, L'overloading degli operatori unari, L'overloading degli operatori binari, Conversioni tra tipi diversi

EreditarietÓ
I membri protected, Cast dei puntatori a classi, Overriding di membri della classe base in una classe derivata, Utilizzo dei costruttori e dei distruttori nelle classi derivate, Conversione implicita di un oggetto di una classe derivata in oggetto della classe base, Composizione ed ereditarietÓ, EreditarietÓ multipla

Le funzioni virtuali e il polimorfismo
Le funzioni virtuali, Le classi base astratte e le classi concrete, Il polimorfismo, Binding dinamico, Distruttori virtuali, EreditarietÓ di interfaccia e di implementazione

Tracce

[01/02] Implementare la struttura dati albero 3-ario con puntatori, con (almeno) gli operatori utili alla soluzione dei seguenti problemi:
  1. definizione della funzione che restituisce la profonditÓ dell'albero;
  2. definizione della funzione che stampa l'albero, un nodo per riga, con i figli indentati rispetto ai padri.
[02/02] Implementare la struttura dati albero binario con puntatori, nel quale ogni nodo contiene un intero; scrivere (almeno) gli operatori utili alla soluzione dei seguenti problemi:
  1. definizione della funzione che restituisce la profonditÓ dell'albero;
  2. definizione della funzione che, dato un intero n a scelta, restituisce la somma degli interi che si trovano nel percorso fra la radice e il nodo contenente n, se tale nodo esiste, -1 altrimenti.
[05/02] Si fornisca una realizzazione (in C o, se volete, in C++) che dimostri il corretto utilizzo e funzionamento della struttura dati di pila di interi e delle funzioni richieste di seguito:
  1. scrivere gli operatori di inserimento ed eliminazione di un oggetto, e di stampa del contenuto della pila dal fondo alla cima;
  2. definire la funzione che, ricevute in input due stringhe stringa1 e stringa2 rappresentanti due numeri interi n1 e n2, restituisce una stringa che rappresenta l'intero somma dei due numeri Suggerimento: si utilizzino tre pile (due per gli addendi, una per il risultato) e si tenga conto dell'eventuale riporto.
[07/02] Si fornisca una realizzazione (in C o C++) che dimostri il corretto utilizzo della struttura dati ad albero di interi e delle funzioni richieste di seguito:
  1. definizione delle funzioni di immissione e stampa del contenuto dell'albero
    (un nodo per riga e indentato a seconda della sua profonditÓ);
  2. definizione di una funzione (ricorsiva o iterativa con stack ausiliario) di stampa la somma dei pesi dei nodi dell'albero, dove il peso di un nodo Ŕ pari al numero dei suoi discendenti
[09/02] Implementare mediante opportuna realizzazione (C o C++) la struttura di lista per rappresentare polinomi come liste di monomi (coefficiente, grado) dove la lista
< (a0,0), (a1,1), (a2,i),... , (an,n) >
starÓ a rappresentare il polinomio:
p(x) = a0 + a1x + a2x2 + ... + anxn
Tenendo presente che non Ŕ detto che siano presenti i monomi per tutti i gradi, la struttura dati va utilizzata per risolvere i seguenti problemi (dimostrando il corretto funzionamento con almeno una chiamata dal main):
  1. definizione della funzioni di immissione (robusta) e stampa di un polinomio nella forma sopra rappresentata;
  2. definizione di una funzione che per una data x passata in input calcola e restituisce il valore di p(x);
  3. (per volenterosi) definizione di una funzione che produce la lista della derivata prima di p'(x)
[11/02] Implementare mediante opportuna realizzazione la struttura di coda di record < procID, time >
La struttura dati va utilizzata per implementare opportunamente le seguenti funzioni, mostrando il loro corretto funzionamento con almeno una chiamata dal main:
  1. funzioni di immissione (read_queue()) e stampa (print_queue()) di una coda
  2. funzione di ordinamento della coda (sort_queue()) in base al campo time
[12/02] Sia G un grafo realizzato con matrice di adiacenza;
realizzare in C (o C++)
  1. la funzione che consente di creare il grafo;
  2. la funzione che restituisce il numero di archi afferenti ad un nodo scelto dall'utente.
Scrivete tutti gli operatori utili alla soluzione del problema, producendo un programma funzionante.
[06/03] Implementare la struttura dati di albero 3-ario (realizzazione a scelta), contenente una stringa per ogni nodo con gli operatori utili alla soluzione dei seguenti problemi:
  1. definizione delle funzioni di immissione e stampa dell'albero;
  2. definizione della funzione che, per ogni cammino, stampa le frase ottenuta concatenando le stringhe sui nodi che vi appartengono, separando le stringe dal carattere spazio.
[inizio pagina]