Corso di Robotica
Residenza Universitaria Alcantara
20 Gennaio 2005
Modulo di Informatica:
Introduzione alla programmazione
Giovanni Farinella
Riferimenti




Corso di Programmazione 1 (G. Gallo, G.
Cincotti) www.dmi.unict.it/~gallo/SitoProg1
Corso di Laurea in Informatica - Dipartimento
di Matematica e Informatica - Università di
Catania www.dmi.unict.it/informatica
Corso di Fondamenti di
Informatica(Calabrese), Facoltà di Ingegneria,
Università di Parma
Corso di Fondamenti di Informatica(A.
Fantechi), Dipartimento di Sistemi e
Informatica, Università di Firenze
Introduzione: Cos’è l’informatica?

Informatica = Informazione +
Automazione

Si riferisce ai processi e alle tecnologie che
rendono possibile l’immagazzinamento e
l’elaborazione dell’informazione mediante
macchine
Calcolatore= esecutore di ordini o automa
 Programmatore= colui che individua la
sequenza di ordini per risolvere un
problema

Computer: Un modello
Semplificato(grezzo)
Dati in Uscita
Dati in Ingresso
Operazioni sui dati
Dati

In maniera semplificata possiamo dire che i dati
sono:

Numeri


Testi



Sequenze alfanumeriche con codici che ne condizionano la
“apparenza”
Segnali digitali


Sequenze Alfanumeriche
Testi Formattati


Interi, decimali;
Imitano i segnali analogici a cui siamo abituati (suoni e
immagini)
Queste informazioni vengono rappresentate in un
computer attraverso la codifica binaria
ES: 00001001 = codifica il numero decimale 9
Alfabeto Digitale
Alfabeto Digitale = {0, 1}
 Una cifra binaria è pari ad un BIT (b)
 8 cifre binarie sono pari ad un BYTE (B)
 1024 BYTE sono pari ad 1 KiloByte (KB)
 1024 KB sono pari ad 1 MegaByte (MB)
 1024 MB sono pari ad 1 GigaByte (GB)
 1024 GB sono pari ad 1 TeraByte (TB)
:
:

Operazioni

Un computer esegue operazioni logiche e
aritmetiche

Un programma contiene la descrizione di
tutte le operazioni da eseguire
Programmazione

L’attività di redigere programmi per i calcolatori è
detta Programmazione

Programmare è una attività che si “apprende”!



Come fare?
Da dove iniziare
Analogia

Come si fa ad imparare a guidare?


Un po’ di Teoria (a cosa servono i pedali, le spie, ecc..) ,
tanta pratica(quando frenare? Quanto velocemente
si arresta l’auto?).
Algoritmo

Dato un problema, un algoritmo è una
procedura, cioè una sequenza di passi,
che può essere eseguita automaticamente
da una macchina in modo da risolvere il
problema dato.

Non tutti i problemi sono risolvibili. Un
problema risolvibile con un algoritmo si dice
computabile
Esempio di Algoritmo

La torta al cioccolato



Abbiamo gli ingredienti (uova, farina, latte,
ecc..) con le giuste quantità
Seguiamo la ricetta
Serviamo la torta
Altro esempio

Kit di montaggio




Procuriamo il kit e gli strumenti
Apriamo la scatola
Leggiamo le istruzioni
Mettiamo insieme i pezzi
Risoluzione di un problema
Algoritmo
Input

Esecutore
Output
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
Non è così facile come sembra!

Per scrivere la giusta “sequenza di passi”
bisogna essere un bravo cuoco e un bravo
costruttore!
Infatti…
Problema
Risolutore
Esecutore
… la risoluzione
automatica prevede
una notevole componente
umana!!!
Algoritmo
Processo di Esecuzione
Definizione di algoritmo (Formale)

Un algoritmo è una sequenza ordinata e
finita di passi (azioni o istruzioni) che
producono un ben determinato risultato in
un tempo finito
Caratteristiche di un algoritmo
1.
Azioni eseguibili e non ambigue
1.
2.
Deterministico
1.
3.
4.
Non sono ammessi “un pò” e “a piacere”, che non sono
termini adatti ad una macchina
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
1.
2.
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
1.
2.
3.
4.
Si consideri il numero N
Scrivere N
Scrivere il numero successivo ad N
Ripetere il passo precedente
Esempio di non terminazione
F(X,Y)=
1 se nell’espansione decimale di ∏
ci sono più “X” che “Y”
O altrimenti
Non esiste un programma che riesce a dare una risposta in tempo
finito (Numero finito di passi)
L’espasione decimale di ∏ è infinita!
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
Risoluzione di un problema: Esecuzione
Automatica
L’uomo descrive l’algoritmo che la
macchina deve seguire per risolvere il
problema (ad esempio con i Diagrammi
di flusso)
Problema
Algoritmo
Programma
Linguaggio Macchina
Input
Macchina
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)
Output
Scomposizione in sottoproblemi

Ricetta del pollo alle mandorle



Abbiamo gli ingredienti (pollo, olio, mandorle,
ecc..) con le giuste quantità (150g di pollo, 3
cucchiai d’olio, ecc..)
Seguiamo la ricetta
Serviamo il piatto
Scomposizione in sottoproblemi

Ricetta del pollo alle mandorle







Preparare il soffritto e aggiungervi il pollo
Unire le mandorle pelate al soffritto
Mescolare fino a quando il pollo sarà ben
cotto
Aggiungere il pepe
Rosolare con il vino bianco per 3 minuti
Aggiungere l’olio
Se preferisci salato, allora aggiungi il sale
Scomposizione in sottoproblemi


La ricetta precedente è un esempio di cosa
significa scomporre un problema in sottoproblemi
(Top-Down)
Ogni sottoproblema può essere scomposto in
problemi via via più elementati






Preparare il soffritto e aggiungervi il pollo
Si può ancora scomporre in
Sbucciare le carote
Pulire il pollo
:
:
Descrizione di un algoritmo

Si descrive un algoritmo cercando di
sintetizzare il più possibile la sua sequenza
di passi.

La descrizione avviene mediante:


Pseudo-Codice, oppure
Diagramma di flusso
Diagramma di Flusso

I diagrammi di flusso permettono di
descrivere in modo grafico le azioni che
costituiscono un algoritmo e il loro flusso
di esecuzione.

Ogni azione elementare è rappresentata da un
blocco.

Esistono 4 tipi di blocchi
Diagrammi di flusso (1)

Istruzioni di inizio e fine
Inizio
Fine
In degree: 0
Out degree: 1
In degree: 1
Out degree: 0
Diagrammi di flusso (2)

Operazioni di lettuta (input) e scrittura
(output)
Leggi Dato
In degree: 1
Out degree: 1
Scrivi Dato
In degree: 1
Out degree: 1
Diagrammi di flusso (3)

Istruzioni imperative (azioni oppure
operazioni)
In degree: arbitrario
Out degree: 1
Calcola: 10+2
Connettori
I singoli diagrammi devono essere uniti
tramite i connettori.
 L’esecuzione delle istruzioni deve essere
fatta sequenzialemente, ovvero sequendo
i connettori.


Quando si scrive l’algoritmo bisogna fare molta
attenzione alla direzione del flusso di
esecuzione.
Istruzione di Assegnamento

Una variabile numerica è una entità caratterizzata da


Un nome, e
Un valore (contenuto)


Una costante numerica è una entità caratterizzata da


Un nome, e
Un valore (contenuto)


Non può cambiare nel tempo
Un’espressione è una combinazione di operatori aritmetici,
costanti e variabili che può essere calcolata generando un singolo
valore numerico


Può cambiare nel tempo
ES: X,
X+1
Istruzione di assegnamento: “”


VariabileEspressione
ES: Z3 ZX+3
X+(Y*3)
Esempio

Descrivere mediante diagrammi di flusso,
un algoritmo che calcoli la somma di due
numeri letti in input
Diagramma di flusso: Somma
Inizio
ZX+Y
Leggi X
Scrivi Z
Leggi Y
Fine
Esempio

Descrivere, mediante diagrammi di flusso,
un algoritmo che scambi i valori di due
variabili lette in input.
Diagramma di flusso: Somma
Inizio
Leggi X
AuxY
Scrivi Y
Scrivi X
YX
Fine
Leggi Y
XAux
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

Digrammi di flusso (4)

Istruzioni condizionali
In degree: arbitrario
Out degree: 2
Condizione
Falso
Vero
I connettori Out
Sono etichettati
Esempio

Descrivere mediante diagramma di flusso,
un algoritmo che determini il massimo tra
due numeri letti in input
Diagramma di Flusso: Max
Inizio
Leggi X
X>Y
Vero
Scrivi X
Falso
Scrivi Y
Leggi Y
Fine
Esempio

Descrivere mediante diagrammi di flusso,
un algoritmo che determini se un numero
è pari o dispari
Diagramma di flusso: Pari o Dispari
Inizio
Leggi X
Dividi X per 2
Vero
Resto=0
Scrivi
N è pari
Falso
Scrivi
N è dispari
Fine
Supponiamo lo 0 sia un numero pari
Esempio

Descrivere, mediante diagramma di flusso,
un algoritmo che scriva 10 volte “Ciao
Mondo!”
Diagramma 10 volte “Ciao Mondo”
Vero
Inizio
X1
Scrivi
“Ciao Mondo!”
X<=10
XX+1
Falso
Fine
-
Ciclo
Ripetizione
Fino a Quando
Per 10 Volte
Strutture di controllo
Input
Input
Input
No/Si
No/Si
Si/No
Si/No
Si/No
No/Si
While
Output
Do-While
Output
If-else
Output
Risoluzione di un problema: esecuzione
Automatica
L’uomo descrive l’algoritmo che la
macchina deve seguire per risolvere il
problema (ad esempio con i Diagrammi
di flusso)
Problema
Algoritmo
Programma
Linguaggio Macchina
Input
Macchina
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)
Output
Risoluzione di un problema: esecuzione
Automatica
L’uomo descrive l’algoritmo che la
macchina deve seguire per risolvere il
problema (ad esempio con i Diagrammi
di flusso)
Problema
Algoritmo
Programma
Linguaggio Macchina
Input
Macchina
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)
Output
Dall’Algoritmo al programma

Dato un algoritmo ottengo il
corrispondente programma attraverso la
fase di traduzione



Fase di scrittura di un algoritmo in un insieme
ordinato di istruzioni scritte in un qualche
linguaggio di programmazione, che specificano
le azioni che il calcolatore deve svolgere
Il testo del programma è scritto in accordo alla
sintassi e alla semantica del linguaggio di
programmazione scelto
Il programma, a seconda del linguaggio, verrà
compilato ed eseguito o interpretato (esistono
vie di mezzo)
Linguaggi di Programmazione
Notazione formale per l’implementazione
degli algoritmi
 Linguaggio artificiale
 Compromesso tra uomo-macchina

Sintassi e Semantica

Sintassi: Insieme delle regole per la
costruzione di frasi corrette

Semantica: Insieme di regole per
l’attribuzione di un significato alle frasi

Una frase può essere sintatticamente
corretta e tuttavia non avere significato
Livelli di un linguaggio

Rappresenta la posizione del linguaggio fra
il programmatore e la macchina
Linguaggi Macchina
Linguaggi Naturali
C/C++
Assembly
Linguaggio Macchina

Insieme delle operazioni elementari
eseguibili da un calcolatore



Diverse per ogni processore
Codice Numerico (binario)
Difficoltà di utilizzo e comprensione
Assembly

Sostituzione del codice binario con simboli
mnemonici
Start: Mov AX, BX
CMP AX, 12h
MUL BX, 10d
:
:
Linguaggi ad alto livello (di astrazione)
Linguaggi macchina e corrispondenti
assemblylinguaggi a basso livello
 Linguaggi ad alto livello





Mascherano il calcolatore
Maggiore leggibilità e comprensibilità
Necessita di traduzione
portabilità
Tipi di linguaggi ad alto livello

Esistono differenti tipi di linguaggi ad alto
livello





Imperativi
Logici
Funzionali
Orientati agli ogetti
Ognuno provvede le forme espressive
appropriate per problemi specifici
Linguaggio Imperativo
Diretta evoluzione del linguaggio macchina
 Elenco di istruzioni da eseguirsi in
sequenza






Operazioni di trasferimento
Operazioni Aritmetiche
Operazioni di controllo di flusso
Concetto di variabile
Macchina di von Neumann
C, Fortran, Pascal, Basic
Linguaggio C (Cenni)


Il linguaggio C venne sviluppato nel 1973 da
Ritchie, dell’AT&T Bell Labs, come linguaggio di
programmazione di sistema
Il linguaggio doveva essere



Un linguaggio di livello sufficientemente alto per
garantire ai programmi leggibilità e mantenibilità
Un linguaggio sufficientemente semplice da stabilire una
corrispondenza immediata con la macchina sottostante
Nel 1983, lAmerican National Standards Institute
(ANSI), costituì una commissione per la
standardizzazione del linguaggio; La versione
finale dello standard fu approvata nel 1989.
Elementi di Base del Linguaggio C

Il nucleo del linguaggio si fonda su un set ricco di:

Tipi di dati



Strutture di controllo



Selezione (strutture decisionali)
Iterative
Costrutti di decomposizione del programma



Base
Derivati
Funzione
Unità di compilazione(Modulo)
Librerie Standard di corredo al compilatore





Standard di I/O
Gestione di stringhe
Gestione Dinamica della Memoria
Funzioni Matematiche
Altre
Componenti base di un Programma

Dichiarazione di variabili





Statement







In C le variabili devono essere dichiarate prima di essere
utilizzate. Le dichiarazioni specificano il tipo e il nome di una
variabile
Es: int i;
E’ sempre consigliabile inizializzare le variabili
ES: i=0;
Esempi:
printf(“Hello World!”);
scanf(…);
result = sum(n);
return 0;
int i;
Il ; è un terminatore di statement; deve essere aggiunto
alla fine di ogni statement
Componenti base di un Programma

Commenti


Parentesi Graffe


Si affiancano a dichiarazioni di variabili o parti
del programma per indicarle lo scopo e
l’utilizzo (leggibilità e mantenimento delle
applicazioni)
Delimitano i blocchi di codice e costituiscono il
costrutto primario di raggruppamento
Costanti

#define max 10
Componenti base di un Programma

Prototipi di funzione



Dicono al compilatore quale sarà il formato di
una funzione
Devono apparire prima che la funzione sia
utilizzata
Un prototipo di una funzione è diverso dalla
sua definizione:



Il primo descrive l’interfaccia della funzione
La seconda descrive l’implementazione della funzione
Definizione di Funzione

Codifica l’algoritmo corrispondente alla funzione
(solitamente una subroutine)
Componenti base di un Programma

Le librerie standard contengono delle funzioni utili
per il programmatore

printf(“Hello World”);


Per ogni gruppo di funzioni (es: quelle di I/O)
esiste un file sorgente, chiamato file header
contenente le informazioni necessarie per
utilizare le funzioni


Appartiene alla libreria di I/O
stdio.h
La funzione appartenente ad una libreria può
essere utilizzata includendo un file header in un
programma (preprocessore)

#include <stdio.h>
La funzione main

Ogni programma eseguibile deve
contenere una funzione speciale chiamata
main(), che indica il punto da cui inizia il
programma
Il Primo Programma
#include <stdio.h>
#define ok 1
#define nok 0
int main()
{
int i;
i=10;
printf(“Valore della variabile: %d”,i);
return val;
}
Il Primo Programma
#include <stdio.h>
#define ok 1
#define nok 0
Definizione delle Costanti
Definizione delle Variabili
i=10;
printf(“Valore della variabile: %d”,i);
return val;
}
Corpo del programma
int main()
{
int i;
Inclusione delle librerie
I Tipi: Scalari

I tipi fondamentali sono





char: rappresenta uno dei caratteri del set locale
int: un intero, il cui valore dipende dall’ampiezza degli
interi sulla macchina utilizzata
float: floating-point in singola precisione
double: floating point in doppia precisione
Le dimensioni sono contenute nei file limit.h e
float.h




char: 1 byte
int: 4 byte
float: 4 byte
double: 8 byte
Altri tipi

Enumerativi


:
:
:
Enum {red, green, blue} color;
Tipi definiti dal programmatore
Strutture di Controllo

if-else


switch


Vari casi di scelta
while


Scelta in base ad una condizione
Ciclo secondo il valore di una condizione
for

Ciclo ripetuto esattamente un numero n di
volte
if - else
Input
No/Si
Si/No
opzionale
if (espressione_bool)
{
istruzione1;
istruzione2;
:
}
else
{
istruzione1;
istruzione2;
:
}
If-else
Output
L’espressione viene valutata in esecuzione;
Se vera viene eseguito il blocco if altrimenti viene eseguito il blocco else
if – else: esempio
#include <stdio.h>
int main()
{
if (n>0)
{
if (a>b)
z=a;
else
z=b
}
else
{
z=a+b;
}
printf(“valore della variabile z: %d”,z)
}
switch
switch (espressione-variabile)
{
case espressione-costante:
{
istruzioni
break;
}
case espressione-costante:
{
istruzioni
}
}
case espressione-costante:
{
istruzioni
break
}
default:
{
istruzioni
break;
}
Se il valore di espressione-variabile
coincide con uno di quelli dei vari casi,
allora l’esecuzione inizia dal blocco di
istruzioni relative a quel caso
Se il valore di espressione-variabile non
coincide con quello dei vari casi
vengono eseguire le espressioni di
default
L’istruzione break provoca l’uscita
immediata dallo switch. Se non
presente, l’esecuzione dei casi è
sequenziale
switch: esempio
switch (n)
{
case 0:
{
}
case 1:
{
printf(“zero”);
break;
printf(“uno”);
break;
}
default:
{
printf(“numero maggiore di uno”);
break;
}
}
while
while (espressione_bool)
{
istruzioni
}
L’espressione viene valutata; se il suo valore è
vero viene eseguito il blocco di istruzioni e viene
valutata nuovamente la condizione
Se l’espressione è falsa, l’esecuzione del
Programma riprende dalla prima istruzione dopo
il while
Input
Si/No
While
Output
for
for(espr_1; espr_2; espr_3)
{
istruzioni
}
Input
count
Falso
Vero
istruzioni
In generale:
espr_1 è un assegnamento
espr_2 è una espressione relazionale
espr_3 incrementa la variabile “contatore”
Inc; count
Output
for: esempio
for(count=1, n=0; count<3; count=count+1)
{
printf(“ciclo: %d”, count);
n=n+1;
printf(“valore di n: %d”, n);
}
Esempio: Fattoriale di un Numero

L’algoritmo si basa sulla proprietà del
fattoriale


N!=N*(N-1)!= N*(N-1)*(N-2)*…*2*1
Con un ciclo si scorrono tutti i numeri da 1
a N, ricalcolando il fattoriale ogni volta
secondo la formula precedente
Diagramma di flusso
Inizio
i<=n
falso
vero
Leggi N
Fatt=Fatt*i
i=i+1
Fatt=1
Scrivi Fatt
i=2
Fine
Codice del programma
#include <stdio.h>
int main()
{
int i, n, fattoriale;
}
printf(“Numero: ”);
scanf(“%d”,&n);
fattoriale=1;
for(i=2; i<=n; i=i+1)
{
fattoriale=fattoriale*i;
}
printf(“Fattoriale di %d = %d\n”, n, fattoriale);
Risoluzione di un problema: esecuzione
Automatica
L’uomo descrive l’algoritmo che la
macchina deve seguire per risolvere il
problema (ad esempio con i Diagrammi
di flusso)
Problema
Algoritmo
Programma
Linguaggio Macchina
Input
Macchina
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)
Output
Risoluzione di un problema: esecuzione
Automatica
L’uomo descrive l’algoritmo che la
macchina deve seguire per risolvere il
problema (ad esempio con i Diagrammi
di flusso)
Problema
Algoritmo
Programma
Linguaggio Macchina
Input
Macchina
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 in codice
binario (ad esempio dal
compilatore)
Output
Riepilogo delle fasi di programmazione

1.
2.
3.
4.
5.
6.
Dato un problema
Individuare l’algoritmo
Scrittura/Modifica del programma
Compilazione
Esecuzione
Debug e ritorno al punto 2
Consegna Prodotto
Strumenti per la programmazione

1.
2.
3.
Dato un problema
Esperienza e Capacità
Editor
Compilatore
4.
5.
6.
Debugger
Editor
Strumento che permette al
programmatore di scrivere agevolmente
un programma
 Il codice sorgente del programma è un file
di testo (ASCII)
 Alcuni Editor sono orientati alla
programmazione (sintassi, rientri, …)

Compilatore

Strumento che dal programma sorgente
genera il linguaggio macchina





Controllo della sintassi
Segnalazione errori e anomalie
Ottimizzazione
Supporto sistema operativo
Non segnalano errori di run time
Debugger

Permette l’esecuzione controllata di un
programma




Esecuzione Passo a Passo
Ispezione dei dati
Breackpoint
Visualizzazione grafica strutture dati
Fine Modulo