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

cucinare ricetta aggiungere olio

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

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

Programmazione

problema

⇓ algoritmo

⇓ programma

 fasi

 progettare un algoritmo

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?

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

Correttezza

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

 metodi formali

 metodi empirici

 inaffidabilità dei programmi

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

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

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

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

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

Rappresentazione

 linguaggi per rappresentare algoritmi:

 naturale

 pseudocodice

 flow chart

 linguaggio di programmazione

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

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