Corso Informatica di Base
Flow Chart
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.
Modello di Computer (semplificato)
Dati In Ingresso
Elaborazione dei Dati
Dati in Uscita
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.
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)
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
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
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à).
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
Esempio di non terminazione
Si consideri il numero N
• Scrivere N
• Scrivere il numero successivo ad N
• Ripetere il passo precedente
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)
Tutti i problemi sono risolvibili???
No..
Un problema risolvibile con un algoritmo si dice
computabile
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
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
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
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
Rappresentazione degli algoritmi
1. Rappresentazione grafica
– Diagrammi a blocchi / Flow Chart
2. Rappresentazione testuale
– Notazione Lineare Strutturata / PseudoCodice
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)
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.
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
Istruzioni di I/O
• lettura di dati in input
• scrittura dei risultati in output
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 l ’ algoritmo bisogna fare molta
attenzione alla direzione del flusso di esecuzione.
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
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
Istruzione di Assegnamento
A = 5 Alla Variabile A
assegno il valore 5
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)
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
Esempio
Descrivere mediante diagrammi di flusso, un
algoritmo che calcoli la somma di due numeri
letti in input
Diagramma di flusso: Somma
Inizio
Leggi Y Leggi X
Z X + Y
Scrivi Z
Fine
Esempio 2
Descrivere, mediante diagrammi di flusso, un
algoritmo che scambi i valori di due variabili
lette in input.
Diagramma di flusso: Scambio
Inizio
Leggi X
Leggi Y
Aux Y
Y X
X Aux
Scrivi Y
Scrivi X
Fine
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
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.
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.
Strutture di controllo
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”.
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.
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.
Esempio
Descrivere mediante diagramma di flusso,un
algoritmo che determini il massimo tra due
numeri letti in input
Diagramma di Flusso: Max
Inizi
Leggi X
Leggi Y
X>Y Scrivi X
Scrivi Y
Vero
Falso
Fine
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.
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"; }
}}
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.
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".
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".
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)
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.
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.
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
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
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