Dati e Algoritmi [PDF]

Zitiervorschau

Dati e Algoritmi 1 Nozioni Fondamentali

Fabio Vandin

25 Settembre 2017

1

Problema Computazionale Un problema computazionale ⇧ `e una relazione tra un insieme I di istanze (input) ed un insieme S di soluzioni (output), ovvero: ⇧✓I ⇥S con l’ulteriore vincolo che per ogni istanza i 2 I esista almeno una soluzione s 2 S tale che (i, s) 2 ⇧.

N.B. ⇧ `e un insieme di coppie (istanza,soluzione), sottoinsieme di tutte le possibili coppie. Data la coppia (i, s) 2 ⇧, diciamo che s `e soluzione di i.

2

Esempi Somma di Interi • I=coppie di interi; S= interi

• ⇧ associa ad ogni coppia di interi (istanza) la loro somma

(soluzione)

• ((1, 9), 10) 2 ⇧; ((23, 6), 29) 2 ⇧; ((13, 45), 31) 62 ⇧

Ordinamento di Sequenze di Interi • I=sequenze di interi; S= sequenze interi ordinate "

• ⇧ associa ad ogni sequenza di interi (istanza) la sequenza

ordinata costituita dagli stessi interi, eventualmente ripetuti (soluzione) ? (< 7, 1, 7, 3, 3, 5 >, < 1, 3, 3, 5, 7, 7 >) 2 ⇧ ? (< 13, 4, 25, 17 >, < 11, 27, 33, 68 >) 2 ⇧ ?

• (< 43, 16, 75, 2 >, < 2, 16, 43, 75 >) 2 ⇧

3

Esempi (2) Ordinamento di Sequenze di Interi (ver.2) • I=sequenze di interi; S= permutazioni

• ⇧ associa ad ogni sequenza di interi (istanza) la permutazione

che la ordina in senso crescente (soluzione)

? (< 7, 1, 7, 3, 3, 5 >, < 2, 4, 5, 6, 1, 3 >) 2 ⇧ ? (< 7, 1, 7, 3, 3, 5 >, < 2, 5, 4, 6, 1, 3 >) 2 ⇧ ? (< 13, 4, 25, 17 >, < 1, 2, 4, 3 >) 2 ⇧ ?

• (< 43, 16, 75, 2 >, < 4, 2, 1, 3 >) 2 ⇧

Osservazioni • un’istanza pu` o avere pi` u soluzioni (ad es., ordinamento ver. 2) • una soluzione pu` o essere associata a pi` u istanze diverse (ad

es., somma di interi)

4

Algoritmo e Modello di Calcolo Definizione Un algoritmo `e una procedura computazionale ben definita che transforma un dato input in un output eseguendo una sequenza finita di passi elementari. L’algoritmo fa riferimento a un modello di calcolo (o modello di computazione), ovvero un’astrazione di computer che definisce l’insieme di passi elementari. Il modello di calcolo pi` u utilizzato `e il modello RAM1 (Random Access Machine)

• input, output, dati intermedi (e programma): in memoria • passi elementari sono operazioni primitive quali:

assegnamento, operazioni logiche, operazioni aritmetiche, indicizzazione di array, restituzione di un valore da parte di un metodo, ecc.

1

Diverso da Random Access Memory!

5

Un algoritmo A risolve un problema computazionale ⇧ ✓ I ⇥ S se e solo se: 1 2 3

A riceve come input istanze i 2 I

A produce come output soluzioni s 2 S

Dato un input i 2 I, A produce come output s 2 S tale che (i, s) 2 ⇧

In altre parole: A calcola una funzione che mappa ogni istanza in una soluzione di tale istanza. (Pi` u soluzioni? A ne calcola una.) Per semplicit`a e facilit`a di analisi, un algoritmo viene di solito descritto tramite pseudocodice, ovvero un mix di costrutti di linguaggi di programmazione ad alto livello e linguaggio naturale.

6

Esempio di Pseudocodice

Algoritmo Transpose(A) Input: matrice A n ⇥ n Output: matrice AT (trasposta) i 0; j 1; while i < n 1 do scambia A[i, j] e A[j, i]; if j = n 1 then i i + 1; j else j j + 1; return A

i + 1;

7