1

1

Elementi di informaticaElementi di informatica

Problemi, algoritmi e programmi

2

L’ELABORATORE ELETTRONICO

Il calcolatore elettronico è uno strumento in grado di

• eseguire insiemi di azioni elementari• le azioni vengono eseguite su oggetti

(dati) per produrre produrre altri oggetti (risultati)

• l’esecuzione di azioni viene richiesta all’elaboratore attraverso frasi scritte in qualche linguaggio (istruzioni)

2

3

PROGRAMMAZIONE

L’attività con cui si predispone l’elaboratore a eseguire un particolare insieme di azioni su particolari dati, allo scopo di risolvere un problema

I N P U TD A T I

ElaboratoreElettronico

O U T P U TR I S U L T A T I

4

agente di calcolo

Uno degli scopi fondamentali dell’informatica è:

la risoluzione di problemila risoluzione di problemi

problema = compito che si vuole far risolvere automaticamente al calcolatore

ProblemProblem solvingsolving

3

5

ProblemProblem solvingsolving ((contcont.).)

I problemi che siamo interessati a risolvere sono di natura molto varia:

Trovare il maggiore tra due numeriDato un elenco di nomi e numeri di telefono, trovare il numero di una data personaDati a e b, risolvere l’equazione ax+b=0Stabilire se una parola precede alfabeticamente un’altraPrenotare aerei, treni, hotel, …Ordinare un elenco di nomiEcc.

6

ProblemProblem solvingsolving ((contcont.).)

input

acquisire i dati

ElaborazioneElaborazione output

presentare i risultati

4

7

Esempio: sommaEsempio: somma

n1, n2 totaletotale

=n1 + n2

totale=

n1 + n2

8

RISOLUZIONE DI PROBLEMI

La descrizione del problema non fornisce (in generale) un metodo per risolverlo.

– Affinché un problema sia risolvibile è però necessario che la sua definizione sia chiara e completa

Non tutti i problemi sono risolvibili attraverso l’uso del calcolatore. Esistono classi di problemi per le quali la soluzione automatica non è proponibile.

Ad esempio:– se il problema presenta infinite soluzioni– per alcuni dei problemi non è stato trovato un metodo risolutivo– per alcuni problemi è stato dimostrato che non esiste un metodo

risolutivo automatizzabile

5

9

RISOLUZIONE DI PROBLEMIRISOLUZIONE DI PROBLEMI

La risoluzione di un problema è il processo che, dato un problema e individuato un opportuno metodo risolutivo, trasforma i dati iniziali nei corrispondenti risultati finali.

Affinché la risoluzione di un problema possa essere realizzata attraverso l’uso del calcolatore, tale processo deve poter essere definito come sequenza di azioni elementari.

10

Attività per risolvere un problemaAttività per risolvere un problema

1. Comprendere il problema2. Definire un procedimento risolutivo (algoritmo)3. Implementare l’algoritmo in un linguaggio di

programmazione4. Prova5. Documentazione 6. Manutenzione

6

11

Comprendere il problemaComprendere il problema

• Focalizzare gli obiettivi

• Evidenziarele regolei dati espliciti ed impliciti

• Eliminare i dettagli inutili ed ambigui

12

Attività per risolvere un problemaAttività per risolvere un problema

1. Comprendere il problema2. Definire un procedimento risolutivo (algoritmo)3. Implementare l’algoritmo in un linguaggio di

programmazione4. Prova5. Documentazione 6. Manutenzione

7

13

AlgoritmoAlgoritmoDescrizione rigorosa Un algoritmo è una sequenza finita di

azioni che risolve in un tempo finito una classe di problemi.

L'esecuzione delle azioni nell'ordine specificato dall'algoritmo consente di ottenere, a partire dai dati di ingresso, i risultati che risolvono il problema di ingresso

RISULTATI

ESECUTOREuna macchina astrattacapace di eseguire le azionispecificate dall’algoritmo.Esecutore

MetodoRisolutivo(algoritmo )

DATI

14

ConsiderazioniConsiderazioni

1. Suddivisione in sottoproblemi

2. Precisione dell’algoritmo cresce al diminuire delle capacità dell’agente di calcolo

8

15

Caratteristiche di un algoritmoCaratteristiche di un algoritmo

Eseguibilità: ogni azione dev’essere essereeseguibile dall’esecutore in un tempo finito

Non-ambiguità: ogni azione deve essereunivocamente interpretabile dall'esecutore

Finitezza : il numero totale di azioni da eseguire, per ogni insieme di dati di ingresso, deve essere finito

16

Caratteristiche di un algoritmoCaratteristiche di un algoritmo

Quindi, l’algoritmo deve: essere applicabile a qualsiasi insieme di dati di ingresso appartenenti al dominio di definizione dell’algoritmo

essere costituito da operazioni appartenenti ad undeterminato insieme di operazioni fondamentali

essere costituito da regole non ambigue, cioèinterpretabili in modo univoco qualunque sial’esecutore (persona o “macchina”) che le legge

9

17

Struttura in passi elementariStruttura in passi elementari

Tutte le operazioni specificate dall’algoritmo devono essere eseguibili dall’agente (operazioni elementari) … altrimenti è necessario scomporre il problema troppo complesso in sotto problemi più semplici

18

Esempio: l’area di una campanaEsempio: l’area di una campana

r

h2 b

Sottoproblema 1

A1 = ½ π r2

Sottoproblema 2

A2 = b h2

Sottoproblema 3

A3 = b h1 +

½ ( ½ (B-b) h1) +

½ ( ½ (B-b) h1)

Area della campana =

A1 + A2 +A3

h1B

r=b/2

h2 b

h1B

b

10

19

Esempio: gestione bibliotecaEsempio: gestione biblioteca

Libri disposti sugli scaffaliLa posizione di ogni libro è fissa ed è individuata da due coordinate:

• 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• Numero dello scaffale• Posizione attribuita al libro nello scaffale

20

Esempio di schedaEsempio di scheda

Autore: Manzoni

Titolo: I promessi Sposi

Scaffale: 33

Posizione: 13

Autore: Manzoni

Titolo: I promessi Sposi

Scaffale: 33

Posizione: 13

11

21

ProblemaProblema

Trovare un libro??

22

Formulazione dell’algoritmoFormulazione dell’algoritmo

1. Cerca la scheda del libro nello schedario

2. Segnati numero scaffale e posizione

3. Cerca lo scaffale indicato

4. Accedi alla posizione indicata e preleva il libro

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

raffinamenti successivi

12

23

Primo sottoPrimo sotto--algoritmo di ricercaalgoritmo di ricerca

1. Prendi la prima scheda dello schedario

2. Se titolo e autore/i sono quelli cercati, la ricerca termina con successo, altrimenti passa alla scheda successiva

3. Continua di scheda in scheda finché non trovi quella cercata. Se vengono esaurite le schede, il libro cercato non esiste. Devi cercare il libro in un’altra biblioteca.

24

Cosa succede se l’autore cercato è Cosa succede se l’autore cercato è Zuzzurellone?Zuzzurellone?

13

25

Autore: Manzoni

Titolo:Scaffale: 33

Posizione: 13

Autore: Manzoni

Titolo:Scaffale: 33

Posizione: 13

Cosa succede se l’autore cercato è Cosa succede se l’autore cercato è Zuzzurellone?Zuzzurellone?

Autore: Alighieri

Titolo:La Divina Commedia

Scaffale: 5

Posizione: 10

Autore: Alighieri

Titolo:La Divina Commedia

Scaffale: 5

Posizione: 10

Autore:Zuzzurellone

Titolo:Scaffale: 33

Posizione: 13

Autore: VergaTitolo:Scaffale: 33

Posizione: 13

Autore: PetrarcaTitolo:Scaffale: 33

Posizione: 13

Autore: ManzoniTitolo: I promessi SposiScaffale: 33Posizione: 13

Autore: LeopardiTitolo:

Scaffale: 33

Posizione: 13

Autore: Alighieri

Titolo:La Divina Commedia

Scaffale: 5

Posizione: 10

Autore: Alighieri

Titolo:La Divina Commedia

Scaffale: 5

Posizione: 10

schedario

Autore: Zuzzurellone

Titolo:Scaffale: 33

Posizione: 13

Autore: GoldoniTitolo:Scaffale: 33

Posizione: 13

Autore: Petrarca

Titolo:Scaffale: 33

Posizione: 13

Autore: Manzoni

Titolo:

Scaffale: 33

Posizione: 13

Autore: Leopardi

Titolo:

Scaffale: 33Posizione: 13

Autore: Goldoni

Titolo:Scaffale: 33

Posizione: 13schedario

26

Secondo sottoSecondo sotto--algoritmo di ricercaalgoritmo di ricerca

1. Esamina la scheda centrale dello schedario

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

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

14

27

Cosa succede ora se l’autore cercato Cosa succede ora se l’autore cercato è Zuzzurellone?è Zuzzurellone?

28

Autore: VergaTitolo:Scaffale: 33

Posizione: 13

Autore:Zuzzurellone

Titolo:

Scaffale: 44

Posizione: 12

Cosa succede ora se l’autore cercato Cosa succede ora se l’autore cercato è Zuzzurellone?è Zuzzurellone?

Autore: Alighieri

Titolo:La Divina Commedia

Scaffale: 5

Posizione: 10

Autore: Alighieri

Titolo:La Divina Commedia

Scaffale: 5

Posizione: 10

Autore: PetrarcaTitolo:Scaffale: 33

Posizione: 14

Autore: Manzoni

Titolo: I promessi Sposi

Scaffale: 33

Posizione: 13Autore: LeopardiTitolo:

Scaffale: 33

Posizione: 13

Autore: GoldoniTitolo:Scaffale: 33

Posizione: 13schedario

15

29

Secondo sottoSecondo sotto--algoritmo di ricerca: algoritmo di ricerca: erroreerrore

1. Esamina la scheda centrale dello schedario

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

3. In caso contrario, 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

30

Revisione del passo 2Revisione del passo 2

Se la scheda centrale corrisponde al libro cercato

Se la scheda centrale corrisponde al libro cercato

Se la parte dello schedario da consultare è vuota

Se la parte dello schedario da consultare è vuota

TerminazioneTerminazione

oppure

Libro trovato Libro inesistente

16

31

Qualità degli algoritmiQualità degli algoritmi

Due qualità fondamentali di un algoritmo:

• Correttezzal’algoritmo permette effettivamente di risolvere il problema

• Efficienzal’esecuzione dell’algoritmo richiede un uso limitato di risorseun algoritmo è tanto più efficiente quanto meno risorse richiede per la sua esecuzione. Una risorsa importante è il tempo di esecuzione

32

Esempio: gestione bibliotecaEsempio: gestione biblioteca

• Entrambi gli algoritmi di ricerca sono corretti

• Il secondo algoritmo è più efficiente del primo

17

33

Altre qualità degli algoritmiAltre qualità degli algoritmi

• leggibilitàessere facilmente comprensibile

• modificabilitàessere facilmente modificabile, a fronte di (piccole) modifiche nelle specifiche del problema risolto dall’algoritmo

• parametricità

• riusabilità

34

EsempiEsempi

Soluzione dell’equazione ax+b=0– leggi i valori di a e b– calcola calcola -b – dividi quello che hai ottenuto per a e chiama x il risultato– stampa xCalcolo del massimo di un insieme–Scegli un elemento come massimo provvisorio max –Per ogni elemento i dell’insieme: se i>max eleggi i comenuovo massimo provvisorio max–Il risultato è maxNOTANOTAI passi sono eseguiti in sequenza e l’ordine delle istruzioni è essenziale per la correttezza dell’algoritmo

18

35

…… riassumendoriassumendo

AlgoritmoAlgoritmo

Sequenza di azioni che trasforma i dati iniziali in un numero finito di passi, elementari e non ambigui, per giungere al risultato finale

Questa sequenza di azioni può essere eseguita da un agente di calcolo

36

Attività per risolvere un problemaAttività per risolvere un problema

1. Comprendere il problema2. Definire un procedimento risolutivo (algoritmo)3. Implementare l’algoritmo in un linguaggio di

programmazione4. Prova5. Documentazione 6. Manutenzione

19

37

Implementazione di un algoritmoImplementazione di un algoritmo

Algoritmo deve essere trascritto in un linguaggio

Linguaggi

Linguaggi artificialiusati in informatica: linguaggi di programmazione

Linguaggi naturaliusato dagli uomini per comunicare

complessi ambigui

38

ALGORITMI E ALGORITMI E ALGORITMI E ALGORITMI E PROGRAMMIPROGRAMMI

Ogni elaboratore è una macchina in grado di eseguire azioni elementari su oggetti detti DATI.

• L’esecuzione delle azioni è richiesta all’elaboratore tramite comandi elementari chiamati ISTRUZIONI espresse attraverso un opportuno formalismo: il LINGUAGGIO di PROGRAMMAZIONE.

• La formulazione testuale di un algoritmo in un linguaggio comprensibile a un elaboratore è detta programma.

Un programma è la formulazione testuale, in uncerto linguaggio di programmazione, di un algoritmoche risolve un dato problema.

20

39

Alcuni linguaggi di programmazione Alcuni linguaggi di programmazione “famosi”“famosi”

• FORTRAN: metà degli anni ’50(FORmula TRANslator)

• COBOL: metà degli anni ’50 (Common Business-Oriented Language)

• Pascal: inizio degli anni ’70 (nome dal matematico francese Blaise Pascal che fu il primo ad ideare una macchina calcolatrice: la Pascalina)

• C: inizio degli anni ’70suo antenato: linguaggio B

• Prolog: inizio degli anni ’70(PROgramming in LOGic)

• …

Linguaggi ad alto

livello

40

Il linguaggio CIl linguaggio C

Il linguaggio C è stato sviluppato intorno al 1972, nei Bell Laboratories AT&T americani, da DennisRitchie

E’ nato come linguaggio di sviluppo del Sistema Operativo UNIX

21

41

Sintassi e semanticaSintassi e semantica

Linguaggio

Sintassiinsieme di regole che consentono di costruire correttamente le frasi del linguaggio

Semanticadisciplina che studia il significato delle parole e delle frasi

FORMA NON CORRETTAFORMA CORRETTALIVELLO

l’albero è un animaleil gatto è un animalesemanticoho andato a scuolasono andato a scuolasintattico

42

ProgrammaProgramma

Testo (i.e. sequenza di istruzioni) scritto in accordo alla sintassi e semantica di un linguaggio di programmazione

22

43

Linguaggio macchinaLinguaggio macchina

Un calcolatore non è in grado di eseguire direttamente programmi scritti in linguaggi ad alto livello

un calcolatore è in grado di eseguire direttamente soloprogrammi scritti nel proprio linguaggio macchina

0110001000100101110100100101010100101001010001001110100100110101

………

44

Linguaggio macchina (Linguaggio macchina (contcont.).)

Il linguaggio macchina è

linguaggio di programmazione comprensibile direttamente dal calcolatore

molto elementare e primitivo: sequenza di cifre binarie. Ad esempio, una possibile istruzione potrebbe essere 0010110000101100

è difficile da comprendere per un essere umano

specifico di un calcolatore: calcolatori di tipo diverso hanno linguaggi macchina differenti

23

45

TraduzioneTraduzione

Per rendere un programma (scritto in un linguaggio ad alto livello) eseguibile da un calcolatore è necessario tradurre il programma in un programma equivalentescritto nel linguaggio macchina del calcolatore

La traduzione può avvenire in due modi:

compilazione

interpretazione

46

CompilazioneCompilazioneun programma scritto in un linguaggio di programmazione ad alto livello viene trasformato in un programma in linguaggio macchinae poi può essere eseguito più volte senza dover tradurre nuovamente il programma

Programma scritto in C

0110001000100101110100100101010100101001010001001110100100110101

………

Compilazione

controllo della correttezza sintattica

correttezza sintattica

correttezza semantica

Nota:

codicesorgente

codiceeseguibile

ERRORI• sintassi (compilatore)

• d’esecuzione

(divisione per 0)

• logici

24

47

InterpretazioneInterpretazione

Traduzione riga per riga:

ciascuna istruzione del programma scritto in un linguaggio di programmazione ad alto livello viene trasformata in istruzioni del linguaggio macchina ed eseguita

48

Compilazione & interpretazioneCompilazione & interpretazione

Una analogia con la traduzione tra linguaggi diversi

la compilazione è analoga alla traduzione di un libro

l’interpretazione è analoga alla traduzione simultanea

25

49

50