02 algo programmi

Click here to load reader

download 02 algo programmi

of 67

  • date post

    12-Nov-2014
  • Category

    Technology

  • view

    579
  • download

    0

Embed Size (px)

description

 

Transcript of 02 algo programmi

  • 1. Fondamenti di Informatica Algoritmi e Programmi La catena di programmazione1

2. Algoritmo2 3. Algoritmo (definizione informale) Una sequenza finita di operazioni elementari, comprensibili da un esecutore,che portano alla realizzazione di un compito Esecutore: chiunque sappia comprendere la specifica delle operazioni (tipicamente uno strumento automatico) Compito: la risoluzione di un problema3 4. Osservazioni sulla definizione Mette in luce gli aspetti progettuali e realizzativi dellattivit dellinformatico Dice che si pu svolgere attivit informatica senza usare un computer Esempio: progettare/applicare regole precise per le operazioni aritmetiche su numeri grandi usando solo carta e matita Il computer (calcolatore elettronico) solo un esecutore potente, che gestisce quantit di informazioni altrimenti intrattabili 4 5. Un esempio di algoritmo (scritto in linguaggio naturale) Ricetta di cucina: 1. Metti un ricciolo di burro in una padella 2. Metti la padella sul fuoco 3. Aspetta due minuti 4. Rompi un uovo ( un'istruzione semplice?) 5. Versa il tuorlo e lalbume nella padella 6. Aggiungi un pizzico di sale (quanto sale?) 7. Quando lalbume si rappreso, togli dal fuoco5 6. Altri esempi Istruzioni di montaggio di un elettrodomestico(comprensibile?) Uso di un terminale Bancomat Calcolo del massimo comune divisore di due numeri naturali essenziale che un algoritmo sia comprensibile al suo esecutore6 7. Problemi ed esecutori Ogni algoritmo risolve una sola classe di problemi Ogni algoritmo dipende strettamente dallesecutore per cui formalizzato Operazioni elementari per un esecutore possono non esserlo affatto per un altro7 8. Revisione: definizione di algoritmo Dati un problema specifico e un esecutore specifico, un algoritmo : una successione finita di passi elementari tale che: i passi sono effettuabili senza ambiguit da parte dellesecutore la successione risolve il problema dato Nel nostro caso: algoritmi sequenziali i passi si eseguono in ordine, uno alla volta 8 9. Risoluzione automatica di problemi Le attitudini umane si adattano tipicamente a individuare metodi per ottenere le soluzioni I calcolatori elettronici, invece, eccellono in: Ripetizione di un grande numero di operazioni di per s relativamente semplici Capacit di trattare grandi quantit di dati senza errori (trattare: leggere, scrivere, trasferire) Rapidit e precisione nellesecuzione Ma non trovano da soli i metodi di soluzione 9 10. I mattoni elementari di un algoritmo Azione Sequenza Decisione Ripetizione (detta anche Iterazione) 11. Sequence matters! 1. 2. 3. 4. 5. 6.Alzarsi dal letto Togliersi il pigiama Fare la doccia Vestirsi Fare colazione Prendere il bus per andare a scuolaNB: I passi sono eseguiti in sequenza e l'ordine delle istruzioni essenziale per la correttezza dell'algoritmo! (2,3 3,2 ... !!!)11 12. Oltre la sequenza 1. 2. 3. 4. 5. 6.Alzarsi dal letto Togliersi il pigiama Fare la doccia Vestirsi Fare colazione Se piove alloraControllo del flusso se allora prendere ombrello1. Prendere il bus per andare a scuola12 13. Controllo del flusso (se allora altrimenti ) 1. 2. 3. 4. 5. 6.Alzarsi dal letto Togliersi il pigiama Fare la doccia Vestirsi Fare colazione Se piove allora prendere la macchina altrimenti prendere il bus 13 14. Controllo del flusso (ciclo fintantoch") 1. 2. 3. 4. 5. 6.Alzarsi dal letto Togliersi il pigiama Fare la doccia Vestirsi Fare colazione Fintantoch piove restare in casa1. Prendere il bus per andare a scuola14 15. Esempio: gestione biblioteca Libri disposti sugli scaffali Ogni libro si trova in una precisa posizione definita con due coordinate s,p scaffale e posizione nello scaffale La biblioteca ha uno schedario, ordinato per autore/i e titolo Ogni scheda contiene, nellordine: cognome e nome dellautore titolo del libro, editore e data di pubblicazione numero dello scaffale in cui si trova (s) numero dordine della posizione nello scaffale (p) 15 16. Esempio di scheda Autore/i:Atzeni, Paolo Ceri, Stefano Fraternali, Piero Paraboschi, Stefano Torlone, Riccardo Titolo: Basi di dati Scaffale: 35 Posizione: 2116 17. Formulazione del problema e dell'algoritmo 1. 2. Problema: deciso un libro da richiedere, prelevarlo Algoritmo: Preleva il libro desiderato Se un passo dell'algoritmo non direttamente comprensibile ed eseguibile dall'esecutore, occorre dettagliarlo a sua volta (mediante un algoritmo pi preciso!) Tale procedimento incrementale si dice top-down o anche procedimento per raffinamenti successivi (stepwise refinement)17 18. Un algoritmo per il prelievo 1. 2. 3. 4. 5.Ricerca la scheda del libro richiesto Segnati scaffale e posizione s,p Cerca lo scaffale s Preleva il libro alla posizione p Compila la scheda prestito18 19. Il sotto-algoritmo di ricerca 1. Prendi la prima scheda 2. Titolo e autore/i sono quelli cercati?2.1 Se s, la ricerca termina con successo, altrimenti prendi la scheda successiva 2.2 Se le schede sono esaurite il libro cercato non esiste (in biblioteca) altrimenti ricomincia dal punto 2.Che cosa succede se lautore cercato Manzoni, A. o, peggio, Zola, E. ? 19 20. Un sotto-algoritmo migliore 1. Esamina la scheda centrale dello schedario 2. Se la scheda centrale corrisponde al libro cercato, termina 3. Se non corrisponde, prosegui nello stesso modo nella met superiore (inferiore) dello schedario se il libro cercato segue (precede) quello indicato sulla scheda Lalgoritmo incompleto Esiste unaltra condizione di terminazione: quando il libro non esiste 20 21. Revisione del passo 2 2. Se la scheda centrale corrisponde al libro cercato oppure se la parte di schedario da consultare vuota, terminaLibro trovatoLibro inesistente21 22. Qualit degli algoritmi Criteri di valutazione di un algoritmo: Correttezza: capacit di pervenire alla soluzione in tutti i casi significativi possibili Efficienza: propriet strettamente correlata al tempo di esecuzione e alla memoria occupataLa correttezza imprescindibile Lefficienza auspicabile22 23. Il problema e la soluzione Prima di formulare la soluzione occorre capire esattamente il problema Non serve risolvere il problema sbagliato In questo corso supporremo che il problema sia ben noto e chiaramente formulato e ci concentreremo prevalentemente sulla formulazione delle soluzioni Spesso, in pratica, pi difficile capire esattamente la natura del problema che non trovare una soluzione Analisi dei requisiti in Ingegneria del Software Analisi dei requisiti da svolgere in QUESTO corso Il testo del compito scritto Le specifiche del progetto23 24. Dal problema alla soluzione Specifiche dei requisiti: descrizione precisa e corretta dei requisiti (verificabilit) cosa? Progetto: procedimento con cui si individua la soluzione come? Soluzione: un algoritmo24 25. Esempio: prodotto di interi positivi Specifiche: ideare un algoritmo che calcoli il prodotto di due numeri positivi usando solo loperazione di somma Soluzione Dati 2 addendi (X,Y) la loro somma (Z)Operazioni Leggi il primo numero (X) da terminale Leggi il secondo numero (Y) da terminale Somma a 0 il valore di X per Y volte Scrivi il risultato (Z) sul terminale25 26. I due pilastri della soluzione Che dati devo usare (ricordare, modificare, leggere, scrivere)? X, Y, Z, 0 Quali operazioni devo svolgere e in che sequenza? Leggi, somma, scrivi 27. Prodotto per somme ripetute di due interi positivi 1 2 3 4 5 6 7Leggi X Leggi Y SP = 0 NS = Y SP = SP + X NS = NS - 1 NS uguale a 0 ? Se no: torna al passo 5 8 Z = SP 9 Scrivi Z Procedimento sequenziale Non ambiguo Formulazione generale, non dipende dal valore dei numeri letti Prevede tutti i casi ? SP e NS sono VARIABILI, introdotte come ausilio alla scrittura dellalgoritmo SP: SommaParziale NS: NumeroSomme27 28. Sintassi & Semantica 29. Sintassi & Semantica dei programmi Determina la corretta interpretazione delle istruzioni di un algoritmo Sintassi [come si scrivono: forma e struttura] = Semantica [come si interpretano: significato] Interpretazione: calcola il valore dellespressione e assegna al contenuto della variabile il valore calcolato Si perde il valore precedentemente contenuto nella variabile NON la semantica delle equazioni !! SP=SP+X NS=NS-1se e solo se X=0 una contraddizione valore di NS Il simbolo = denota lASSEGNAMENTO di valore Le istruzioni di assegnamento modificano i valori 29 30. Evoluzione dello stato Durante la computazione evolve lo stato del sistema stato: il complesso dei valori contenuti nelle variabili Ad ogni ripetizione delle istruzioni 5-6 levoluzione dello stato pu essere tale da cambiare lesito dellistruzione 7 Se questo non accadesse mai? Lalgoritmo entrerebbe in un ciclo infinito (loop) Tuttavia in questo caso impossibile: Si ricevono in ingresso due interi positivi Continuando a decrementare Y inevitabilmente il valore arriva a zero Se ricevesse in ingresso un valore Y 0 allora A = A + 1 altrimenti A = 0 Diagrammi di flusso Detti anche flow chart o schemi a blocchi leggi inizioBlocco di input dati fineassegnamento test?test ? scriviBlocchi di inizio/fine dellesecuzione Blocco esecutivo Blocco condizionale Blocco di output dati Flusso di controllo delle operazioni 35 36. Flow charts 37. Somma dei primi N numeri naturali INIZIOLeggi: NN: il numero di interi da sommareS=0S: la somma parzialeI=1 S=S+II: un "contatore"I=I+1 SIQuante volte viene eseguita?NOI>N "condizione di uscita"Scrivi: "la somma " S FINE37 38. Prodotto per somme ripetute di due interi positivi INIZIOLeggi: X Leggi: Y SP = 0 NS = YnoNS > 0 ? s SP = SP + X NS = NS - 1 Z = SP Scrivi: Z FINE1. 2. 3. 4. 5. 6. 7.Legenda:Leggi X NS: numero somme Leggi Y SP: somma parziale SP = 0 NS = Y SP = SP + X NS = NS - 1 NS uguale a 0 ? Se no: torna al passo 5 8. Z = SP 9. Scrivi Z Notare la diversa posizione del test Che differenza produce? 39. Prodotto per somme ripetute Variante: lalgoritmo non calcola il pro