PROGRAMMAZIONE II a.a.2006/2007

Prof.ssa EMANUELA FACHINI, dott.ssa IRENE FINOCCHI, dott. ANGELO SPOGNARDI.

• Programma del corso a.a. 2006/2007
• Modalità prenotazioni ed esami
• Diario delle lezioni
• Diario delle esercitazioni

PROF.SSA EMANUELA FACHINI STUDIO : Stanza 338, D.to Informatica Via Salaria,113 - 00198 ROMA TEL . 0649918314 E-MAIL : l'indirizzo si ottiene aggiungendo al cognome @di.uniroma1.it ORARIO DI RICEVIMENTO: GIOVEDÌ dalle ore 14 alle ore 16

DOTT. SSA IRENE FINOCCHI STUDIO : Stanza 311, D.to Informatica Via Salaria,113 - 00198 ROMA TEL . 06 4991 8428 E-MAIL : l'indirizzo si ottiene aggiungendo al cognome @di.uniroma1.it ORARIO DI RICEVIMENTO: LUNEDÌ dalle ore 10:00 alle ore 11:30 (avvisatemi prima via e-mail).

DOTT. ANGELO SPOGNARDI STUDIO : Stanza 301, D.to Informatica Via Salaria,113 - 00198 ROMA TEL . 0649918431 E-MAIL : l'indirizzo si ottiene aggiungendo al cognome @di.uniroma1.it ORARIO DI TUTORAGGIO Martedì 12,30-14, Laboratorio AST, via Tiburtina 205

I testi e, nel caso della prova di giugno, le soluzioni degli esercizi proposti nei precedenti appelli si scaricano qui:

PII4Luglio07.pdf,

ProgII19Giu07Sol.pdf

Coloro che vogliono sostenere l'esame non "dimentichino" di esercitarsi a programmare, scaricare il materiale in rete e leggerlo prima di presentarsi all'esame!

Obiettivo del corso.

L'obiettivo del corso, che prosegue il cammino iniziato con Programmazione I, é quello di portare lo/a studente/ssa ad un buon livello di dimestichezza programmativa. Il linguaggio di riferimento è il C. Alla fine del corso lo studente

• saprà progettare e implementare un programma in C
• conoscerà le tecniche di base per verificare la correttezza del suo programma
• sarà in grado di scrivere moduli di programmi che possano essere facilmente combinati per costruire grandi programmi
• sarà in grado di scrivere programmi facili da modificare, correggere,aggiornare,...

Il corso é fortemente integrato con il corso di Laboratorio Programmazione.

Programma del corso. Ricorsione. Richiami di programmazione ricorsiva: i fondamenti della ricorsione; lo stack delle chiamate ricorsive; esempi di programmi ricorsivi. La "tail ricursion". Richiami su strutture dinamiche ricorsive: le liste.

Cenni di complessità di spazio e di tempo per gli algoritmi e i programmi. Valutazione asintotica e miglioramento delle costanti moltiplicative. Confronto tra soluzioni iterative e ricorsive.

Tecniche per la scrittura di programmi corretti. L'importanza della specificazione precisa di un programma. Precondizioni e postcondizioni delle funzioni. Uso di assert per la loro verifica. Strutturazione dei programmi: sottoprogrammi e moduli. Tipi di dato astratti. L'information hiding. Pile e code: definizione e implementazione mediante liste e vettori. Invarianti come strumenti di progettazione di cicli. Applicazione del metodo al problema dell'ordinamento.

Alberi binari. definizione e implementazione. Proprietà degli alberi binari: altezza, foglie, relazione tra numero dei nodi e altezza in un albero binario qualunque, alberi pieni, completi, criteri di bilanciamento. Gli alberi binari di ricerca.

Riferimenti: TESTI CONSIGLIATI Al Kelley, I. Pohl C, didattica e programmazione, Addison-Wesley, traduzione italiana a cura del Prof. G. Pighizzini, Univ. Milano.
In questo testo son trattati quasi tutti gli argomenti del corso di Programmazione II.

BIBLIOGRAFIA RAGIONATA

Il C introdotto in confronto a Java, per chi ha conosce Java. CperJavaExpert.pdf:
(i commenti alla bibliografia seguente sono da me condivisi ma si devono al prof. R. Silvestri):
H.M. Deytel , P.Deytel C corso completo di programmazione, Apogeo, 2000.
(questo testo è già stato utilizzato a Programmazione I, e servirà ancora per alcune lezioni di Programmazione II).

S.P. Harbison III, G.L. Steele Jr C: A Reference Manual Prentice Hall.
Un manuale di riferimento per il linguaggio C estremamente curato e preciso. Utilissimo per risolvere dubbi circa: ciò che è C standard (ANSI/ISO) e ciò che non lo è, portabilità, compatibilità con il C++, ecc. Fortemente consigliato a chiunque voglia fare un uso non occasionale del linguaggio C.

B.W. Kernighan, D.M. Ritchie Linguaggio C Jackson libri.
Il classico manuale del linguaggio C.

B.W. Kernighan, R. Pike The Practice of Programming Addison-Wesley. Tratta in modo sintetico e significativo tutti gli aspetti della programmazione. Dalle strutture dati ed algoritmi al debugging e testing, dallo stile di programmazione alla progettazione di librerie, passando per l'analisi delle prestazioni e i metodi per migliorare la portabilità. I linguaggi considerati sono: C, C++ e Java.

J. Bentley Programming Pearls Addison-Wesley.
Molti dei temi trattati nel libro di Kernighan e Pike sono qui elaborati in modo originale e stimolante. Pieno di divertenti ed istruttivi aneddoti che mostrano la reale differenza tra la teoria e la pratica della programmazione e financo dell'ingegneria del software. Usa i linguaggi C e C++.

S. Mc Connell Code Complete: A Practical Handbook of Software Construction. Microsoft Press.
Un trattamento quasi enciclopedico di tutto ciò che riguarda la programmazione. Tantissimi suggerimenti e consigli per migliorare la programmazione in un qualsiasi linguaggio imperativo: C, Pascal, Fortran, ecc.

Corso in linea di A. D. Marshall 1994-9 [[http://www.cs.cf.ac.uk/Dave/C/CE.html][Programming in C, UNIX System Calls and Subroutines using C.]] Questo corso è completo: da un'introduzione ad argomenti avanzati di programmazione in C sotto UNIX, è scritto in modo chiaro e con molti esempi .

L'ESAME CONSISTE DI una prova scritta e una prova orale, che può limitarsi ad una discussione dello scritto.

• La prova scritta è divisa in due parti:
• nella prima parte si chiederà la stesura di due brevi funzioni C. Errori nel primo esercizio pregiudicano tutto l'esame.
• Il secondo esercizio consisterà nella stesura di un funzione (tipicamente ricorsiva) in C (su liste concatenate o alberi,...)
• la seconda parte è più variabile sugli argomenti del corso, potrebbe trattarsi della costruzione di dati di test per una funzione in C,.... Gli esercizi risolti a casa e consegnati entro le scadenze indicate contribuiranno al punteggio finale con un incremento da 0 a 2 punti sul voto raggiunto con le prove scritte e l'orale.

L'esame scritto si può sostenere nei seguenti modi

Prova intermedia ad aprile + esame finale a fine giugno

Esame completo a fine giugno

Esame completo a settembre

L'esame completo sarà diviso in due parti, la prima dovrà essere sostenuta solo da coloro che non hanno superato la prova intermedia o che vogliono migliorarne il voto, la seconda dovrà essere sostenuta da tutti.

Valutazione Il voto finale è ottenuto sommando il voto delle prove scritte, di quella orale e l'eventuale punteggio relativo agli esercizi da risolvere a casa.

Per invogliare gli studenti a sostenere l' esame affrontando la prova intermedia e concludendo l' esame entro giugno il voto, superiore al 18, delle prove scritte sostenute in queste occasioni viene incrementato dell'8%.

Appelli e Date

Prova intermedia: Mercoledi 18 Aprile Ore 9:00 Aula NEC1

Esame finale+Esame Completo+I° Recupero Prog I:

1° appello: 19/06/07 ore 15:00 AULA NEC1

2° appello: 03/07/07 ore 15:00 AULA NEC1

NOTA BENE:I 2 appelli a fine corsi sono ECCEZIONALI solo per quest'anno. Ogni studente potrà presentarsi a solo uno di questi

Recupero Prog II: 19/09/07: ore 15:00 AULA NEC1

2. Le prove scritte durano almeno due ore.

3. Tutte le prove scritte consistono di esercizi di complessità uguale o inferiore a quello svolti in aula durante lo svolgimento delle lezioni.

Nota bene: non è necessario aver superato l'esame di Programmazione I per sostenere le prove intermedie di Programmazione II , mentre lo è per affrontare l'esame di Programmazione II.

6. Gli studenti sono tenuti a PRENOTARE la loro prova di esame entro le ore 12 del giorno precedente la data dell'appello.

7. Gli studenti il cui cognome inizia con una lettera compresa nell'intervallo A-D devono seguire le lezioni e sostenere l'esame con la prof.ssa Fachini. Deroghe a questa regola sono possibili ma solo a seguito di cambio di canale.

DIARIO DELLE LEZIONI

mercoledì 6/1/2007 Esercizi preparazione esame. Alcune soluzioni:EsSol.pdf. EsAlbBibSol.pdf:

mercoledì 6/1/2007 Esercizi preparazione esame. TestiEsPIPII.pdf.

mercoledì 30/5/2007 Esercizi sulla ricorsione su alberi.TestiEsProposti2.pdf

mercoledì 30/5/2007 Esercizi sulla ricorsione su alberi. testiEsAlbBin.pdf

mercoledì 23/5/2007 Introduzione al testing: Testing.pdf, ancora un esercizio sugli alberi: EsAlbSbil.pdf

martedì 22/5/2007 Alberi binari di ricerca: determinazione dell'i-simo elemento in un ABR, verifica bilanciamento nel numero dei nodi. VerAlbBil1.pdf

mercoledì 16/5/2007 Alberi binari di ricerca: esercizi. Gli esercizi proposti: verifica se un albero binario è un albero binario di ricerca e determinazine del successivo, nell'ordine, di un elemento dell'albero. Qui le soluzioni proposte e su cui riflettere: ABR.pdf

giovedì 10/5/2007 Tabelle dinamiche: implementazini su vettori e liste. Alberi binari di ricerca: le tre operazioni.

mercoledì 9/5/2007 Ancora un esempio sugli invarianti di ciclo. Alberi binari e alberi binari di ricerca. InsSort.pdf.tar. Qui trovate una versione della Partition2 senza rischio di accesso a memoria non disponibile: partition2.pdf.

mercoledì 2/5/2007 Algoritmi fondamentali: ordinamenti Quicksort.pdf

martedì 24/4/2007 Soluzioni esercizi prova intermedia: solEsEsonero.tgz versione aggiornata con due ulteriori soluzioni del primo esercizio e una piccola modifica del terzo, con una funzione che puo' essere utile...

mercoledì 11/4/2007 Algoritmi fondamentali: ordinamenti Mergesort.pdf

mercoledì 4/4/2007 La coda: definizione dell'ADT e implementazioni. Coda.pdf

giovedì 29/3/2007 Esercizi sulla ricorsione. Esercizi proposti:

1. liste di Fibonacci: scrivere una funzione ricorsiva in C che dà vero se la lista di interi è una lista di Fibonacci, in un caso richiedendo che l'i-simo elemento della lista sia l'(i-1)-simo numero di Fibonacci, per i che varia 1 e il numero di elementi della lista, e nell'altro richiedendo che l'(n-i)- simo elemento sia l'i-simo elemento della lista, per 0<=i<n, dove n è il numero di elementi della lista. La verifica deve essere compiuta tramite una scansione della lista senza utilizzare funzioni per il calcolo dei numeri di Fibonacci, nè il calcolo degli elementi della lista.

2. scrivere una funzione ricorsiva che fonde due liste ordinate in una lista ordinata che contiene tutti gli elementi delle due liste date, senza allocare ulteriore memoria.

3. scrivere una funzione ricorsiva in C che data una lista di interi, restituisce una nuova lista in cui l'elemento j-simo contiene la somma degli elementi della lista data esclusi i primi j-1. In questo caso si deve allocare la memoria perchè la lista originaria deve essere conservata.

mercoledì 28/3/2007 Esempi di uso della pila: la valutazione di una espressione aritmetica in RPN, ValPostfissa.pdf e la conversione di un'espressione aritmetica infissa nell'equivalente postfissa, aritmPostfissa.pdf:

mercoledì 21/3/2007 Tipi di dato astratto: l'esempio della pila Pila.pdf.

giovedì 14/3/2007 Ricorsione e problem solving. I lucidi utilizzati si scaricano qui * LucProblSolv.pdf, qualche nota PROBLEMSOLVING.pdf. Qualche indicazione sull'uso delle macro con parametri:Macro.pdf.

mercoledì 13/3/2007 Ricorsione e puntatori: richiami con esempi di funzioni ricorsive su liste concatenate e confronto caso iterativo. L'uso di assert per il controllo dei casi eccezionali. I lucidi utilizzati si scaricano qui ListeOrd.pdf,LucProgRobusta.pdf, qualche nota in ProgRobusta.pdf

mercoledì 7/3/2007 Precondizioni e postcondizioni. Ricorsione e puntatori: richiami con esempi di funzioni ricorsive su liste concatenate. I lucidi utilizzati si scaricano qui PrePost.pdf, RiPuntEs.pdf.

giovedì 1/3/2007 Altri esempi sulla ricorsione. LucidiRicorsione.pdf

mercoledì 28/2/2007 Introduzione al corso: programma e motivazioni. Ricorsione. I lucidi utilizzati si scaricano qui IntrPII.pdf Alcune note sul contenuto delle due prime lezioni: Ricorsione.pdf

Calendario esami di Programmazione II: Sarà necessario prenotarsi per ogni prova!

Avvisi Importanti

• L'esame orale si svolgerà giovedi 21/6/2007 alle ore 10:00 in Aula Seminari.

• Il ricevimento della Prof.ssa Fachini di giovedi 28/6/2007 e' sospeso.

• I risultati del secondo homework sono disponibili su questa pagina.

• Il secondo homework è stato assegnato. Il testo ed ulteriori informazioni sono disponibili su questa pagina.

• Il 24 e il 26 aprile prossimo per le lezioni di Architettura degli elaboratori e di Programmazione II ci sarà uno scambio di orario, quindi

• Alcune note e suggerimenti per svolgere il primo homework sono on-line su questa pagina.

• Il primo homework è stato assegnato. Il testo ed ulteriori informazioni sono disponibili su questa pagina.

Links Utili

Corso introduttivo di Programmazione C, di Steve Summit, con note al testo di Kernighan e Ritchie.
FAQ su C  domande frequenti su programmare in C, di Steve Summit
Corso introduttivo di Programmazione C, in italiano, di Fiorella Sartori del CISCA - Presidio Informatico Telematico Multimediale della Facoltà di Scienze MM.FF.NN.- Università degli Studi di Trento

Biografie di matematici e informatici.
Una breve storia della Computer Science

Pagina dedicata dal MIT a Grace Murray Hopper, l'inventrice del compilatore.

Breve biografia di C.A.R. Hoare.
Un articolo sula genesi di SIMULA.
Una breve biografia seguita da un'intervista a Parnas.
La home-page di Barbara Liskov.
La home-page di John Guttag.