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