• Non ci sono risultati.

Algoritmi (9 CFU) Anno Accademico Prof. V. Cutello Algoritmi 1

N/A
N/A
Protected

Academic year: 2022

Condividi "Algoritmi (9 CFU) Anno Accademico Prof. V. Cutello Algoritmi 1"

Copied!
24
0
0

Testo completo

(1)

Algoritmi (9 CFU)

Anno Accademico 2009-10

(2)

Libro di Testo

 Introduction to Algorithms, 2/e

 T.H. Cormen, C.E. Leiserson, R.L.

Rivest, C. Stein

(3)

Prerequisiti

42 CFU del I anno (minimo)

Programmazione 2 (e quindi Progr. 1)

Fondamenti di Informatica,

Matematica Discreta,

Elementi di Analisi Matematica e Geometria

Totale 51 CFU

(4)

Contenuti di Massima

Il corso offre un'introduzione rigorosa allo studio degli algoritmi e delle strutture dati ponendo particolare enfasi sulle relative metodologie generali di progettazione e le tecniche di analisi.

Più specificamente, saranno discussi:

fondamenti matematici per la stima della complessità asintotica degli algoritmi;

problema dell'ordinamento e limiti

(5)

Contenuti di Massima

strutture dati elementari, alberi, alberi binari di ricerca

heap e heapsort

problema dell’hashing e algoritmi correlati

Alberi RB e statistiche d’ordine dinamiche

Programmazione Dinamica

Algoritmi Golosi

Grafi e algoritmi elementari su grafi

(6)

Esami

 esame scritto +

 colloquio orale per chi passa lo scritto

in cui si parlerà di come avete fatto bene allo scritto (si spera)

(7)

Contenuti del corso:

Introduzione

L’Algoritmica.

Analisi e progettazione di Algoritmi

Revisione di alcuni algoritmi di ordinamento fondamentali

Insertion sort

Bubble sort

Merge sort

Capitoli 1-2

(8)

Crescita asintotica di funzioni

Tempi di esecuzione di algoritmi.

Metodologie per confrontare funzioni:

O ≈ ≤

Ω ≈ ≥

Θ ≈ =

o ≈ <

ω ≈ >

Capitolo 3

(9)

Equazioni di ricorrenza

In molti casi il tempo di esecuzione di un algoritmo (ricorsivo) può essere

descritto da equazioni di ricorrenza.

Es. il Teorema Master per risolvere tutte le equazioni del tipo

T(n)=aT(n/b)+f(n)

Capitolo 4.

(10)

Algoritmi randomizzati

 Analisi probabilistica di base e algoritmi randomizzati

 Concetti di base di probabilità

 Esempi particolari

 Capitolo 5 e Appendice C

(11)

Heap e Heapsort

 Struttura dati per l’ordinamento

 Ne vedremo le operazioni e

studieremo l’algoritmo di ordinamento

 Cap. 6

(12)

Quicksort

 Algoritmo randomizzato

 Proprietà ed analisi delle performance

 Capitolo 7

(13)

Ordinamento in tempo lineare

 Vedremo in quali condizioni si può ordinare molto velocemente

 Introdurremo diversi tipi di algoritmi lineari

 Capitolo 8

(14)

Mediane e Statistiche d’ordine

 Casi particolari dell’ordinamento

Trovare minimo e massimo di una lista

Trovare il 10, 23, 97 o k-esimo

 Si può fare velocemente?

 Capitolo 9

(15)

Hashing

 Strutture dati veloci che supportano operazioni di

Search, Insert e Delete

 Capitolo 11

(16)

Alberi Binari di Ricerca

 Definizione della struttura dati e delle operazioni su di essa

 Complessità per tutte le operazioni

 Costruzione casuale ed algoritmo di ordinamento associato

 Capitolo 12

(17)

Alberi Rosso-neri

 O Rossazzurri/Bianco-neri/Nerazzurri se preferite

 Proprietà

 Operazioni su di essi e complessità

 Capitolo 13

(18)

Aumentare le strutture dati

 Vedremo come estendere alcune

strutture dati (Alberi Rosso-neri) per migliorare l’efficienza di alcuni

algoritmi

 Statistiche d’ordine dinamiche

 Capitolo 14

(19)

Programmazione Dinamica

 Tecnica per la risoluzione di problemi (complessi)

 Tipicamente problemi di ottimizzazione

 Ricombinazione della soluzione di sotto-problemi

 Capitolo 15

(20)

Algoritmi Greedy (golosi)

 Tecnica per prendere decisioni

durante la risoluzione di problemi (complessi)

 Tipicamente problemi di ottimizzazione

 Ad ogni passo faccio la scelta migliore possibile. Trovo la soluzione migliore possibile?

(21)

Grafi

 Definizione di grafo

 Rappresentazioni di un grafo

 Visite di un grafo

 Ordinamento topologico

 Componenti fortemente connesse

 Capitolo 22 e appendice B (fatta a Matematica Discreta)

(22)

Basta così

 Ma …. Vi lascio con due problemi (più o meno facili/difficili)

 Se conoscete le soluzioni non ditelo ai vostri colleghi. Fate sudare i loro neuroni che gli fa bene.

(23)

5 in 7

 Per ordinare 2 numeri, a e b, faccio un solo confronto.

 Per ordinare 3 numeri, a,b e c, di confronti ne devo fare al più 3.

 Classico problema (knuth)

 Riuscite ad ordinare 5 numeri facendo sempre al più 7 confronti ?

(24)

12 monete

Giochino molto conosciuto

12 monete d’oro di cui una falsa

Non si sa se la falsa pesa più o meno di quelle d’oro

A disposizione una bilancia (quella classica con i due piatti)

Trovare la falsa con al più 3 pesate.

Riferimenti

Documenti correlati

In pratica, modellando la cartina dell’Italia come un grafo orientato pesato G=(V, E), dove ciascun vertice rappresenta una città, ogni arco (u,v) rappresenta una strada diretta da

Infine, se la lista è doppiamente puntata, il puntatore prev della testa della lista punta all’elemento in coda

lista.h deve includere la definizione della struttura dati a puntatori (lista semplice non circolare) e i soli prototipi delle funzioni implementate in lista.c. Dunque, per

Un albero binario è una tipo astratto di dato che o è vuoto (cioè ha un insieme vuoto di nodi) o è formato da un nodo A (detto la radice) e da due sottoalberi, che sono a loro

Riversamento dei dati contenuti nell’heap nell’albero binario di ricerca utilizzando una visita lineare dell’array. Stampare i dati contenuti nell’albero binario di

La classe di memoria automatica è relativa a quegli oggetti locali ad un blocco (funzione o programma) che viene liberata non appena si raggiunge la fine di quel blocco. La classe

Scrivere in linguaggio C un programma che implementi le operazioni precedenti indipendentemente dal fatto che la struttura dati di appoggio sia un grafo rappresentato con liste

Insertion Sort, Merge Sort, Heap Sort, Quick Sort, Pigeonhole Sort Come si può rendere un qualunque algoritmo