• Non ci sono risultati.

Corso Informatica di Base. Flow Chart

N/A
N/A
Protected

Academic year: 2022

Condividi "Corso Informatica di Base. Flow Chart"

Copied!
53
0
0

Testo completo

(1)

Corso Informatica di Base

Flow Chart

(2)

Abbiamo detto Che..

INFORMATICA: scienza e tecnica che tratta l'elaborazione automatica dei dati e dei procedimenti di calcolo

CALCOLATORE O ELABORATORE ELETTRONICO:

macchina elettronica in grado di manipolare

automaticamente informazioni, eseguendo operazioni su dati forniti in ingresso (input), per ottenere dei risultati emessi come dati in uscita (output)

PROGRAMMA: insieme di istruzioni che possono essere eseguite da un elaboratore elettronico.

PROGRAMMATORE: Si occupa di realizzare

operativamente le applicazioni, scrivendo le istruzioni

sotto forma di linee di codice basate su specifici linguaggi di programmazione.

(3)

Modello di Computer (semplificato)

Dati In Ingresso

Elaborazione dei Dati

Dati in Uscita

(4)

Informatica

Secondo la ACM (Association for Computing Machinery)…

L’Informatica è lo Studio sistematico degli

algoritmi che descrivono e trasformano

l’Informazione: la loro teoria, analisi,

progetto, efficienza, realizzazione e

applicazione.

(5)

Risoluzione di un Problema

Problema

Algoritmo

Programma

Linguaggio Macchina

Input Macchina Output

L’uomo descrive l’algoritmo che la macchina deve seguire per risolvere il problema (ad esempio con i Diagrammi di flusso)

La descrizione viene tradotta in Linguaggio di alto livello (ad esempio il linguaggio C)

Il programma di alto livello viene tradotto in linguaggio

Macchina, ovvero codice binario (ad esempio dal

compilatore)

(6)

Esempi di Algoritmi

Ricetta per cucinare gli spaghetti

➔ Metti l’acqua nella pentola

➔ Fai bollire l’acqua

➔ Metti la pasta nell’acqua

➔ Aggiungi un po’ di sale

➔ Attendi 6 minuti

➔ Scola la pasta

(7)

Esempi di Algoritmi

Verifica se un numero è pari o dispari

➔ Prendi il numero

➔ Calcola il resto della divisione intera del numero per 2

➔ Se il resto è zero

– Allora il numero è pari

– Altrimenti il numero è dispari

(8)

Algoritmi

Con il termine algoritmo si intende, in genere, un

metodo per la risoluzione di problemi utilizzando un numero finito di passi.

Da questa definizione si evincono le quattro proprietà fondamentali dell'algoritmo:

la sequenza di istruzioni deve essere finita (finitezza);

essa deve portare ad un risultato (effettività);

• le istruzioni devono essere eseguibili materialmente (realizzabilità);

• le istruzioni devono essere espresse in modo non ambiguo (non ambiguità).

(9)

Caratteristiche di un algoritmo

Azioni eseguibili e non ambigue

Non sono ammessi “un pò” e “a piacere”, che non sono termini adatti ad una macchina

Deterministico

Fatto un passo, il successivo è uno ed uno solo, ben

determinato. Alternative sono possibili, ma la scelta deve essere unica

Numero finito di passi

Terminazione

L’esecuzione prima o poi deve finire e produrre un risultato in tempo finito

Osservazione: la 3 non implica la 4

(10)

Esempio di non terminazione

Si consideri il numero N

• Scrivere N

• Scrivere il numero successivo ad N

• Ripetere il passo precedente

(11)

Esempio di non terminazione

Trova il più grande numero primo.

Non esiste un programma che riesce a dare una risposta in tempo finito (Numero finito di

passi)

(12)

Tutti i problemi sono risolvibili???

No..

Un problema risolvibile con un algoritmo si dice

computabile

(13)

Risoluzione di un problema

Generalmente la risoluzione di un problema

consiste nel prendere alcuni dati iniziali (input) relativi al problema e nel fornire un

risultato (output) che risolve quest’ultimo.

Input Esecutore Output

Algoritmo

(14)

Non è così Facile

Per scrivere la giusta “sequenza di passi”bisogna essere un bravo cuoco!

Preparare gli Spaghetti:

• Ingredienti (acqua, Sale, Spaghetti)

• Eseguire la ricetta

• Servire gli Spaghetti

(15)

Codifica dell’Algoritmo

Affinchè una macchina riesca a comprendere ed eseguire i passi specificati da un algoritmo,

quest’ultimo deve essere prima codificato in un opportuno programma scritto in un

linguaggio ad alto livello (che verrà

successivamente compilato/interpretato)

Algoritmo Traduzione Programma

(16)

Rappresentazione degli algoritmi

E’ necessario far riferimento a dei formalismi che:

• non introducano ambiguità

• siano universalmente riconosciuti ed interpretati allo stesso modo da un generico esecutore

• permettano di rappresentare in modo efficace un algoritmo

• Costituiscano un utile strumento per poi poter passare alla fase di codifica in un linguaggio di programmazione

(17)

Rappresentazione degli algoritmi

1. Rappresentazione grafica

– Diagrammi a blocchi / Flow Chart

2. Rappresentazione testuale

– Notazione Lineare Strutturata / PseudoCodice

(18)

Algoritmi: operazioni base

Le operazioni primarie sono:

Trasferimento di informazioni (istruzioni di I/O)

lettura dati, scrittura risultati, visualizzazione dati intermedi

Esecuzione di calcoli (valutazione espressioni)

Istruzioni di assegnamento

Strutture di controllo (che modificano il flusso

sequenziale di esecuzione delle operazioni)

(19)

Diagrammi di Flusso

I diagrammi a blocchi (detti anche diagrammi di flusso) sono un linguaggio di modellazione grafico per

rappresentare algoritmi (in senso lato).

Esso consente di descrivere le differenti operazioni sotto forma di uno schema in cui le diverse fasi del processo e le differenti condizioni che devono essere rispettate vengono rappresentati da simboli grafici detti blocchi elementari. I blocchi sono collegati tra loro tramite frecce che indicano la cronologia.

(20)

Diagrammi di Flusso

Ogni azione elementare è rappresentata da un blocco.

Esistono 5 tipi di blocchi elementari:

Blocco iniziale Blocco finale

Blocco I/O Blocco Controllo

Blocco Elaborazione

(21)

Istruzioni di I/O

• lettura di dati in input

• scrittura dei risultati in output

(22)

Connettori

I singoli diagrammi devono essere uniti tramite i connettori.

L’esecuzione delle istruzioni deve essere fatta

sequenzialmente, ovvero seguendo i connettori.

Quando si scrive lalgoritmo bisogna fare molta

attenzione alla direzione del flusso di esecuzione.

(23)

Istruzione di Assegnamento

Concetto di variabile

• Identificata da un’etichetta / identificatore simbolico

Può essere comodo pensare alla variabile come ad un contenitore in cui possiamo memorizzare o reperire dei dati utilizzati durante il calcolo

• L’istruzione di assegnamento permette di

assegnare un valore ad una variabile

(24)

Istruzione di Assegnamento

Una variabile numerica è una entità caratterizzata da

• Un nome

• Un valore (contenuto)

• Può cambiare nel tempo

Una costante numerica è una entità caratterizzata da

• Un nome

• Un valore (contenuto)

• Non può cambiare nel tempo

(25)

Istruzione di Assegnamento

A = 5 Alla Variabile A

assegno il valore 5

(26)

Espressione

Un’espressione è una combinazione di

operatori aritmetici, costanti e variabili che può essere calcolata generando un singolo valore numerico

Es: X+1 X+(Y*5)

(27)

Istruzione di Assegnamento

• Istruzione di assegnamento: “ ”

• Variabile Espressione X 5 Y X+4

Assegno alla Variabile x il valore 5

La Variabile Y conterrà il valore della somma tra il numero 4 ed il valore assegnato alla variabile X

X = 5 Y=X+4

(28)

Esempio

Descrivere mediante diagrammi di flusso, un

algoritmo che calcoli la somma di due numeri

letti in input

(29)

Diagramma di flusso: Somma

Inizio

Leggi Y Leggi X

Z X + Y

Scrivi Z

Fine

(30)

Esempio 2

Descrivere, mediante diagrammi di flusso, un

algoritmo che scambi i valori di due variabili

lette in input.

(31)

Diagramma di flusso: Scambio

Inizio

Leggi X

Leggi Y

Aux Y

Y X

X Aux

Scrivi Y

Scrivi X

Fine

(32)

Flusso di esecuzione

Si possono avere casi in cui nel flusso di esecuzione si deve scegliere tra diverse direzioni

La direzione da scegliere è subordinata al verificarsi di una condizione

La condizione può assumere due stati:

– Vero – Falso

In questi casi si parla di istruzione condizionale

(33)

Strutture di controllo

Tutti gli algoritmi devono adattarsi ad una classe di problemi per essere applicati al mondo reale e le

operazioni da effettuare per raggiungere la soluzione spesso differiscono a seconda dei casi che si

presentano.

Per questo esistono delle particolari strutture del

linguaggio che permettono di controllare il flusso di esecuzione (quindi delle operazioni), ovvero di

eseguire una certa serie di istruzioni anche piu' volte nel momento in cui si verifica di una serie di condizioni.

Queste strutture sono assolutamente indispensabili, infatti non esiste un linguaggio di programmazione in cui non e' possibile controllare il flusso del processo.

(34)

Strutture di controllo

Quasi la totalità dei programmi ha la necessità di

svolgere alcune istruzioni o compiere determinate operazioni (oppure evitare di compiere alcune

operazioni) a seconda dei dati di partenza.

Per esempio un programma che esegue una divisione tra due numeri a / b dovrà evitare di compiere

l'effettiva operazione aritmetica se il dato b = 0.

Per questo in tutti i linguaggi di programmazione

esistono dei particolari costrutti che generalmente permettono di:

- Scegliere se eseguire o meno una certa porzione di codice, oppure

- Eseguire più volte una certa parte di codice.

(35)

Strutture di controllo

(36)

Istruzioni Condizionali

La selezione (o scelta) permette a un programma di

proseguire secondo uno tra due (o più) flussi di istruzioni

alternative, a seconda del risultato di un test o del verificarsi di una condizione.

L’iterazione (o ciclo, o loop) consiste nella ripetizione di una o più istruzioni, e si può ottenere collegando il flusso in uscita da un blocco con il flusso in entrata nel blocco stesso o in uno precedente.

In tal modo si possono eseguire compiti ripetitivi senza

specificare uno per uno un gran numero di singoli passi, ma scrivendo per esempio un’istruzione del tipo: “esegui il

prossimo passo 1.000 volte”.

(37)

Istruzioni Condizionali

Selezione binaria. Nella selezione il test o la condizione sono tipicamente costituiti da una variabile logica, scritta dentro il simbolo di decisione, (blocco

controllo)dal quale escono due frecce. Queste

indicano le possibili azioni da compiersi a seconda del valore della variabile, come mostra la figura.

(38)

Istruzioni Condizionali

Si può anche volere compiere una certa azione se il test o la condizione hanno un valore vero, e nessuna

azione nel caso contrario.

(39)

Esempio

Descrivere mediante diagramma di flusso,un

algoritmo che determini il massimo tra due

numeri letti in input

(40)

Diagramma di Flusso: Max

Inizi

Leggi X

Leggi Y

X>Y Scrivi X

Scrivi Y

Vero

Falso

Fine

(41)

Struttura IF-ELSE

L’istruzione condizionale if-else è costruita per

scegliere l’esecuzione di un’istruzione in alternativa a un’altra a seconda del valore assunto da una data condizione.

if (condizione) { operazione }

L'operazione può anche non essere racchiusa tra parentesi graffe.

Vediamo un semplice esempio.

if ($a==5) {

echo "La variabile a vale 5";

}In questo caso verrà stampata la stringa "La variabile a vale 5" solo quando $a sarà uguale a 5.

(42)

Struttura IF-ELSE

Abbiamo introdotto il controllore else: aggiunge la possibilità di eseguire un'istruzione alternativa nel caso la condizione non sia vera.

if (condizione) { operazione1 } else{ operazione2 }

Vediamo ora di applicare tutti i casi finora visti, utilizzando l'annidamento di più if: l'importante è ricordarsi di chiudere sempre una condizione che si è aperta.

if ($a>$b)

{ echo "a è maggiore di b"; }

else{ if ($a<$b) { echo "a è minore di b"; } else{ if ($a == $b) { echo "a è uguale di b"; }

}}

(43)

Strutture di Controllo Iterattive

Le strutture di controllo "iterative" consentono di

specificare che una data istruzione o un dato blocco di istruzioni devono essere eseguiti ripetutamente.

Esse vengono anche dette cicli.

Ogni struttura di controllo di questo tipo deve consentire di specificare sotto quali condizioni l'iterazione (ripetizione) di tali istruzioni debba

terminare, ovvero la condizione di terminazione del ciclo oppure, equivalentemente, la condizione di

permanenza nel ciclo.

(44)

Struttura While

Il ciclo while (mentre, o fintantoché) è indicato quando la condizione di permanenza in un ciclo è una

generica condizione booleana, indipendente dal

numero di iterazioni eseguite. Le forme tradizionali di ciclo while possono essere parafrasate come "ripeti (il codice controllato) fintantoché resta vera la

condizione C". Un esempio tipico è la lettura di dati da un file di cui non si conosca a priori la dimensione;

esso potrebbe assumere la forma "leggi il prossimo dato finché non incontri la fine del file".

(45)

Struttura While

Vediamo un semplice esempio:

$i=1;

while ($i <= 10) { echo $i;

$i++;

} Questo ciclo continua ad incrementare la variabile $i fino a quando non sarà uguale a 10 ed ogni volta

stampa il suo valore. In pratica verrà stampata la stringa "1 2 3 4 5 6 7 8 9 10".

(46)

Struttura Do-While

Un modo alternativo per eseguire la stessa cosa sarà ricorrere al ciclo do..while. L'unica differenza è che il valore della condizione viene

controllato alla fine del ciclo e non all'inizio. In pratica la prima operazione viene sempre eseguita, sia che la condizione sia vera o falsa.

do {

operazione

} while ( condizione ) Vediamo l'esempio:

$i=1;

do{

echo $i;

$i++;

}while ($i <= 10)

(47)

Strutture Dati

Una struttura dati è un'entità usata per organizzare un insieme di dati all'interno della memoria del

computer, ed eventualmente per memorizzarli in una memoria di massa. La scelta delle strutture dati da utilizzare è strettamente legata a quella degli

algoritmi.

La struttura dati è un metodo di organizzazione dei dati, quindi prescinde dai dati effettivamente

contenuti.

Ciascun linguaggio di programmazione offre strumenti, più o meno sofisticati, per definire strutture dati,

ovvero aggregare dati di tipo omogeneo o eterogeneo.

(48)

Gli Array

Un array è una struttura dati omogenea, che contiene un numero finito di elementi dello stesso tipo, ad

esempio un vettore di 10 interi. Questi elementi sono individuati attraverso un indice numerico, che

tipicamente va da 0 al numero massimo di elementi meno uno. La dimensione del vettore deve essere dichiarata al momento della sua creazione. Vettori di dimensione diversa costituiscono tipi di dati diversi.

Gli elementi dell'array (le variabili che lo costituiscono) sono identificate dallo stesso nome dell'array e da uno o più indici, che indicano la posizione

dell'elemento all'intero del vettore o della matrice.

(49)

Gli Array

Array monodimensionale:

Un array ad una dimensione è costituito da un insieme finito di elementi omogenei in corrispondenza

biunivoca con un insieme di indici.

Array bidimensionale può essere considerato un array di array monodimensionali cioè ogni componente dell’array è esso stesso un array

L’accesso ad ogni componente di un array

bidimensionale si ha tramite una coppia di indici (i,j) Il primo indice si riferisce alla riga ed il secondo alla

colonna

(50)

Gli Array

X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7]

Array Monodimensionale X

A[0][0] A[0][1] A[0][2] A[0][3] A[0][4]

A[1][0] A[1][1] A[1][2] A[1][3] A[1][4]

A[2][0] A[2][1] A[2][2] A[2][3]

Array Bidimensionale

A

COLONNE

R I G H E

(51)

Gli Array

Essi godono delle seguenti proprietà:

• Gli array sono uno dei tipi di dato strutturato

• Sono composti da elementi omogenei

• Ogni elemento è identificato all’interno del vettore da un numero d’ordine detto anche indice

dell’elemento

• E’ possibile riempire o leggere una sola posizione per volta

Il numero degli elementi è detto dimensione o lunghezza del vettore

(52)

Gli Array

Ad esempio, pensiamo di voler memorizzare i nomi dei giorni della settimana all'interno dell'array di tipo stringa chiamato giorno;

avremo la seguente struttura:

$giorno[0] = "lunedi'" $giorno[1] = "martedi'"

$giorno[2] = "mercoledi'" $giorno[3] =

"giovedi'" $giorno[4] = "venerdi'" $giorno[5] =

"sabato" $giorno[6] = "domenica"

(53)

Array

Esercizi sugli array

Riferimenti

Documenti correlati

Scrivere un programma C che definisca la struttura “esame”, composta dal nome dell’esame (stringa) e dal voto (intero).. Si leggano poi da terminale n esami, con n

 Quando un tipo è dichiarato con typedef su strutture aggregate anonime (struct e union senza tag), le variabili di quel nuovo tipo sono considerate dello stesso tipo.

Lo studente sarà in grado di applicare le conoscenze del Linguaggio C e delle metodologie di progettazione dei programmi per la soluzione di problemi relativi a casi di

10  Docente: Davide Catania. INFO: IN BIBLIOTECA, 0363

 “Estrarre dalla base di dati una tabella, StudentiTriennio, contenente i dati degli studenti della laurea

[r]

Nota: il metodo considerato in questo esercizio funziona bene anche se applicato al problema (B) introdotto a lezione (il problema sul quale Eulero per funzionare richiedeva un

=⇒ Non serve specificare la dimensione del vettore nel parametro formale ( `e un puntatore al tipo degli elementi del vettore).. Quando passiamo una matrice ad una funzione, per