Appunti di Fondamenti di Programmazione (PDF)

ALGORITMI ED ESECUTORI Fondamenti di Programmazione Francesco Tortorella Fondamenti di Programmazione 1  Che cosa si intende per INFORMATICA ? ▪ Scienza della rappresentazione e dell’elaborazione dell’informazione ▪ L’informazione è il concetto principale dell’Informatica. ▪ L’elab...

ALGORITMI ED ESECUTORI Fondamenti di Programmazione Francesco Tortorella Fondamenti di Programmazione 1  Che cosa si intende per INFORMATICA ? ▪ Scienza della rappresentazione e dell’elaborazione dell’informazione ▪ L’informazione è il concetto principale dell’Informatica. ▪ L’elaborazione dell’informazione che si considera è quella svolta in maniera automatica tramite un calcolatore (o computer) ▪ Per poter essere automatizzata, l’elaborazione deve essere formalizzata in maniera sistematica e rigorosa Fondamenti di Programmazione 2  Che cosa si intende per INFORMATICA ? ▪ Scienza dell’astrazione ▪ creare il giusto modello per un problema e individuare le tecniche appropriate per risolverlo in modo automatico ▪ L’obiettivo è quello di sostituire una situazione del mondo reale complessa e particolareggiata con un modello comprensibile e privo di dettagli inessenziali, all’interno del quale si possa risolvere il problema Fondamenti di Programmazione 3  Che cosa si intende per INFORMATICA ? ▪ Mettiamo insieme le due definizioni: Obiettivo dell’Informatica è creare delle astrazioni di problemi del mondo reale che possano essere rappresentate ed elaborate all’interno di un sistema di calcolo al fine di eseguire dei procedimenti risolutivi in modo automatico Fondamenti di Programmazione 4  Esempio ▪ Si devono dividere lastre di marmo di Carrara, rettangolari e di dimensioni AxB (con A e B variabili) in tanti quadrati uguali avente il lato della maggiore lunghezza possibile e senza generare sfrido. ▪ Si supponga che tutte le dimensioni siano numeri interi. Fondamenti di Programmazione 5  Esempio ▪ Si vuole realizzare un procedimento automatico che, per ogni lastra, verifichi se ciò è possibile, date le dimensioni, e, in caso positivo, fornisca la lunghezza del lato del quadrato (può essere diverso per ogni lastra). Fondamenti di Programmazione 6  Esempio ▪ Quali sono gli aspetti importanti del problema ? ▪ Quali sono i dati a disposizione ? ▪ Quali sono i dati richiesti ? ▪ Come si può ridefinire in forma astratta il problema? Fondamenti di Programmazione 7  Esempio Dati in ▪ Quali sono gli aspetti ingresso importanti del problema ? ▪ Quali sono i dati a disposizione ? ▪ Quali sono i dati richiesti ? Procedimento risolutivo ▪ Come si può ridefinire in forma astratta il problema? Dati in uscita Fondamenti di Programmazione 8  Esempio ▪ Quali sono gli aspetti importanti del problema ? lato A lato B ▪ Quali sono i dati a disposizione ? ▪ Quali sono i dati richiesti ? Procedimento risolutivo ▪ Come si può ridefinire in forma astratta il problema? Dati in uscita Fondamenti di Programmazione 9  Esempio ▪ Quali sono gli aspetti importanti del problema ? lato A lato B ▪ Quali sono i dati a disposizione ? ▪ Quali sono i dati richiesti ? Procedimento risolutivo taglio ▪ Come si può ridefinire in possibile forma astratta il problema? Fondamenti di Programmazione 10  Esempio ▪ Quali sono gli aspetti importanti del problema ? lato A lato B ▪ Quali sono i dati a disposizione ? ▪ Quali sono i dati richiesti ? Procedimento risolutivo taglio lato ▪ Come si può ridefinire in possibile quadrato forma astratta il problema? Fondamenti di Programmazione 11  Esempio Dati in ▪ Quali sono gli aspetti ingresso importanti del problema ? lato A lato B ▪ Quali sono i dati a disposizione ? ▪ Quali sono i dati richiesti ? Procedimento risolutivo taglio lato ▪ Come si può ridefinire in possibile quadrato forma astratta il problema? Dati in uscita Fondamenti di Programmazione 12  Ridefiniamo il problema ▪ Calcolare il Massimo Comune Divisore (MCD) lato A lato B dei due numeri interi A e B ▪ Se il MCD è diverso da 1, il Procedimento risolutivo taglio è possibile e la misura del lato del taglio lato quadrato è data dal MCD. possibile quadrato ▪ Se il MCD è uguale a 1, il taglio non è possibile Fondamenti di Programmazione 13  Come realizzare il procedimento risolutivo? ▪ Dovremo specificare il procedimento in modo che sia eseguibile in maniera automatica. ▪ Quali caratteristiche dovrebbe avere? ▪ Dovrebbe essere una sequenza finita di operazioni chiaramente definite ▪ Dovrebbe essere specificato l’ordine di esecuzione di ogni operazione ▪ Dovrebbe essere chiaramente specificata la condizione di termine della sequenza Fondamenti di Programmazione 23  Che cosa fa? 1. Leggi due numeri X e Y, con X > Y 2. Dividi X per Y e ottieni il resto R 3. Se R=0, termina: il risultato è Y 4. Sostituisci X con Y 5. Sostituisci Y con R 6. Torna al punto 2. Fondamenti di Programmazione 25  Proviamo … X Y R Output X Y R Output 96 36 83 17 Fondamenti di Programmazione 26  Algoritmo di Euclide ▪ Uno degli algoritmi più antichi conosciuti per il calcolo del MCD, presente negli Elementi di Euclide intorno al 300 a.C. (proposizione VII.2) ▪ Probabilmente non scoperto da Euclide. Certamente era conosciuto da Eudosso di Cnido intorno al 375 a.C. ▪ Aristotele (intorno al 330 a.C.) ne ha fatto cenno ne I topici, 158b, 29-35. ▪ Non richiede la fattorizzazione dei due interi. Fondamenti di Programmazione 27  Che cos’è un algoritmo? ▪ E’ un procedimento sistematico, costituito da un insieme finito di operazioni, ognuna delle quali è precisa (non ambigua) ed eseguibile, da applicare ai dati in ingresso perché possa fornire dei dati in uscita. Fondamenti di Programmazione 28  Caratteristiche interessanti … ▪ L’algoritmo è del tutto generale, ma, in qualsiasi caso specifico, il procedimento avrà termine e fornirà una risposta precisa in un numero finito di passi. ▪ A ogni passo, è perfettamente chiaro quale operazione si debba compiere e anche la decisione circa il momento in cui il procedimento si debba ritenere concluso è perfettamente definita. Fondamenti di Programmazione 29  Caratteristiche interessanti … ▪ Con il termine passo intendiamo un'operazione di natura qualsiasi, ma elementare e determinata ▪ Con più passi si possono costruire procedimenti più articolati che realizzano un particolare compito. ▪ Con finitezza si indica un aspetto fondamentale: perché sia svolto in maniera utile il compito non può richiedere un numero infinito di passi. Fondamenti di Programmazione 31  Chi esegue l’algoritmo? ▪ Una volta definito, l’algoritmo deve essere sottoposto ad un esecutore. ▪ L’esecutore deve essere in grado di: ▪ interpretare correttamente la sequenza di comandi ▪ eseguire ognuno dei comandi forniti ▪ memorizzare informazioni su opportuni supporti che permettano di accedere alle informazioni memorizzate e modificarle ▪ Questione: ▪ l’esecutore deve essere consapevole di quello che sta facendo? Fondamenti di Programmazione 34  Un esecutore «umano» controllo lista di istruzioni dati in ingresso esecuzione risultati temporanei risultati finali Scambio dati con l’esterno 1 2 3 + 4 5 6 - 7 8 9 x 0. C / Fondamenti di Programmazione 35  Un esecutore artificiale istruzioni Unità di controllo Unità di Unità di memoria ingresso/ Unità logico- uscita aritmetica dati Fondamenti di Programmazione 36  Algoritmo e programma ▪ Differenze tra i due tipi di esecutori (umano vs artificiale): ▪ rappresentazione delle istruzioni ▪ rappresentazioni dei dati ▪ La descrizione di un algoritmo è indipendente dall’esecutore che dovrà eseguirlo ▪ Di conseguenza, è necessario rappresentare istruzioni e dati in un formato tale che l’esecutore sia capace di memorizzare e manipolare Fondamenti di Programmazione 39  Algoritmo e programma Fondamenti di Programmazione 40  Algoritmo e programma ▪ La rappresentazione dell’algoritmo comprensibile ed eseguibile dall’esecutore automatico costituisce un programma ▪ L’elaborazione delle azioni è richiesta all’elaboratore tramite comandi elementari chiamati istruzioni espresse attraverso un opportuno formalismo: il linguaggio di programmazione Fondamenti di Programmazione 42  Algoritmo e programma ▪ Un programma è un testo scritto in accordo al lessico, alla sintassi e alla semantica di un linguaggio di programmazione. ▪ Un programma è la formulazione testuale, in un certo linguaggio di programmazione, di un algoritmo che risolve un dato problema. Fondamenti di Programmazione 43  Algoritmo e programma ▪ Molti linguaggi di programmazione possibili, ognuno tipicamente indicato per risolvere problemi in un certo ambito ▪ C, C++, Java, Python, Ruby, Pascal, Perl, Swift, FORTRAN, COBOL, Assembly, C#, Basic, R, Matlab, … ▪ Di conseguenza, un algoritmo può essere implementato in linguaggi diversi ▪ Ognuno dei programmi ottenuti è un’implementazione dell’algoritmo originale ed è quindi equivalente agli altri programmi (assumendo che non ci siano errori …) Fondamenti di Programmazione 45  Algoritmo e programma problema algoritmo programma Definizione del Dati in Dati in procedimento ingresso uscita risolutivo Linguaggio di programmazione Fondamenti di Programmazione 46  Eseguire un programma: risorse e processo ▪ Una volta ottenuto il programma, questo deve essere eseguito su un sistema di elaborazione che realizzi il ruolo di esecutore. ▪ A questo scopo è necessario che il sistema metta a disposizione del programma le opportune risorse che rendano possibile l'esecuzione ▪ Esempio: memoria per ospitare i dati ed il programma, dispositivi per inserire i dati in ingresso e fornire i dati in uscita, ecc. Fondamenti di Programmazione 49  Eseguire un programma: risorse e processo ▪ Se le risorse sono disponibili, è possibile avviare l'esecuzione del programma. Da questo momento in poi si parla di processo. ▪ Differenza sostanziale: mentre il programma è la descrizione di un procedimento risolutivo, il processo è invece l'attuazione di tale procedimento. ▪ Il processo richiede un esecutore che fornisce le risorse necessarie, effettua le azioni previste, riceve i dati di ingresso e produce i dati in uscita. Fondamenti di Programmazione 52  Riferimenti ▪ Appunti prof. M.Vento ▪ 1.3.1-1.3.3 ▪ Appunti sul concetto di Algoritmo Fondamenti di Programmazione 53