Problemi, algoritmi, linguaggi

Luca Bortolussi

Dipartimento di Matematica e Informatica

Università degli studi di Trieste

Programmazione

Elaboratore

elettronico

RISULTATI

OUTPUT

DATI

INPUT

La programmazione è l'attività con cui si predispone

l'elaboratore ad eseguire un particolare insieme di

azioni su una particolare tipologia di dati, allo scopo

di risolvere un problema.

Alcune domande …

Quali istruzioni esegue (cosa può fare) un

elaboratore?

Quali problemi può risolvere un elaboratore?

Esistono problemi che un elaboratore non può risolvere?

Che ruolo ha il linguaggio di programmazione?

Quali problemi?

I problemi affrontati dalle applicazioni informatiche sono di

natura molto varia:

- Trovare il maggiore fra due numeri

- Dato un elenco di nomi e numeri di telefono, trovare il

numero di una data persona

- Dati a e b, risolvere l'equazione ax+b=0

- Stabilire se una parola precede alfabeticamente un'altra

- Ordinare un elenco di nomi

- Creare, modificare e alterare suoni

- Analizzare, riconoscere e modificare immagini

- Supportare operazioni di commercio elettronico

Problemi e modelli

Modello

F = m × a

ft ttre 12 14tf 13 15

Costruzione

modello

Ricerca della

soluzione

Interpretazione

della soluzione

Mondo Reale

Come affrontare un problema

PROBLEMA

Descrizione Risoluzione

La descrizione del problema non indica direttamente

(in genere) un modo per ottenere il risultato voluto

specifica di un

problemaspecifica del processo

di risoluzione#

Risoluzione di un problema

•Descrizione del problema in modo preciso.

•Individuazione di un opportuno metodo

risolutivo (algoritmo).

Il metodo di risoluzione trasforma i dati iniziali nei corrispondenti risultati finali, che costituiscono una soluzione del problema.

L’algoritmo: essenza dell’informatica

Un algoritmo è una sequenza finita di passi

elementari che descrive come risolvere in un tempo

finito un problema.

Esempi di algoritmi:

- Istruzioni di montaggio

- Preparazione del caffè

- Prelievo bancomat

- Preparazione di un ricetta

- Calcolo del massimo comun divisore tra due interi

Più precisamente …

Dati inizialiDati finali (soluzione)

ALGORITMO

Si definisce algoritmo una sequenza di azioni

elementari che consenta di trasformare i dati

iniziali nei risultati finali attraverso un numero

finito di passi, elementari e non ambigui.

Questa sequenza di passi è valida per un insieme

di dati iniziali ben definito e può essere eseguita

da un opportuno esecutore.

Azioni elementari

Finitezza: l’azione deve concludersi in un tempo

finito

Osservabilità: l’azione deve avere un effetto

osservabile, cioè deve produrre qualcosa

Riproducibilità: a partire dallo stesso stato

iniziale, la stessa azione deve produrre sempre lo

stesso risultato

Non-ambiguità: ogni azione deve essere

univocamente interpretabile dall'esecutore

Dipendono dall’esecutore! In generale devono avere le seguenti proprietà:

Proprietà fondamentali degli algoritmi

Correttezza

L’algoritmo perviene sempre alla

soluzione del compito cui è preposto.

Efficienza

L’algoritmo perviene alla soluzione del

problema usando la minor quantità

possibile di risorse fisiche, quali:

- tempo di esecuzione, memoria, …

Ricapitolando

Dunque, un algoritmo deve essere:

- applicabile a qualsiasi insieme di dati di ingresso

appartenenti al dominio di definizione

dell’algoritmo;

- costituito da operazioni appartenenti ad un

determinato insieme di operazioni

fondamentali;

- costituito da regole non ambigue, cioè

interpretabili in modo univoco qualunque sia

l’esecutore (persona o “macchina”) che le legge.

Esempio: prendere l’automobile

1. Aprire l’auto

2. Aprire la portiera

3. Sedersi al posto di guida

4. Schiacciare la frizione

5. Avviare il motore

6. Inserire la prima marcia

7. Rilasciare “delicatamente” la frizione per partire

NB: I passi sono eseguiti in sequenza e l'ordine delle istruzioni è essenziale per la correttezza dell'algoritmo!

Esempio: gestione biblioteca

•I libri sono disposti sugli scaffali

•La posizione di ogni libro è fissa ed è individuata da due coordinate:

-Scaffale (i.e. numero dello scaffale)

-Posizione nello scaffale

•La biblioteca è dotata di uno schedario (ordinato per autore/i e titolo). Ogni scheda contiene, nell’ordine:

-cognome e nome dell’autore

-titolo del libro

-data di pubblicazione

-numero dello scaffale in cui si trova

-posizione attribuita al libro nello scaffale.

Esempio di scheda

Autore/i: Sciuto, DonatellaBuonanno, GiacomoMari, Luca

Titolo: Introduzione ai Sistemi Informatici,III Edizione, 2005

Scaffale: 22Posizione:11

Formulazione dell’algoritmo

1. Decidi il libro da richiedere

2. Preleva il libro richiesto

Se un passo non è direttamente comprensibile ed eseguibile dall’esecutore, occorre dettagliarlo a sua volta mediante un ulteriore algoritmo.

Questo modo incrementale di procedere si dice top-down o anche procedimento per raffinamenti successivi.

Un algoritmo per il prelievo

1. Decidi il libro da richiedere

2. Cerca la scheda del libro richiesto

3. Segnati numero scaffale e posizione

4. Cerca lo scaffale indicato

5. Accedi alla posizione indicata e preleva il libro

6. Scrivi i tuoi dati sulla "scheda prestito"

Il sotto-algoritmo di ricerca

1. Prendi la prima scheda.

2. Esamina se titolo e autore/i sono quelli cercati.In caso positivo la ricerca termina con successo, altrimenti passa alla scheda successiva e ripeti.

3. Se esaurisci le schede il libro cercato non esiste.

Cosa succede se l’autore cercato è“Zoran Zuzzurellone”?

Una algoritmo di ricerca più furbo

1. Esamina la scheda centrale dello schedario.

2. Se la scheda centrale corrisponde al libro cercato allora termina.

3. Altrimenti, prosegui allo stesso modo nella metà superiore o inferiore dello schedario a seconda che il libro cercato segua o preceda quello indicato sulla scheda.

L’algoritmo è incompleto!

C’è un’altra condizione di terminazione: quando il libro non esiste.

Perfezionando il passo 2

1. Esamina la scheda centrale dello schedario.

2. Se la scheda centrale corrisponde al libro cercato oppure se la parte di schedario da consultare è vuota allora termina.

3. Altrimenti, prosegui allo stesso modo nella metà superiore o inferiore dello schedario a seconda che il libro cercato segua o preceda quello indicato sulla scheda.

Libro inesistenteLibro trovato

Perché più furbo?

Perché il secondo modo di cercare la scheda è più furbo del primo?

Si fa meno fatica!!!

Se abbiamo 15 schede e cerchiamo l’ultima:-Il primo metodo ne esamina 15-Il secondo metodo ne esamina 4

(la 8, la 12, la 14 e la 15)

In generale, se abbiamo n schede-Il primo metodo ne esamina al più n-Il secondo metodo ne esamina al più log(n)

(per n = 1010, log(n) = 36)

Complessità! Perché così importante?

Le risorse che abbiamo sono finite

Universo protone

40 miliardi di anni luce

10-13 cm

Abbiamo non più di 10125

protoni nell’Universo

(limite alla memoria disponibile!)

Complessità! Perché così importante?

Se assumiamo come unità temporale il temponecessario alla luce a viaggiare per 10-13 cm eassumiamo che l’universo sia nato 10 miliardi di annifa, il numero di unita’ di tempo trascorse finora èminore o uguale a

1042

(limite al tempo disponibile!)

Le risorse che abbiamo sono finite

Che speranze abbiamo?

• snail 0.0006 mil./h

• man 4 mil./h

• US auto 55 mil./h

• Jet 600 mil./h

• Supersonic jet 1200 mil./h

• man (pencil) 0.2/sec

• man (abacus) 1/sec

• calculator 4/sec

• computer 200.000/sec

• fast computer 2M/sec

L’informatica progredisce molto più rapidamente di altre tecnologie!!!

Grid problemcalcolare il numero di cammini da start a finish

start

finish

Il problema è difficile

•non ci sono metodi noti per calcolare il numero di cammini (in a reasonable amount of time)

possiamo comunque generare dei cammini random eusare un teorema di statistica che ci dice che la stimamigliore e’ data dalla media dei reciproci delle probabilita’osservate

•otteniamo una stima enorme: (1.6 ± 0.3) 1024

Non li possiamo enumerare tutti!!!elencando un milione di cammini al secondo, ci vorrebbero

più di 10 miliardi di anni!!!

The need for a theory!

Abbiamo bisogno di una teoria degli algoritmi che:

• Fornisca algoritmi per risolvere problemi

• Classifichi la complessità dei problemi in:

• Trattabili

• Intrattabili

• Non risolvibili

Problemi intrattabili e non risolubili

Problema intrattabile Protein structure prediction: data la struttura primaria di una proteina, predire la sua struttura terziaria

(teoria della complessità, NP-completezza)

Problema non risolubileTerminazione: dire se un dato algoritmo termina oppure no.

(teoria della computabilità, Macchine di Turing)

Risoluzione di problemi col computer

Un programma non è altro che la formulazione

testuale di un algoritmo in un linguaggio di

programmazione.

Ogni elaboratore è una macchina in grado di

eseguire azioni elementari su dati.

L'esecuzione delle azioni elementari è richiesta

all'elaboratore tramite comandi chiamati istruzioni.

Le istruzioni sono espresse attraverso frasi di un

opportuno linguaggio di programmazione.

Algoritmi e Programmi

Algoritmo: sequenza finita di passi che risolve

in un tempo finito un problema.

Codifica: fase di scrittura di un algoritmo attraverso

un insieme ordinato di frasi (“istruzioni”), scritte in

un determinato linguaggio di programmazione,

che specificano le azioni da compiere.

Programma: Testo scritto in

accordo alla sintassi e alla

semantica di un linguaggio

di programmazione

Algoritmi e Programmi

PROBLEMA ALGORITMO PROGRAMMA

metodo risolutivo

linguaggio di programmazione

Concludendo

•L’informatica si occupa di risolvere problemi ben definiti, spesso legati alla modellazione della realtà.

•Dato un problema, la sua soluzione è fornita mediante un algoritmo, che specifica i passi elementari che devono essere compiuti per giungere ad una soluzione.

•Non tutti i problemi ammettono una soluzione algoritmica, non tutti i problemi risolubili ammettono una soluzione trattabile.

•Dato un algoritmo, esso può venire eseguito da un computer previa codifica in un opportuno linguaggio di programmazione.