descrizione di come si deve eseguire un lavoro o risolvere un problema

Algoritmi

Paolo Bison

Fondamenti di Informatica 1 A.A. 2004/05 Universit`a di Padova

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.1/17

Algoritmo

 descrizione di come si deve eseguire un lavoro o risolvere un problema

 sequenza di passi/istruzioni

 Muh.ammad ibn M¯us¯a al- Khuw¯arizm¯ı

matematico arabo autore di

Al-jabr w’al muq¯abala

 procedimento di calcolo

 esistono anche in altri contesti:

processo algoritmo passo tipico

montare un istruzioni incolla mobile di montaggio A su B

cucinare ricetta aggiungere olio

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.2/17

Esecuzione

 esecutore

uomo/calcolatore

 funzionalità dell’esecutore:

 capire il significato di ogni passo

 eseguire l’operazione corrispondente

 descrizione

uomo linguaggio naturale calcolatore programma in un

linguaggio di programmazione

Programmazione

problema

⇓ algoritmo

⇓ programma

 fasi

 progettare un algoritmo

 esprimerlo in un linguaggio di programmazione

Progettazione

 Dato un problema come si progetta un algoritmo che lo risolva ?

 NON ESISTE un algoritmo per progettare algoritmi

 attività intellettuale

 metodologie e linguaggi

 prevedere tutti i possibili eventi che potrebbero verificarsi durante l’esecuzione

• distruzione del vettore Arianne

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.5/17

Computabilità

 Ci sono problemi per i quali non esistono algoritmi?

 halting problem

 Dato un problema, come possiamo sapere se esiste un algoritmo che lo risolve?

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.6/17

Correttezza

 Dato un algoritmo, come possiamo essere sicuri che è corretto?

 metodi formali

 metodi empirici

 inaffidabilità dei programmi

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.7/17

Complessità

 dato un algoritmo

quali sono le risorse necessarie per eseguirlo ? in quanto tempo ?

 se ci sono più algoritmi per un dato problema, qual’è il

“migliore”?

 esistono problemi per i quali il miglior algoritmo richiede tante risorse da rendere impossibile l’elaborazione?

 crittografia

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.8/17

Algoritmo

 un insieme di passi/istruzioni che definiscono una sequenza di operazioni mediante le quali si risolve un problema (o una classe di problemi)

 proprietà

finitezza

numero dei passi finito ed eseguito un numero finito di volte

determinatezza

istruzioni definite senza ambiguità in modo tale da garantire sempre gli stessi risultati a parità di condizioni

realizzabilit`a

istruzioni devono essere conosciute all’esecutore che sa come eseguirle

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.9/17

Top Down

 approccio metodologico alla progettazione di algoritmi per affinamenti successivi

 divide et impera

 fasi

 dato un problema

 lo si scompone in sottoproblemi

 ogni sottoproblema è scomposto in ulteriori sottoproblemi

 così via finché ogni sotto- problema è sufficientemente dettagliato e preciso da poter essere eseguito.

P

P

P

P

P

P

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.10/17

Algoritmo del tè - I

 algoritmo principale:

 fai bollire dell’acqua

 metti il tè nella tazza

 versa l’acqua

 si noti:

 azioni(istruzioni) e oggetti (dati)

 ambiguità

Algoritmo del tè - II

 affinamento primo sottoproblema

 fai bollire l’acqua:

 riempi il bollitore

 accendi il fuoco

 attendi che bolla

 spegni il fuoco

Bottom Up

 approccio opposto al top down

 dato un certo insieme di algoritmi/istruzioni elementari si cerca di aggregarli in maniera da costruire

l’algoritmo per la soluzione del problema o di suoi sottoproblemi

 combinazione delle due metodologie

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.13/17

Algoritmo del tè - III

Se esecutore capace di strofinare si può accendere il fuoco con il seguente algoritmo:

 strofina due legnetti

 continua finché il fuoco appare

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.14/17

Rappresentazione

 linguaggi per rappresentare algoritmi:

 naturale

 pseudocodice

 flow chart

 linguaggio di programmazione

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.15/17

Elementi di un linguaggio

 sintassi

l’insieme della regole relative ai procedimenti tramite i quali le unità sintattiche si combinano in espressioni linguistiche

 semantica

relazione fra le espressioni linguistiche e il mondo cui si riferiscono

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.16/17

Do it yourself

 Dato un esecutore capace solamente di disegnare e contare, sviluppare un algoritmo per calcolare la somma di due numeri interi

Algoritmi, Paolo Bison, A.A. 2004-05, 2004-10-04 – p.17/17