Algoritmi e Programmazione Strutturata: concetti base e risoluzione problemi

Algoritmi e Programmazione Strutturata

Prof R. Bresolin a.s. 2013 - 20142

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Programmazione

Calcolatore Elettronico È uno strumento in grado di eseguire insiemi di azioni elementari; Le azioni vengono eseguite su oggetti (dati) per produrre altri oggetti (risultati); L'esecuzione di azioni viene richiesta all'elaboratore attraverso opportune direttive, dette istruzioni.

Definizione di Programmazione

È l'attività con cui si predispone l'elaboratore ad eseguire un particolare insieme di azioni su particolari dati, allo scopo di risolvere un certo problema.3

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Problemi Risolvibili con un Calcolatore

I problemi che possono essere risolti con un calcolatore possono essere di varia natura per esempio:

• Sommare due numeri interi;
• Trovare il percorso ottimale per una consegna;
• Stabilire se una parola viene alfabeticamente prima o dopo di un'altra;
• Dati a e b, risolvere l'equazione ax +b = 0
• Dati due numeri trovare il maggiore;
• Gestire acquisti e prestiti dei libri di una biblioteca;
• Trovare gli zeri di una funzione f(x);4

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Risoluzione dei Problemi

Affinché un problema sia risolvibile, in generale è necessario che la sua definizione sia chiara e completa. Non tutti i problemi sono risolvibili attraverso l'uso del calcolatore. In particolare esistono classi di problemi per le quali la soluzione automatica non è proponibile. Ad esempio:

• Se il problema presenta infinite soluzioni;
• Se per il problema non stato trovato un metodo risolutivo ( Problema di Fermat: trovare tutti gli N per cui l'equazione xN+yN=zN sia soddisfatta);
• Non esiste un metodo risolutivo automatizzabile.5

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Analisi e Programmazione

Tramite un elaboratore si possono risolvere problemi di varia natura. Il problema deve essere formulato in modo opportuno, perché sia possibile utilizzare un calcolatore per la sua soluzione

• Per analisi e programmazione si intende l'insieme delle attività preliminari atte a risolvere problemi utilizzando un elaboratore, dalla formulazione del problema fino alla predisposizione dell'elaboratore.
• Scopo dell'analisi: definire un algoritmo
• Scopo della programmazione: definire un programma6

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Risoluzione di Problemi

• Algoritmo: elenco finito di istruzioni, che specificano le operazioni, eseguendo le quali si risolve una classe di problemi;
• Programma: ricetta che traduce l'algoritmo ed è direttamente comprensibile, pertanto eseguibile, da parte di un elaboratore;
• Linguaggio di programmazione: linguaggio rigoroso che permette la formalizzazione di un algoritmo in un programma (es: C, C++, Basic, Java ... );7

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Fasi di Risoluzione del Problema

Problema

Analisi

Algoritmo

Relazioni tra Problema, Analisi, Algoritmo, Programmazione, Programma, Dati ed Elaborazione

PROGRAMMAZIONE Programma ELABORAZIONE Dati Risultati8

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Proprietà di un Algoritmo

• Affinchè un elenco di istruzioni possa essere considerato un algoritmo devono essere soddisfatti tali requisiti:
• Finitezza: ogni algoritmo deve essere finito, cioè ogni singola istruzione deve poter essere eseguita in tempo finito e numero finito di volte;
• Eseguibilità: ogni istruzione dell'algoritmo deve essere eseguibile da parte dell'esecutore dell'algoritmo;
• Non ambiguità: devono ssere definiti in modo univoco i passi successivi da seguire; devono essere evitati paradossi, contraddizioni ed ambiguità; il significato di ogni istruzione deve essere univoco per chiunque esegua l'algoritmo.9

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Proprietà di un Algoritmo: Linguaggi

Gli algoritmi devono essere formalizzati per mezzo di appositi linguaggi, dotati di strutture linguistiche che garantiscano precisione e sintesi; I linguaggi naturali non soddisfano tali requisiti, infatti sono ambigui: la stessa parola può assumere significati diversi in contesti differenti (pesca è un frutto e uno sport) . sono ridondanti: lo stesso concetto può essere espresso in modi diversi, ad esempio "somma 2 a 3", "calcola 2+3", "esegui l'addizione tra 2 e " 3"10

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Proprietà di un Algoritmo: Procedimento di Calcolo

Un algoritmo può essere visto come un procedimento di calcolo (non necessariamente calcolo aritmetico), dal punto di vista sistemistico l'algoritmo a partire da un input fornisce un output. Dati input Risultati (output) Algoritmo x f(x)11

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Rappresentazione di Algoritmi: Diagrammi di Flusso

E' un formalismo che consente di rappresentare graficamente gli algoritmi.

• un diagramma a blocchi descrive le azioni da eseguire e il loro ordine di esecuzione.
• Il diagramma a blocchi o flowchart è una rappresentazione grafica che descrive il flusso delle operazioni da eseguire per realizzare la trasformazione, definita nell'algoritmo, dai dati iniziali ai risultati.
• Ogni istruzione dell'algoritmo viene rappresentata all'interno di un blocco elementare, la cui forma grafica è determinata dal tipo di istruzione.
• I blocchi sono collegati tra loro da linee di flusso, munite di frecce, che indicano il susseguirsi di azioni elementari.12

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Rappresentazione di Algoritmi: Blocchi Principali

Blocchi Principali e Loro Funzioni

Inizio/Fine Scrivi/Leggi Blocco terminatore: inizio o fine Blocco di input/output Elaborazione/Assegnazione Vero Condizione (test) Falso Blocco di assegnazione o elaborazione (calcoli) Connettore Blocco condizionale o decisionale, esecuzione alternativa13

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Rappresentazione di Algoritmi: Diagrammi di Flusso Dettagli

1 leggi/scrivi X Blocco di lettura/scrittura vero falso C Blocco di controllo

• ciascun blocco di azione o di lettura/scrittura ha una sola freccia entrante ed una sola freccia uscente.
• ciascun blocco di controllo ha una sola freccia entrante e due frecce uscenti.
• ciascuna freccia entra in un blocco oppure si innesta in un'altra freccia.
• ciascun blocco è raggiungibile dal blocco iniziale.
• il blocco finale è raggiungibile da qualsiasi altro blocco.14

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Algoritmi: Esempio Non Numerico (Torta)

• Problema: preparare una torta ( ?!? )
• Dato iniziale: numero di persone
• Dato finale: la torta pronta
• Esecutore: in grado di comprendere i diagrammi a blocchi e di effettuare le operazioni elementari di cucina (mescolare, cuocere ... )15

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Diagramma di Flusso per Preparare una Torta

inizio leggi num_persone metti 2*num_persone uova in una pentola aggiungi 100*num_persone grammi di farina cuoci per 20 minuti mescolando ogni 30 secondi sforna e metti in tavola fine16

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Algoritmi: Esempio Numerico (Numero Primo)

• Problema: verificare se un numero è primo
• Dato iniziale: il numero intero positivo
• Dato finale: "primo" o "non primo"
• Esecutore: in grado di comprendere i diagrammi a blocchi e di effettuare le operazioni matematica compresa il resto della divisione intera resto(n,d)17

inizio Algoritmi e programmazione strutturata Prof. R. Bregolin a.s. 2013-14

Diagramma di Flusso per Verificare un Numero Primo

leggi numero divisore + 1 divisore -- divisore + 1 FALSO r +resto (numero, divisore) r = 0 - VERO FALSO divisore = numero VERO 1 scrivi "non primo scrivi "primo" fine18

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Verifica: Esempio di Esecuzione

numero divisore r input output passo1 15 - - 15 - passo2 1 - - passo3 2 - - - passo4 - - - - passo5 3 - - - passo6 - - passo7 - - - - non primo - - -19

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Algoritmi: Esempio Non Numerico (Videoregistratore)

• Problema: insegnare ad un bambino ad utilizzare un videoregistratore per registrare un film.
• Dati iniziali: Canale, Ora e Minuto di inizio film
• Dato finale: Film registrato su videocassetta
• Esecutore (bambino) è in grado di comprendere i diagrammi a blocchi e di eseguire alcune operazioni elementari (prendere una videocassetta, comprend significato dei tasti del videoregistratore ... ) 000 0020

inizio Algoritmi e leggi C, O, M programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Diagramma di Flusso per Registrare un Film

inserisci la videocassetta nel registratore il nastro è all'inizio? FALSO riavvolgi il nastro VERO seleziona il canale C guarda l'orologio FALSO il nastro è all'inizio? VERO 1 1 aspetta 5 minuti fai partire la registrazione fine21

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Diagrammi a Blocchi: Pregi e Difetti

• Pregi: - Semplicità
• Possibilità di seguire facilmente il flusso di esecuzione
• Difetti:
• Per algoritmi complessi si ottiene una struttura molto complessa e risulta difficile decifrare il procedimento seguito nella risoluzione22

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Algoritmi: Esempio Numerico (Ipotenusa)

• Problema: date le misure dei cateti trovare la misura dell'ipotenusa in un triangolo rettangolo
• Dati iniziali: misura del cateto1 e del cateto2
• Dato finale: misura dell'ipotenusa
• Esecutore: in grado di comprendere i diagrammi a blocchi e di effettuare le operazioni sui numeri reali compreso elevamento al quadrato - quadrato(x) - calcolo della radice quadrata - radice(x) -23

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Diagramma di Flusso per Calcolare l'Ipotenusa

inizio leggi cateto 1 leggi cateto2 ipotenusa +-radice(quadrato(cateto 1)+quadrato(cateto2)) scrivi ipotenusa fine24

Algoritmi e programmazione strutturata Prof. R. Bresolin a.s. 2013-14

Programmazione Strutturata

La programmazione strutturata favorisce la descrizione di algoritmi facilmente documentabili e comprensibili. I blocchi di un diagramma a blocchi strutturato sono collegati secondo i seguenti schemi di flusso:

• Schema di sequenza - più schemi di flusso sono eseguiti in sequenza.
• Schema di selezione - un blocco di controllo subordina l'esecuzione di due possibili schemi di flusso al verificarsi di una condizione.
• Schema di iterazione - si itera l'esecuzione di un dato schema di flusso.