Home page di Marco Liverani

Corso IN110 Algoritmi e Strutture Dati

“[...] da allora assunsi la mia "filosofia": mi occuperò soprattutto
degli studenti più deboli e parlerò sempre, a voce alta, a quelli dell'ultimo banco.”
−− Mario Fiorentini

Il corso IN110 Algoritmi e Strutture Dati è finalizzato a fornire una competenza di base sull'informatica e sulla programmazione dei computer in particolare. Non sono richiesti prerequisiti di tipo informatico, ma esclusivamente delle competenze elementari di Algebra e Logica Matematica. Il corso è attivo presso il Corso di Laurea in Matematica del Dipartimento di Matematica e Fisica dell'Università degli Studi Roma Tre ed è destinato agli studenti iscritti al primo anno.

Il corso si suddivide in tre parti principali: la prima è una introduzione sintetica e molto generale sui computer come esecutori di metodi risolutivi per problemi di vario genere. Vengono descritte le caratteristiche di base dei calcolatori elettronici e del sistema operativo UNIX/Linux; viene anche fornita una prima descrizione dell'approccio algoritmico alla soluzione di problemi mediante un computer. La seconda (Programmazione in linguaggio C) e la terza parte (Algoritmi e strutture dati fondamentali) del corso si integrano e si mescolano l'un l'altra: facendo uso del linguaggio di programmazione C, di cui viene fornita una descrizione dettagliata che prescinde da ogni eventuale competenza pregressa degli studenti, vengono affrontati alcuni problemi fondamentali ed alcuni dei principali e più interessanti algoritmi risolutori, rivolgendo anche l'attenzione al concetto di complessità computazionale; saranno presentati anche alcuni metodi fondamentali per la soluzione di problemi di ottimizzazione combinatoria.

È disponibile il programma ufficiale del corso per l'anno accademico 2021/2022.

Sito web del corso

All'indirizzo http://www.mat.uniroma3.it/users/liverani/IN110 è disponibile il sito web dedicato alla didattica del corso IN110. Sul sito è possibile trovare:

• una descrizione del corso e dei suoi contenuti generali;
• il diario delle lezioni tenute durante l'anno accademico in corso, con numerosi link ad appunti e alle soluzioni degli esercizi proposti durante le esercitazioni;
• una sezione dedicata agli esami, con le date degli appelli, i risultati e le soluzioni degli esercizi proposti nelle ultime sessioni;
• una raccolta di esercizi svolti in linguaggio C;
• i riferimenti bibliografici utili per la preparazione dell'esame;
• la bacheca delle comunicazioni agli studenti.

Programma indicativo del corso

1. Calcolatori, sistemi operativi, algoritmi

Introduzione alle caratteristiche del calcolatore ed al rapporto programmatore/esecutore; compiti ed abilità del programmatore; principali caratteristiche ed abilità dell'esecutore, operazioni di base (operatori logici, aritmetici e di confronto).

Struttura generale di un calcolatore elettronico, principali componenti di cui è costituito. Introduzione al sistema operativo UNIX/Linux, ai comandi della shell e all'utilizzo di alcuni importanti pacchetti software (Latex, GNUplot, ecc.).

Linguaggi di programmazione. Istruzioni fondamentali di un linguaggio di programmazione generico. Algoritmi e programmi; diagrammi di flusso. Regole della programmazione strutturata; approccio top-down alla soluzione di un problema.

2. Il linguaggio C

Linguaggio macchina, linguaggi di alto livello; compilatori ed interpreti. Il linguaggio C: scopi e principali caratteristiche.

Organizzazione della memoria di un calcolatore, indirizzi, parole, puntatori. Codifica binaria ed esadecimale. Tipi di dato (interi, floating point, double precision, caratteri, stringhe).

La struttura di un programma C, l'inclusione degli header, dichiarazione delle variabili; le librerie.

Tipi di dato elementari in linguaggio C: interi, floating point, double, small int, long, char. Puntatori; aritmetica sui puntatori. Array e matrici e loro rappresentazione in memoria. Strutture dati complesse: liste, alberi, grafi; la definizione di strutture.

Strutture di controllo: "if... else...", "while...", "do... while...", "for...". Operatore di assegnazione, operatori aritmetici in C in forma estesa e compatta.

Funzioni: funzioni di libreria e funzioni definite dall'utente. Passaggio di parametri per valore e per indirizzo alle funzioni. Funzioni ricorsive.

Funzioni di input/output: "printf", "scanf".

Funzioni per la gestione diretta della memoria: "malloc", "free", "sizeof".

Funzioni sulle stringhe: "sprintf" e "strlen".

3. Algoritmi fondamentali

Strutture dati (array, matrici, liste, pile, code, code di priorità, alberi, grafi).

Algoritmi di ordinamento: insertion sort, selection sort, bubble sort, quick sort; algoritmi ottimi: heap sort, merge sort. Complessità di un algoritmo, la notazione "O grande", analisi della complessità degli algoritmi di ordinamento.

Algoritmi su grafi. Definizioni principali: grafo, grafo orientato, grafo connesso; sottografo, sottografo indotto; passeggiata, cammino, ciclo; cut-set; lista, albero, spanning tree di un grafo. Strutture dati per la rappresentazione di grafi mediante un calcolatore: liste di adiacenza e matrici di adiacenza. Algoritmi di visita di un grafo: visita in ampiezza (BFS), visita in profondità (DFS). Problemi di cammino minimo, l'algoritmo di Dijkstra. Alberi di copertura minima, l'algoritmo di Prim. Alberi binari di ricerca.

Cenni sulla teoria della complessità: problema astratto, problema concreto, problema di ottimizzazione, problema in forma decisionale. La classe dei problemi polinomiali (P). Problemi e linguaggi formali. La classe dei problemi NP, algoritmi di verifica; la classe dei problemi NP completi, principali proprietà caratteristiche.