Laboratorio di Laboratorio di Algoritmi e Strutture Dati Algoritmi e Strutture Dati classi A/B classi A/B

(1)

Laboratorio di Laboratorio di

Algoritmi e Strutture Dati Algoritmi e Strutture Dati

classi A/B classi A/B

Moreno Marzolla

Dipartimento di Informatica—Scienza e Ingegneria (DISI) Università di Bologna https://www.moreno.marzolla.name/

(2)

Lab. Algoritmi e Strutture Dati 2

(3)

Presentiamoci

● Docente del laboratorio

– Moreno Marzolla moreno.marzolla@unibo.it

– https://www.moreno.marzolla.name/

● Tutor

– Luca Deluigi

– Nicolas Farabegoli

– Gabriele Graffieti

● Orario delle lezioni

– Giovedì 15:00–18:00 (cl. B prof. Maniezzo)

– Venerdì 09:00–12:00 (cl. A prof. Margara)

● Ricevimento

– Da concordare via mail

(4)

Sito web

● https://www.moreno.marzolla.name/teaching/LabASD

– Avvisi

– Esercizi e materiale vario

(5)

Lab. Algoritmi e Strutture Dati 5 / 20

Nota

● Per comunicare con me al di fuori delle lezioni usare la mail

● Regole da rispettare:

– Specificare l'oggetto (subject) delle mail

– Usare sempre e solo il proprio indirizzo istituzionale

– Indicare il proprio nome, cognome e n. di matricola

– Specificare il corso a cui vi riferite

● In questo anno accademico tango 5 corsi differenti

● Indicare se fate parte del gruppo A oppure B, dato che le esercitazioni potrebbero essere diverse

– Non aspettatevi una risposta immediata

● La mail è un mezzo di comunicazione asincrono

(6)

● Testo adottato

– Thomas H. Cormen, Charles E.

Leiserson, Ronald L. Rivest, Clifford Stein, Introduzione agli algoritmi e

strutture dati 3/ed, 2010, McGraw-Hill, ISBN: 9788838665158

● Testi di consultazione

– Alan Bertossi, Alberto Montresor, Algoritmi e strutture di dati Terza Edizione, 2014, Città Studi, ISBN:

9788825173956

– Camil Demetrescu, Irene Finocchi,

Giuseppe F. Italiano, Algoritmi e strutture dati 2/ed, 2008, McGraw-Hill, ISBN:

9788838664687

Bibliografia

(7)

Prerequisiti

● Sapere scrivere in autonomia

programmi in C di media complessità

– Tipi di dato; scalari, array, strutture, puntatori

– Espressioni, costrutti base

– Gestione della memoria (malloc/free)

– Funzioni, ricorsione

● Aver almeno seguito il corso di programmazione

– Meglio se anche superato l'esame

● Testo consigliatissimo:

– Brian W. Kernighan and Dennis M. Ritchie, The C Programming Language, Second Edition Prentice Hall, Inc., 1988. ISBN 0- 13-110362-8 (paperback), 0-13-110370-9

(8)

Scopo del corso

● Contenuto

– Una panoramica di problemi noti e loro soluzioni

– Elenco di algoritmi e strutture dati standard

– Come valutare l'efficienza di un algoritmo

● Metodo

– Come risolvere problemi nuovi, applicando soluzioni note o inventando varianti alle soluzioni note

(9)

Scopo del corso

(10)

Perché un modulo di laboratorio?

(11)

Modalità d'esame

https://www.moreno.marzolla.name/teaching/LabASD/#esami

● Progetto da svolgere individualmente

– 1-2 problemi algoritmici da risolvere in C

– Livello di difficoltà simile agli esercizi visti in laboratorio

– Assegnati a fine del modulo

– Consegna tramite Virtuale

– Una volta consegnato, il progetto non può essere modificato fino alla correzione

● Un progetto sufficiente consente l'accesso alla prova scritta di tutti gli appelli successivi (anche di altri anni accademici)

– Obbligatoria la consegna almeno 10gg lavorativi prima dell'appello cui si vuole partecipare

● Il progetto non ha voto: il voto finale è quello dello scritto

(12)

(13)

Non copiate

● Tutti i progetti vengono esaminati manualmente

– Anche se funzionanti

– In caso di codice incomprensibile/inefficiente verranno rimandati al mittente per una revisione

● La similarità tra progetti consegnati sarà valutata in modo automatico

– Con un ulteriore controllo manuale successivo

● Indice di similarità troppo alto → progetto rifiutato

(14)

Come funziona il laboratorio

● Verranno proposti alcuni esercizi

– In molti casi viene fornito uno "scheletro" da completare

● All'inizio (primi 20 min.) illustrerò gli esercizi, eventualmente con qualche richiamo di teoria

● Poi, assieme ai tutor daremo supporto allo svolgimento degli esercizi

● La pratica è fondamentale: lo studio degli algoritmi non è uno sport da seguire come “spettatori”

– Verranno messe a disposizione tutte le soluzioni

– Prima di sbirciare la soluzione cercate di risolvere gli esercizi da soli (anche con l'aiuto di colleghi/e, del docente e dei tutor)

(15)

Cosa fare e cosa non fare

● Fare

– Seguire le lezioni

– Studiare anche sul libro

– Partecipare al laboratorio

– Provare a svolgere gli esercizi

– Chiedere aiuto in caso di difficoltà

– Venire a ricevimento in caso di difficoltà

● Non fare

– Studiare solo sui lucidi

– Saltare i laboratori

– Guardare subito le soluzioni

– Non leggere i messaggi di errore del compilatore

– Ignorare i warning del compilatore

– Dichiarare un programma

"corretto" solo perché

compila e supera qualche test

(16)

Il vero significato

della complessità degli algoritmi

(17)

Sottovettore di valore massimo

● Consideriamo un vettore V[1..n] di n ≥ 1 valori reali arbitrari

● Vogliamo individuare un sottovettore V[i..j] non vuoto di V la somma dei cui elementi sia massima

● Soluzione "di forza bruta": O(n³)

● Esiste una soluzione O(n)

– stay tuned...

3 -5 10 2 -3 1 4 -8 7 -6 -1

(18)

Soluzione di “forza bruta” O(n³)

real SommaMax1( real V[1..n] ) real smax ← V[1];

for integer i ← 1 to n do

for integer j ← i to n do real s ← 0;

for integer k ← i to j do s ← s + V[k];

endfor

if (s > smax) then smax ← s;

endif endfor endfor

return smax;

(19)

L'efficienza conta!

● Confrontiamo la soluzione O(n³) con una soluzione O(n) (che vedremo più avanti) su due sistemi molto diversi

● Algoritmo O(n³)

– Ubuntu Linux 18.04

– CPU: Intel i7 @ 3.6GHz

– 16 GB RAM

– Linguaggio C

● Algoritmo O(n)

– Commodore 64 (anno 1982)

– CPU: MOS 6502 @ 1MHz

– 64 KB RAM

– Commodore BASIC

(20)

0.00 100.00 200.00 300.00 400.00 500.00 600.00 700.00 800.00 900.00 1,000.00

Sottovettore di somma massima

Tempi di esecuzione in secondi

Intel i7 O(n^3) C64 O(n)