|
Linguaggi di Programmazione |
Programma del corso:
| Lezione |
Argomenti |
Materiale |
|---|---|---|
|
28-09-2009 |
Definizione del concetto di linguaggio di programmazione. Analogie e
differenze con il linguaggio naturale. Proprietą di un linguaggio di
programmazione.
Cenni storici all'evoluzione dei linguaggi di programmazione. Classificazione dei linguaggi di programmazione in base a: esigenze applicative, livello di astrazione, paradigma di programmazione. Linguaggi imperativi e dichiarativi. Cenni fondamentali ai traduttori: compilatori ed interpreti. Analisi comparativa dei linguaggi compilati ed interpretati. |
|
|
05-10-2009 |
Calcolabilitą e tesi di Church Turing. Complessitą asintotica degli
algoritmi. la notazione O, Ω e Θ. Esempi: alcuni semplici
algoritmi di ordinamento.
Allocazione statica e dinamica della memoria. I meccanismi di allocazione dinamica della memoria in c/c++: malloc e free in C; new e delete in C++. Esempi. |
Ulteriori riferimenti Esempi |
|
07-10-2009 |
Introduzione alle tecniche algoritmiche di programmazione. Tecnica divide
et impera: Iterazione e ricorsione. Cenni alla programmazione
dinamica. Strutture dati in memoria centrale. Definizioni Strutture dati indicizzate e collegate. |
|
|
12-10-2009 |
Le strutture dati lista, pila e coda.
Le liste e le relative operazioni. Complessitą computazionale delle operazioni sulle liste. Implementazione C. Esempi. Le pile e le relative operazioni. Complessitą computazionale delle operazioni sulle pile. Implementazione C. Esempi. Le code e le relative operazioni. Complessitą computazionale delle operazioni sulle code. Implementazione C. Esempi. |
|
|
14-10-2009 |
Esercitazione su liste, pile e code. | |
|
19-10-2009 |
La struttura dati albero.
Alberi generali e relative definizioni. Alberi binari. Visite in ordine anticipato, simmetrico e posticipato. Operazioni di inserimento e cancellazione. Analisi della complessitą computazionale delle operazioni. Alberi binari di ricerca. Proprietą della visita in ordine simmetrico. Operazioni: inserimento, massimo e minimo, predecessore e successore, cancellazione. Analisi della complessitą computazionale delle operazioni sugli alberi binari di ricerca. |
Materiale didattico supplementare (dal Web):
Codice sorgente in C: |
|
21-10-2009 |
Esercitazione sugli alberi binari. | |
|
26-10-2009 |
Conseguenze dell'ordine di inserimento dei dati sugli alberi binari di ricerca. Degenerazione in liste e conseguenze computazionali. Concetto di albero bilanciato. Svolgimento di alcuni temi di esame concernenti gli alberi binari. |
|
| 28-10-2009 | Esercitazione | Download |
|
02-11-2009 |
Esercitazione | Download |
|
04-11-2009 |
Esercitazione | Download |
|
09-11-2009 |
Esercitazione | Download |
|
11-11-2009 |
La struttura dati grafo.
Definizioni preliminari. Rappresentazione dei grafi in memoria centrale. Visite in ampiezza e profonditą di un grafo. Implementazione in C di una struttura dati basata su matrice di adiacenza. Analisi del complessitą computazionale delle operazioni di visita in ampiezza e profonditą sulla struttura dati. |
Materiale didattico supplementare (dal Web):
Codice sorgente in C |
|
16-11-2009 |
Visita di un grafo.
Visita in ampiezza. Visita in profonditą: ricorsiva ed iterativa (con gestione esplicita della pila). Costo delle operazioni di visita su matrice di adiacenza. Esempi. |
|
|
Tecniche algoritmiche di programmazione: Backtracking. Analisi
generale della tecnica e delle sue applicazioni. Alcune applicazioni:
generazione di tutti i sottoinsiemi di un insieme, generazione di tutte
le permutazioni.
Esempio pratico: generazione di tutti gli anagrammi di una stringa. |
Materiale didattico supplementare (dal Web) | |
|
18-11-2009 |
Concetto di cammino su grafo. Cammino ciclico ed aciclico. Peso di un cammino. Problema dell'individuazione dei cammini minimi con singola sorgente su grafi orientati e pesati con pesi non negativi. L'algoritmo di Dijkstra. Analisi della complessitą computazionale. | Materiale didattico supplementare (dal Web) |
|
23-11-2009 |
Sistemi aperti ed applicazioni avanzate.
Estensione delle funzionalitą dell'ambiente Matlab tramite MEX function in C. Principali differenze tra M file e Mex function. La libreria mex.h. Anatomia di una MEX function. Lo scambio di parametri tra Matlab e MEX function: funzioni per il binding dei parametri attuali di input ed il binding dei parametri attuali di output. Compilazione ed esecuzione di una MEX function tramite l'ambiente interattivo dei comandi di Matlab. Esempio generazione di numeri primi tramite MEX function. |
Materiale didattico |
|
23-11-2009 |
Esercitazione | Download |
|
25-11-2009 |
Esercitazione | Download |