Informatica: algoritmi, linguaggi di programmazione e loro esecuzione

Informatica

UNIVERSITA SITAS . STUDIORUN RUM . PAR INFORMATICA SCIENZE ZOOTECNICHE E TECNOLOGIE DELLE PRODUZIONI ANIMALI ALMA Lezione 2 A.D. 962 AENSIS

Esecuzione di un algoritmo sul computer

Definizione di algoritmo

IMPLabEsecuzione di un algoritmo sul computer algoritmo Procedura di trasformazione di un insieme di dati iniziali in un insieme di risultati finali mediante una sequenza di istruzioni.

Linguaggio e Programma

Linguaggio (insieme di simboli e regole) linguaggio di programmazione per rappresentare le istruzioni di un algoritmo e la loro concatenazione Programma algoritmo scritto in un linguaggio di programmazione al fine di comunicare al calcolatore elettronico le azioni da eseguire

Processo

Processo programma in esecuzione sul computer

Requisiti di un algoritmo per il calcolatore

DIOD ALMA PARMENSIS IMPLabEsecuzione di un algoritmo sul computer · REQUISITI DI UN ALGORITMO PER IL CALCOLATORE · Eseguibilità: istruzioni eseguibili in un tempo finito · Non-ambiguità: istruzioni non ambigue, univocamente interpretabile dal calcolatore · Terminazione: terminazione dell'esecuzione dopo un numero finito di passi · Determinismo: dato un insieme di dati in ingresso il flusso delle operazioni deve essere sempre lo stesso

Descrizione di un algoritmo: diagrammi di flusso

Formalismo grafico

IMPLab M . PARMENSISDescrizione di un algoritmo: diagrammi di flusso · Un formalismo grafico: i diagrammi a blocchi (flow chart) · È un linguaggio formale di tipo grafico per rappresentare gli algoritmi · Attraverso il diagramma a blocchi si può indicare l'ordine di esecuzione delle istruzioni · Un particolare simbolo grafico detto blocco elementare è associato a ciascun tipo di istruzione elementare · I blocchi sono collegati fra loro tramite frecce che indicano il susseguirsi delle istruzioni

Esempio di diagramma di flusso

1 begin X blocco iniziale blocco di lettura blocco azione Scrivi falso vero C end X blocco finale blocco di scrittura blocco di controllo IMPLab ALMA . RUM . PARMENSIS 'Leggi A

Cosa sono le variabili

· In informatica, una variabile è un'astrazione di uno spazio di memoria associata a un nome simbolico, che contiene una quantità di dati o un oggetto, noto o sconosciuto, chiamato valore. · Una variabile è un contenitore con un nome specifico per un particolare insieme di bit o tipo di dati. AS . STUDI ALMA . QUM . PARMENSIS JERS IMPLab AD. 962

Diagramma di flusso - Blocchi

Inizio e fine esecuzione

Diagramma di flusso - Blocchi Inizio e fine esecuzione: · Inizio è il blocco da cui deve iniziare l'esecuzione dell'algoritmo (uno solo). La freccia è sempre uscente dal blocco inizio. · Fine è il blocco che fa terminare l'esecuzione dell'algoritmo (almeno uno). La freccia è sempre entrante nel blocco fine A questi blocchi non corrisponde alcuna azione! Inizio Fine AS . STUDI ALMA . QUM . PARMENSIS JERS IMPLab AD. 962

Ingresso (lettura, read, input)

Diagramma di flusso - Blocchi Ingresso (lettura, read, input) Esecuzione dell'istruzione: Si ricevono dall'unità di ingresso (per esempio, la tastiera) tanti valori quante sono le variabili specificate all'interno del blocco 1 var A, B, C Leggi A, B, C «Crea le variabili A,B,C. Leggi i tre valori da tastiera, e salvali rispettivamente nelle variabili A, B e C» ALMA . UM . PARMENSIS ERS IMPLab AD. 962

Uscita (stampa, print, output)

Diagramma di flusso - Blocchi Uscita (stampa, print, output) · Esecuzione dell'istruzione: Si calcolano i valori delle espressioni e si trasmettono all'unità di uscita (ad esempio,il video) · «calcola il valore dell' espressione A e stampala a video» · N.B. il valore di A non viene alterato dall'esecuzione del blocco 1 Stampa A TUDI ALMA . UN UM . PARMENSIS JERS IMPLab AD 962

Assegnamento

Diagramma di flusso - Blocchi Assegnamento Esecuzione dell'istruzione: Si calcola il valore dell'espressione a destra del simbolo «=» e lo si salva (assegna) nella variabile indicata a sinistra del simbolo «=» «Calcola il valore dell'espressione i+1 ed assegnalo alla variabile i » · Esempio: se i vale 6 prima di entrare nel blocco, calcolo 6+1 (7) e lo salvo nella variabile i. · Quando si esce dal blocco la variabile i vale 7. 1 i=i+1 DIOD ALMA ARMENSIS IMPLab A.D. 962

Condizioni

Diagramma di flusso - Blocchi Condizioni Esecuzione dell'istruzione: Si valuta la condizione specificata all'interno del blocco: se è verificata, si prosegue con la line di flusso contrassegnata da «Sì», altrimenti (se non è verificata) si prosegue con il ramo etichettato con «No» «Calcola il valore dell'espressione ¡<= 10: se è vero, prosegui per il ramo Sì, altrimenti prosegui per il ramo No» · Il blocco condizione è l'elemento base per realizzare alternative e ripetizioni. Sì (vero) No (falso) i ≤ 10 ? IMPLab ALMA . UN AD. 962 RUM . PARMENSIS

Diagrammi di flusso

Descrizione di un algoritmo

Diagrammi di flusso Un diagramma a blocchi descrive un algoritmo se: · ha un blocco iniziale e uno finale; · è costituito da un numero finito di blocchi azione e/o blocchi lettura/scrittura e/o blocchi di controllo; · ciascun blocco elementare soddisfa le condizioni di validità AS . STUDI JERS QUM . PARMENSIS IMPLab ALMA . AD. 962

Condizioni di validità

Diagrammi di flusso Condizioni di validità: · ciascun blocco azione, lettura/scrittura ha una sola freccia entrante e una sola freccia uscente; · ciascun blocco di controllo ha una sola freccia entrante e due frecce uscenti; · ciascuna freccia entra in un blocco o si innesta su un'altra freccia; · ciascun blocco è raggiungibile dal blocco iniziale; · il blocco finale è raggiungibile da qualsiasi altro blocco. ALMA UM . PARMENSIS IMPLab

Esempio di diagramma di flusso

Distributore automatico di caramelle

Esempio di diagramma di flusso Distributore automatico di caramelle inizio no la macchina funziona I Sİ si il cassetto e' vuoto no inserire le monete rivolgersi al negozio accanto ritirare il resto e il pacchetto fine fine i test decidono la sequenza delle istruzioni successive

Azioni ripetute

0 Azioni ripetute inserire una moneta inserire una moneta inserire una moneta inserire una moneta no inserite 3 monete ¥ si AS . STUDIORI ALMA . UM . PARMENSIS IMPLab

Esempio con variabili

Esempio di diagramma di flusso Inizio var A, B leggi A, B var C Sì No A<B ? C = A C =B stampa C Fine DIOR ALMA . UN A.D. 962 M . PARMENSIS IMPLab

Iterazione o Ripetizione

Descrizione

Iterazione o Ripetizione Esprime la ripetizione di una sequenza di istruzioni. Nel caso più generale (ripetizione enumerativa), è costituita da: · Inizializzazione: assegnazione dei valori iniziali alle variabili caratteristiche del ciclo (viene eseguita una sola volta); · Controllo: determina, in base al valore delle variabili che controllano l'esecuzione del ciclo se il ciclo deve essere ripetuto o meno; · Corpo: esecuzione delle istruzioni fondamentali del ciclo che devono essere eseguite in modo ripetitivo; · Modifica: modifica dei valori che controllano l'esecuzione del ciclo (eseguito ad ogni iterazione). ALMA UM . PARMENSIS IMPLab

Esempio di iterazione

Iterazione o Ripetizione - Esempio Inizio var n leggi n var i = 1 Inizializzazione Controllo No i <= n ? Sì stampa i Corpo i = 1 + 1 Modifica Fine ALMA . UNIVERS A.D. 962 UM . PARMENSIS TUDIORUA 5 IMPLab

Calcolatore elettronico come esecutore

Istruzioni e ipotesi

Calcolatore elettronico come esecutore Il calcolatore elettronico è un esecutore di algoritmi : un algoritmo per il calcolatore elettronico deve essere scritto tenendo conto delle istruzioni che il calcolatore elettronico è capace di eseguire Ipotesi sull'esecutore: 1. comprende un linguaggio simbolico 2. è in grado di acquisire numeri interi in ingresso e produrre numeri interi in uscita 3. è in grado di eseguire soltanto somme e sottrazioni tra due operandi e di verificare se un operando è uguale a 0

Requisiti dell'esecutore

Requisiti dell'esecutore: · disponibilità dei valori delle variabili in ogni momento dell'esecuzione: unità di memoria · capacità di elaborazione per somme, sottrazioni, confronti con 0: unità aritmetico/logica · capacità di colloquiare con l'esterno: unità di ingresso (input) ed uscita (output) · comunicazione tra le varie unità ALMA RUM . PARMENSIS IMPLab

Esempio di algoritmo

Moltiplicazione di due interi

Esempio di algoritmo Algoritmo per l'esecuzione della moltiplicazione di due interi

Schemi a blocchi (non corretti)

Schemi a blocchi (non corretti) dell'algoritmo della moltiplicazione condizioni 1 e 2 inizio leggi w leggi y z == w* y scrivi z fine condizioni 2 e 3 (ma non 1) inizio leggi w leggi y Z=0 Z := Z+W l'operazione precedente e' stata ripetuta y volte ? no + si scrivi z fine AS . STUDI JERS ALMA . AD. 962 QUM . PARMENSIS IMPLab

Schema a blocchi corretto

Esempio di algoritmo Schemi a blocchi corretto dell'algoritmo della moltiplicazione inizio leggi w leggi y Z := 0 u == y Z := Z+W u := u-1 no u= 0 - scrivi z fine soddisfa tutte le condizioni enunciate opera su una qualsiasi coppia di numeri interi ( Y strettamente positivo) i valori acquisiti dall'esterno sono memorizzati nelle variabili w e Y; il risultato è memorizzato in Z 0 e 1 sono costanti la variabile U è utilizzata come contatore del numero di iterazioni l'operazione di assegnamento calcola l'espressione a destra del simbolo := e ne assegna il valore alla variabile a sinistra l'istruzione <leggi> è un particolare tipo di assegnamento che preleva valori dall'unità di ingresso M . PARMENSIS IMPLab ALMA

Linguaggi di programmazione

Codifica e struttura

Linguaggi di programmazione · Il programma deve essere riportato in memoria in forma binaria: · Come codificare le istruzioni di un programma in forma binaria ? · Occorre una descrizione più dettagliata del calcolatore. · I linguaggi di programmazione hanno un lessico (operazioni elementari che il calcolatore è in grado di capire) e una grammatica (o sintassi) che esprime le regole con cui si possono combinare gli elementi lessicali · I linguaggi si distinguono in linguaggi a basso livello e linguaggi a alto livello · Quelli di basso livello sono più vicini alla logica del calcolatore e si distinguono in linguaggi macchina (sequenza di 0 e 1 - l'unico che il calcolatore riesce a capire) e linguaggi assemblativi ALMA . L UM . PARMENSIS IMPLab AD. 962

Linguaggio assemblativo

Operazioni elementari

Linguaggio assemblativo · È un linguaggio che definisce le operazioni elementari effettivamente disponibili sul calcolatore. Ogni operazione è definita da un codice operativo simbolico e un (eventuale) indirizzo di memoria simbolico. Il Linguaggio assemblativo dipende dallo specifico calcolatore.

Esempio di linguaggio assemblativo

· Semplice esempio di Linguaggio assemblativo · caricamento operando - LOAD: LOAD in R1 A (LOAD in R2 A) carica in R1 (R2) il dato memorizzato alla cella il cui indirizzo è A · operazioni aritmetiche sui registri - ADD, SUB : somma (sottrai) il contenuto di R2 a quello di R1 e memorizza il risultato in R1 · operazioni di test - JUMP to A: se R1 ¢ O la prossima istruzione da eseguire è nella cella di indirizzo A, altrimenti procede in sequenza · memorizzazione dei registri - STORE: STORE R1 in A (STORE R2 in A) memorizza il contenuto di R1 (R2) nella cella di indirizzo A · arresto dell'esecuzione (STOP) ALMA . L UM . PARMENSIS IMPLab