Corso di laurea in Informatica e Comunicazione Digitale



Scaricare 16.43 Kb.
29.12.2017
Dimensione del file16.43 Kb.

Linguaggi di programmazione + laboratorio (a.a. 2009-2010) - laurea INFCD – Bari

Emanuele Covino – Programma definitivo
Requisiti:

Corso di Programmazione (linguaggio C). Corso di Algoritmi e strutture dati (fondamenti del C++).



Teoria


Introduzione a un generico linguaggio (Gabbrielli, Martini – capitolo 1 e 13; Sethi - capitolo 2)

Panoramica storica (GM 13). Macchine astratte e interprete (GM 1). Implementazione di un linguaggio. Gerarchie di macchine astratte. Un linguaggio per le espressioni (mosaic): sintassi e semantica (S 2).


Sintassi e semantica (Ausiello – capitolo 2; Gabbrielli, Martini - capitolo 2; Sethi – capitolo 10)

Grammatiche libere. Derivazioni e linguaggi. Alberi di derivazione. La gerachia di Chomsky. BNF e diagrammi sintattici. Il problema del riconoscimento. Linguaggi regolari e automi a stati finiti. Automi non deterministici. Vincoli sintattici contestuali. Compilatori. Semantica. Pragmatica.


Nomi e ambiente (Gabbrielli, Martini - capitolo 4; Sethi - capitoli 3 e 4)

Nomi ed oggetti denotabili. Ambiente e blocchi: tipi ed operazioni sull’ambiente. Regole di scope: scope statico, dinamico, problemi di scope. Esercizi.


Gestione della memoria (Gabbrielli, Martini – capitolo 5; Sethi - capitolo 4)

Tecniche di gestione della memoria. Gestione statica. Gestione dinamica tramite pila: blocchi in-line, procedure, gestione della pila. Gestione dinamica tramite heap: blocchi di dimensione fissa e variabile. Implementazione delle regole di scope: catena statica, display, lista di associazioni e CRT. Esercizi.


Strutturare il controllo (Gabbrielli, Martini – capitolo 6; Sethi - capitolo 2 e 3)

Espressioni: sintassi, semantica, valutazione. Comando: variabili, assegnamenti. Comandi per il controllo di sequenza: comandi espliciti, condizionali, iterativi. Programmazione strutturata. Ricorsione: ricorsione in coda. Esercizi.


Astrarre sul controllo (Gabbrielli, Martini – capitolo 7; Sethi – capitolo 5)

Sottoprogrammi: astrazione funzionale, passaggio dei parametri. Funzioni di ordine superiore; come parametro, come risultato. Eccezioni: implementazione. Linker. Eccezioni in C++. Esercizi.


Strutturare i dati (Gabbrielli, Martini – capitolo 8)

Tipi di dato. Sistemi di tipi. Tipi scalari e composti. Equivalenza fra tipi: per nome, strutturale. Compatibilità e conversione. Polimorfismo: overdoading, polimorfismo universale parametrico e di sottotipo. Controllo e inferenza di tipo. Sicurezza. Dangling reference. Garbage collection. Esercizi.


Programmazione object oriented (Gabbrielli, Martini – capitoli 9 e 10; Sethi - capitolo 6)

Astrarre sui dati: tipi astratti, nascondere l’informazione. Limiti dei tipi di dato astratti. Concetti fondamentali: oggetti, classi, incapsulamento, sottotipi, ereditarietà (singola e multipla), selezione dinamica dei metodi. Aspetti implementativi: ereditarietà singola, classe base fragile. Esercizi.


Il paradigma funzionale (Gabbrielli, Martini – capitolo 11; Sethi; dispensa pagina del corso)

Computazioni senza stato: espressioni e funzioni, computazione come riduzione, ingredienti fondamentali. Valutazione: valori, sostituzione senza cattura, strategie di valutazione: per valore, per nome, lazy. Confronto fra strategie. Programmare in un linguaggio funzionale: ambiente locale, pattern matching, tipi. Introduzione a ML: espressioni elementari, valori e tipi, identificatori, binding e dichiarazioni, patterns, definire funzioni, polimorfismo e overloading; definire nuovi tipi, eccezioni, caratteristiche imperative. La macchina SECD. Esercizi.



Python (slides sul sito del corso; inoltre, vedere testi consigliati)

Introduzione alle problematiche. Overview storica. Linguaggi ad alto livello: interpretati e compilati. Primi passi con Python - esempi con l'interprete. Tipizzazione e controllo sui tipi e sulle operazioni. Numeri e espressioni. Tipi immutabili. Tipi mutabili. Binding dinamico. Controllo del flusso. Funzioni, Classi e Metodi. Ereditarietà in Python. Dinamicità dei parametri. Duck Typing. Oggetti e gestione dinamica (esempio di qualche struct in C tipica dell'interprete Cpython). Web Framework (Django).


Testi consigliati:

  • Gabbrielli, Martini - Linguaggi di programmazione - McGraw-Hill.

  • R. Sethi - Linguaggi di programmazione – Zanichelli.

  • Ausiello, D’amore, Gambosi - Linguaggi, modelli, complessità – Utet.

  • Harper - Introduction to standard ML – http://www.di.uniba.it/~covino/

  • Harper - Introduction to standard ML (revised) - http://www.cs.cmu.edu/~rwh/introsml/

  • Downey, Elkner, Meyers - How to Think Like a Computer Scientist: Learning with Python - Gree Tea Press - http://thinkpython.com e  http://www.python.it

  • Deitel, Deitel, Liperi, Wiedermann - Python how to program - Prentice Hall.

  • altro materiale su Python - http://www.voidspace.org.uk/thestore.shtml.




Laboratorio
Linguaggio C++ (Deitel & Deitel – capitoli 9, 10, 12, 13)

Linguaggio C. Classi e astrazioni dati. Classi friend. Allocazione dinamica della memoria. Ereditarietà. Polimorfismo. Eccezioni.


Testi consigliati

  • Deitel, Deitel - C++ fondamenti di programmazione, II edizione – Apogeo

  • Deitel, Deitel - C++ tecniche avanzate di programmazione - Apogeo (per le eccezioni)

  • Oualline S.. C++, corso di programmazione. Jackson libri

  • Qualsiasi manuale di C++ che trovate in biblioteca


Programmi da svolgere

Realizzare i seguenti programmi, applicando le caratteristiche tipiche del C++; realizzare anche i programmi proposti durante le esercitazioni in laboratorio.




  • Algoritmi di ordinamento e ricerca.

  • Gestione di stringhe: contare i caratteri, ordinarli, scrivere e leggere stringhe.

  • Data una espressione aritmetica in forma infissa, definire la sua notazione postfissa e prefissa.

  • Data una espressione aritmetica in forma postfissa calcolarla usando uno stack.

  • Definire la struttura coda usando un vettore unidimensionale, una lista linkata e una doppiamente linkata.

  • Definire la struttura stack usando un vettore unidimensionale, una lista linkata.

  • Definire la struttura albero binario (puntatori); definire un albero binario di ricerca.

  • Alberi , liste e pile (come sopra) usando le classi.

  • Costruire un programma che gestisca le date e il tempo.

  • Implementare una lista bidirezionale con i puntatori; ogni campo della lista contiene un intero. Ordinare la lista con uno degli ordinamenti che avete studiato. Implementare (almeno) gli operatori dell'algebra utili alla soluzione.

  • Il tipo di dato dequeue (double ended queue) è una sequenza modificabile ad entrambi gli estremi, in cui è possibile inserire un elemento in testa o in fondo, e/o cancellare un elemento dalla testa o dal fondo. Fornire una realizzazione in C++ di tale tipo di dato, mediante puntatori, implementando gli operatori di inserimento e cancellazione dalla testa e dalla coda.

  • La profondità di un albero è il massimo livello delle sue foglie. Si fornisca una realizzazione in C++ di tale struttura e la funzione che calcola la profondità dell’albero.

  • Si fornisca una realizzazione in C++ di un albero i cui nodi contengono valori interi. Dopo aver scritto gli operatori necessari alla soluzione, si implementi la funzione che cancella tutte le foglie per le quali il percorso radice-foglia ha somma complessiva dei valori uguale a k.

  • Dati due insiemi realizzati con liste non ordinate, realizzare in C++ la funzione INTERSEZIONE, implementando (almeno) gli operatori dell’algebra utili alla soluzione.

  • Scrivere in C++ l’implementazione di due liste monodirezionali ordinate, realizzate con i puntatori, (scrivere gli operatori utili alla soluzione del problema). Scrivere la funzione che le fonde, restituendo una unica lista ordinata.

  • Data una pila realizzata con puntatori, scrivere la funzione C++ che restituisce la pila rovesciata. Scrivete gli operatori utili alla soluzione del problema.

  • Dato un albero i cui nodi contengono valori interi, scrivere gli operatori tipici di tale struttura (in particolare, l’inserimento e la cancellazione di una foglia), e elencare i valori contenuti nei nodi effettuando una visita in ampiezza (o in profondità).





©astratto.info 2017
invia messaggio

    Pagina principale