Lezioni di Informatica 3 - 03 - Algoritmi e programmi PDF

I.I.S. “Marzotto-Luzzatti” - Valdagno Dipartimento di Informatica Prof. Riccardo Crosato A.S. 2023/2024 Algoritmi + Strutture Dati = Programmi  Concetto di algoritmo Algoritmo: insieme fini...

I.I.S. “Marzotto-Luzzatti” - Valdagno Dipartimento di Informatica Prof. Riccardo Crosato A.S. 2023/2024 Algoritmi + Strutture Dati = Programmi  Concetto di algoritmo Algoritmo: insieme finito e ordinato di passi eseguibili e non ambigui che giunge certamente a terminazione insieme ordinato cioè deve avere un determinato ordine di esecuzione → esiste una prima istruzione ed è sempre possibile stabilire qual è la prossima istruzione passi eseguibili cioè che possono essere portati a termine passi non ambigui cioè durante l’esecuzione lo stato raggiunto permette di stabilire univocamente e completamente le azioni da svolgere (l’algoritmo si dice deterministico) Lezioni di Informatica classe III - Prof. Riccardo Crosato 2  Problemi e algoritmi Un algoritmo risolve un problema trasformando dati iniziali in dati finali Lezioni di Informatica classe III - Prof. Riccardo Crosato 3  Rappresentazione degli algoritmi Rappresentazione di un algoritmo → utilizza una serie di primitive Primitive: componenti fondamentali definite precisamente al fine di eliminare problemi di ambiguità – ogni primitiva ha: – una sintassi → rappresentazione simbolica – una semantica → significato della primitiva Linguaggio di programmazione: insieme di primitive e di regole (che spiegano come possono essere combinate assieme le primitive) Istruzioni: comandi impartiti ad un esecutore utilizzando un linguaggio di programmazione A seconda di dove si collocano le primitive rispetto alle primitive costituite dalle istruzioni macchina (cioè quelle che la macchina è in grado di eseguire) l’insieme di primitive si dive di “livello più alto” - una primitiva di livello più alto è cioè descritta in termini di primitive di livello più basso Lezioni di Informatica classe III - Prof. Riccardo Crosato 4  Pseudocodice Per descrivere un algoritmo, anziché usare da subito un linguaggio di programmazione formale, si usa un linguaggio meno formale e più intuitivo chiamato pseudocodice – permette di rappresentare l’algoritmo indipendentemente dal linguaggio di programmazione che si utilizzerà – consiste di notazioni concise e coerenti per rappresentare le strutture sintattiche e semantiche più usate 1. INIZIO 2. Scrivi "Inserisci un un numero naturale n" 3. Leggi n 4. Se n % 2 = 0 (se il resto della divisione per 2 è 0): 4.1 Scrivi "Il numero è pari" 5. Altrimenti: 5.1 Scrivi "Il numero è dispari" 6. FINE Lezioni di Informatica classe III - Prof. Riccardo Crosato 5  Diagrammi di flusso Diagramma di flusso (in inglese flow chart, anche detto diagramma a bloccchi): rappresentazione grafica a blocchi, di un algoritmo Primo strumento di progettazione ideato agli albori dell’informatica (dagli anni 1950) Utili per visualizzare l’algoritmo ma possono diventare intricati e incomprensibili per algoritmi complessi Lezioni di Informatica classe III - Prof. Riccardo Crosato 6  Diagrammi di flusso: i principali blocchi Blocco iniziale Blocco finale Blocco di dichiarazione Blocchi di Input/Output Blocco di Blocco di selezione assegnazione Lezioni di Informatica classe III - Prof. Riccardo Crosato 7  Procedure Procedure (sottoprogrammi): unità di programma identificate che risolvono un sottoproblema del problema complessivo da risolvere (rappresentano algoritmi che possono essere riutilizzati e compongono l’algoritmo complessivo che risolve l’intero problema) – vengono identificate da un nome – il loro comportamento può dipendere da parametri in modo da rendere più generale il sottoprogramma Lezioni di Informatica classe III - Prof. Riccardo Crosato 8  Scoperta di algoritmi Lo sviluppo di un programma consiste in due attività: 1) individuare l’algoritmo che risolve il problema 2) rappresentarlo sotto forma di programma Risoluzione di un problema: 1) Capire il problema 2) Farsi un’idea di come una procedura algoritmica potrebbe risolvere il problema 3) Formulare l’algoritmo e rappresentarlo come un programma 4) Valutare la precisione del programma e la possibilità che diventi uno strumento per risolvere altri problemi Lezioni di Informatica classe III - Prof. Riccardo Crosato 9  Trovare un punto di partenza provare ad affrontare il problema al contrario analogamente a smontare un oggetto per capire come è stato costruito cercare un problema simile ma più semplice da risolvere o già risolto cercare di scomporre il problema in sottoproblemi più semplici da risolvere – raffinamento a più passi o metodologia top-down → metodologia che procede dal generale allo specifico Lezioni di Informatica classe III - Prof. Riccardo Crosato 10  Rappresentare le informazioni: i tipi di dato Le informazioni sono la conoscenza che abbiamo sul mondo Le informazioni sono rappresentate dai dati ai quali diamo un significato I dati appartengono a varie categorie, possono essere cioè di svariati tipi Il tipo di un dato sintetizza: – l’insieme dei valori rappresentabili, – le operazioni che possono essere effettuate con tali valori I dati sono dunque classificabili in base ai valori che rappresentano e alle operazioni che è possibile compiere su tali valori Tipi di dato di base: – tipo stringa: qualsiasi sequenza (anche vuota) di caratteri – tipo intero: qualsiasi valore numerico intero (positivo o negativo) – tipo reale: qualsiasi valore numerico con una parte decimale – tipo logico (booleano): uno tra i due valori vero (true) o falso (false) Lezioni di Informatica classe III - Prof. Riccardo Crosato 11  Variabili, costanti, espressioni Negli algoritmi le istruzioni descrivono spesso azioni che manipolano dati In un algoritmo vi sono due classi di oggetti che consentono di fare riferimento ai dati da elaborare, le variabili e le costanti Variabile – può essere immaginata come una scatola identificata da un nome, chiamato identificatore della variabile. – il contenuto della scatola rappresenta il valore del dato rappresentato Lezioni di Informatica classe III - Prof. Riccardo Crosato 12  Variabili Una variabile è così chiamata perché mentre il suo nome non cambia, il suo contenuto può essere modificato mediante un’istruzione di assegnazione che si indica con il simbolo = (o ← ) nome variabile = nuovo contenuto a = 200 L’esecuzione dell’assegnazione a = 200 determina le seguenti azioni: 1) l’esecutore calcola il nuovo contenuto della variabile, in questo caso ottenendo 200 2) l’esecutore assegna il valore così calcolato ad a, sostituendo il valore che essa aveva in precedenza. Nota: la maggior parte delle istruzioni di un algoritmo sono istruzioni di assegnazione Lezioni di Informatica classe III - Prof. Riccardo Crosato 13  Costanti I valori che non possono cambiare mai durante l’esecuzione del programma vengono detti costanti Le costanti si suddividono in: – costanti letterali (literal) come i valori 100, 200, “Pippo” – costanti simboliche: sono costanti letterali a cui è attribuito un nome N.B.: è convenzione comune usare identificatori tutti maiuscoli per le costanti, ad esempio PI_GRECO, VERSIONE, … Per specificare i valori costanti (letterali o attribuiti a costanti simboliche) si adottano specifiche notazioni: – le costanti di tipo numerico (reale, intero) vengono semplicemente indicate con il valore, ad esempio 100 200 3.1415 2018, … – le costanti di tipo stringa vengono indicate tra doppi apici ", ad esempio "Pippo" "Gazza Lara" "100" "0445 5400234" Lezioni di Informatica classe III - Prof. Riccardo Crosato 14  Espressioni Un’espressione è una formula che combina uno o più variabili o costanti con zero o più operazioni che operano su di essi Un’espressione, nel momento in cui viene valutata dall’esecutore, produce un valore, il cui tipo dipende dal tipo degli oggetti e dalle operazioni in essa contenute Esempi: b a+100 200 (b+a)*(a+1)/2 Dagli esempi si nota che: 1) un’espressione può contenere un solo oggetto (variabile o costante) e nessuna operazione, nel qual caso il valore dell’espressione coincide con il valore dell’oggetto 2) se l’espressione contiene solo costanti (una o più di una) essa si dice espressione costante, in quanto il suo valore è definito una volta per tutte e non varia mai 3) all’interno di una espressione è possibile fare riferimento più volte alla stessa variabile; in questo caso il valore ottenuto da entrambi i riferimenti è lo stesso Lezioni di Informatica classe III - Prof. Riccardo Crosato 15  Espressioni ed assegnazione Con il concetto di espressione, l’assegnazione è definita più rigorosamente come: nome variabile = espressione L’assegnazione viene eseguita dall’esecutore in questo modo: 1) viene calcolato il valore dell’espressione a destra 2) viene assegnato il valore così calcolato alla variabile, sostituendo quello che essa aveva in precedenza Un’istruzione di assegnazione è valida quando il tipo dell’espressione è compatibile con il tipo della variabile Il concetto di compatibilità tra i tipi di dati è determinato dal linguaggio di programmazione usato. In generale, sono valide le assegnazioni nelle quali: – una espressione di tipo intero viene assegnata a una variabile intera o reale – una espressione di tipo reale viene assegnata a una variabile reale – una espressione di tipo stringa viene assegnata a una variabile stringa Lezioni di Informatica classe III - Prof. Riccardo Crosato 16  Schemi di composizione delle istruzioni Pochi problemi sono risolvibili da una sequenza lineare di istruzioni Piuttosto, gli algoritmi sono descritti utilizzando tre schemi di composizione fondamentali: – sequenza: esecuzione sequenziale di due o più istruzioni – selezione (scelta, condizione): esecuzione alternativa di istruzioni in base al verificarsi di una condizione – iterazione (ripetizione, ciclo): esecuzione ripetuta di una o più istruzioni finché è verificata una condizione Gli schemi di composizione possono essere considerati come singole istruzioni. Ogni schema può cioè usare gli altri schemi Lezioni di Informatica classe III - Prof. Riccardo Crosato 17  Sequenza Lezioni di Informatica classe III - Prof. Riccardo Crosato 18  Selezione (scelta) se non ci sono istruzioni nel ramo “falso” si prosegue con l’esecuzione (non si lascia vuoto il ramo “vero” e se serve si inverte la condizione) Lezioni di Informatica classe III - Prof. Riccardo Crosato 19  Iterazione (ciclo) Ciclo iterativo con controllo in testa Ciclo iterativo con controllo in coda (ciclo pre-condizionale) (ciclo post-condizionale) la sequenza di istruzioni presente all’interno del ciclo viene la sequenza di istruzioni presente all’interno del ciclo viene eseguita fin tanto che la condizione rimane vera eseguita almeno una volta e fin tanto che la condizione Lezioni di Informatica classe III - Prof. Riccardo Crosato rimane vera 20  Il teorema di Böhm-Jacopini Qualunque algoritmo può essere implementato utilizzando tre sole strutture, la sequenza, la selezione e l’iterazione, da applicare ricorsivamente alla composizione di istruzioni elementari Corrado Böhm, Giuseppe Jacopini – 1966 Negli anni 1970 ha contribuito alla definizione delle linee guida della programmazione strutturata e alla critica sull’uso sconsiderato delle istruzioni goto Famoso l’articolo di Dijkstra del 1968, “Goto statement considered harmful”, sugli effetti deleteri del goto sulla qualità del software, e in particolare sulla sua leggibilità e modificabilità (il cosiddetto problema dello spaghetti code) Lezioni di Informatica classe III - Prof. Riccardo Crosato 21  Espressioni condizionali composte Tutti i linguaggi di programmazione mettono a disposizione gli operatori logici condizionali per scrivere condizioni composte, in modo da semplificare la scrittura degli algoritmi. I simboli usati in molti linguaggi sono: – || per il connettivo or ("o") – && per il connettivo and ("e") Connettivo or ( || ) Connettivo and ( && ) condizione1 || condizione2 condizione1 && condizione2 falsa falsa falso falsa falsa falso falsa vera vero falsa vera falso vera falsa vero vera falsa falso vera vera vero vera vera vero Lezioni di Informatica classe III - Prof. Riccardo Crosato 22  Ciclo con contatore Negli algoritmi è comune utilizzare cicli pre-condizionali che effettuano un conteggio Lezioni di Informatica classe III - Prof. Riccardo Crosato 23  Ciclo con contatore Nei linguaggi di programmazione il ciclo con contatore è stato formalizzato Nei flow chart lo rappresenteremo in questo modo: Lezioni di Informatica classe III - Prof. Riccardo Crosato 24