Insegnamento obbligatorio della Laurea in Ingegneria Informatica, collocato al II periodo didattico del I anno.
Il corso approfondisce i concetti necessari per acquisire adeguate conoscenze di programmazione, intesa quale strumento per la soluzione di problemi. Si accentua il passaggio dalle capacità analitiche a quelle progettuali. Vengono presentate le soluzioni algoritmiche "classiche" dei problemi, e la teoria che sta alla loro base, con particolare riferimento a realizzazioni in C. Si propongono agli studenti esempi pratici di soluzione di problemi complessi, con analisi dei principali paradigmi risolutivi, e sono svolte esercitazioni pratiche ad essi connesse.

- Conoscenza dei meccanismi di allocazione della memoria e utilizzo dei puntatori
- Abilità di programmazione in C, utilizzando puntatori e strutture dat dinamiche
- Conoscenza delle nozioni elementari di analisi della complessità
- Conoscenza degli algoritmi di ordinamento
- Abilità di valutare la complessità di algoritmi e di migliorarne l'efficienza in termini di tempo di esecuzione e/o uso di memoria
- Conoscenza di strutture dati complesse e ADT (liste, code, heap, alberi, tabelle di hash e grafi) e dei relativi algoritmi
- Conoscenza delle strategie elementari di programmazione modulare in C
- Conoscenza dei paradigmi di programmazione ricorsiva e greedy, della programmazione dinamica e con memorizzazione
- Abilità di utilizzo di strumenti di ausilio alla programmazione
- Abilità di problem solving mediante progetto di strutture dati e algoritmi
- Abilità nelle tecniche di programmazione ricorsiva

- Conoscenza dell'architettura elementare dei sistemi di elaborazione (modello di Von Neumann)
- Conoscenza di sintassi, tipi di dato e costrutti base del linguaggio C
- Capacità di sviluppare semplici programmi in C, utilizzando construtti condizionali e iterativi, dati scalari a aggregati, I/O standard, file testo e funzioni
- Capacità di soluzione di problemi (algoritmici) elementari

- Analisi di algorítmi (8 h)
- analisi asintotica e complessità di caso peggiore; notazione 0, Q, W; equazioni alle ricorrenze
- Algoritmi di ordinamento: ordinamenti quadratico (selection sort, insertion sort), lineare (counting sort) linearitmico (quicksort, heapsort, mergesort);

- Strutture dati statiche e dinamiche e loro realizzazione in C (6 h)
- rappresentazione dei dati in memoria e gestione della memoria in runtime;
- puntatori (o riferimento a oggettì);
- allocazione di memoria statica, su stack, e dinamica;
- strutture linkate;
- strategie per scegliere la struttura dati.

- Modularità e realizzazione modulare di algoritmi e strutture dati (4 h)
- Il modello implementazione-interfaccia-client
- La realizzazione di un programma C con più sorgenti e header file
- Utilizzo elementare di strumenti di sviluppo e debug: es. make, gdb, cvs, '

- Ricorsione e programi ricorsivi (4 h)
- il concetto di ricorsione
- funzioni matematiche ricorsive
- procedure ricorsive semplici
- backtrack e implementazione della ricorsione.

- Matematica discreta (2 h)
- insiemi, relazioni, funzioni,
- grafi e alberi

- Oggetti astratti, collezioni di oggetti e ADT (6 h)
- Esempi modulari di strutture composte: es. vettori di liste, multi liste, '
- liste, stack, code FIFO, code generalizzate, coda prioritaria, heap

- Paradigmi algoritmici (6 h)
- divide et impera
- il paradigma greedy
- la programmazione dinamica e la ricorsione con memorizzazione

- Problem solving (4 h)
- Strategie di analisi e di definizione di strutture dati e algoritmi
- Problemi di ricerca e di ottimizzazione

- Strutture dati per tabelle di simboli (6 h)
- Alberi Binari di Ricerca
- Alberi bilanciati (RB-tree)
- B-tree
- Tabelle di hash

- Algoritmi sui grafi (8 h)
- visite in profondità e ampiezza
- applicazioni delle visite
- cammini minimi
- alberi ricoprenti minimi

- Esercitazioni in aula (22 h)
- Puntatori e allocazione dinamica di memoria
- Programmi modulari e strumenti di sviluppo
- Programmazione ricorsiva
- Problem solving e paradigmi algoritmici
- Esempi applicativi dalla teoria dei giochi: 8 regine, torre di Hanoi, righello, labirinto
- Strutture dati e ADT

- Esercitazioni in laboratorio (24 h)
- Puntatori e allocazione dinamica di memoria: vettori e matrici dinamiche, liste
- Programmi modulari e strumenti di sviluppo: make, gdb, cvs
- Programmazione ricorsiva con backtrack
- Problem solving e paradigmi algoritmici
- Strutture dati, ADT e tabelle di simboli: stack e FIFO, BST, tabelle di hash
- Algoritmi sui grafi

I testi, scelti tra quelli elencati, saranno comunicati a lezione dal docente titolare dell'insegnamento

R. Sedgewick, 'Algoritmi in C', III edizione, Addison-Wesley

T.H.Cormen, C.E.Leiserson, R.L.Rivest, 'Introduction to Algorithms', MC-Graw Hill

Deitel & Deitel,' Corso completo di programmazione C', Apogeo


- Materiale didattico a disposizione su Web
- Trasparenze proiettate in aula
- Esercizi e soluzioni

L'esame è costituito da una prova scritta, della durata di 150 minuti, è costituita da due parti:
- esercizi e/o domande sugli argomenti svolti a lezione
- La soluzione di un problema mediante linguaggio C
Durante lo svolgimento della prima parte della prova non è possibile consultare testi o appunti.