Introduzione agli algoritmi

Introduzione agli algoritmi

Paolo Bison

Fondamenti di Informatica Ingegneria Meccanica

Università di Padova A.A. 2008/09

Introduzione agli algoritmi, Paolo Bison, FI08, 2008-09-29 – p.1

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

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

 indipendenti dal linguaggio in cui sono espressi

 potenza espressiva del linguaggio

Introduzione agli algoritmi, Paolo Bison, FI08, 2008-09-29 – p.3

Programmazione

problema

⇓

algoritmo

⇓

programma

 fasi

 progettare un algoritmo

 esprimerlo in un linguaggio di programmazione

(programma)

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

Introduzione agli algoritmi, Paolo Bison, FI08, 2008-09-29 – p.5

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?

Correttezza

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

 metodi formali

 metodi empirici

 inaffidabilità dei programmi

Introduzione agli algoritmi, Paolo Bison, FI08, 2008-09-29 – p.7

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

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

Introduzione agli algoritmi, Paolo Bison, FI08, 2008-09-29 – p.9

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 sottoproblema è sufficientemente dettagliato e pre- ciso da poter essere eseguito.

P

P

P

P

P

P

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à

Introduzione agli algoritmi, Paolo Bison, FI08, 2008-09-29 – p.11

Algoritmo del tè - II

 affinamento primo sottoproblema

 fai bollire l’acqua:

 riempi il bollitore

 accendi il fuoco

 attendi che bolla

 spegni il fuoco

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

Introduzione agli algoritmi, Paolo Bison, FI08, 2008-09-29 – p.13

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

Rappresentazione

 linguaggi per rappresentare algoritmi:

 naturale

 pseudocodice

 flow chart

 linguaggio di programmazione

Introduzione agli algoritmi, Paolo Bison, FI08, 2008-09-29 – p.15

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

Differenza positiva di due numeri N e M

 linguaggio naturale se N maggiore M sottrai M da N altrimenti sottrai N da M

 pseudo codice if N > _M then

sottrai M da N

else

sottrai N da M

 flowchart

T

F

N − M M − N

 linguaggio C if (N > M) R=N-M;

else R=M-N;

Introduzione agli algoritmi, Paolo Bison, FI08, 2008-09-29 – p.17

Do it yourself

 Dato un esecutore capace solamente di disegnare e

contare, sviluppare un algoritmo per calcolare la somma di

due numeri interi