Introduzione

Il corso di Algoritmi & Strutture Dati (IN110) valido per l'ottenimento di 9CFU nel settore scientifico disciplinare INF/01 (Informatica) è tenuto ad anni alterni dai proff. Roberto Maieli e Marco Liverani. Il corso è finalizzato a fornire una competenza di base sull'informatica e sulla programmazione dei calcolatori elettronici in particolare. Non sono richiesti prerequisiti di tipo informatico, ma esclusivamente delle competenze elementari di Algebra e Logica Matematica.

Il corso si suddivide in tre parti principali: la prima è una introduzione sintetica e molto generale sui calcolatori elettronici e sugli aspetti da tenere in considerazione per affrontare la soluzione di un problema con l'ausilio di un computer. 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 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 elementari di ottimizzazione combinatoria.

È disponibile il programma ufficiale del corso per l'anno accademico 2018/2019.

Programma indicativo del corso

1. Problemi ed 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 di un calcolatore elettronico, distinzione del ruolo e del compito affidato a ciascuna delle componenti che sono presenti su un computer. Sistemi operativi, introduzione all'uso del sistema operativo UNIX/Linux (comandi della shell).

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, 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 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.