Giovanni Farinella

Corso di RoboticaResidenza Universitaria Alcantara

20 Gennaio 2005

Modulo di Informatica:Introduzione alla programmazione

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 Ingresso Dati in Uscita

Operazioni sui dati

Dati In maniera semplificata possiamo dire che i dati

sono: Numeri

Interi, decimali; Testi

Sequenze Alfanumeriche Testi Formattati

Sequenze alfanumeriche con codici che ne condizionano la “apparenza”

Segnali digitali 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

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

EsecutoreInput Output

Algoritmo

Non è così facile come sembra! Per scrivere la giusta “sequenza di passi”

bisogna essere un bravo cuoco e un bravo costruttore!

Infatti…

Problema Risolutore Algoritmo

Ese

cuto

re

Processo di Esecuzione

… la risoluzione automatica prevedeuna notevole componente umana!!!

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 algoritmo1. Azioni eseguibili e non ambigue

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

2. Deterministico1. Fatto un passo, il successivo è uno ed uno solo, ben

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

3. Numero finito di passi4. Terminazione

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

2. Osservazione: la 3 non implica la 4

Esempio di non terminazione1. Si consideri il numero N2. Scrivere N3. Scrivere il numero successivo ad N4. Ripetere il passo precedente

Esempio di non terminazione

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)

F(X,Y)=

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)

Algoritmo

Programma

Linguaggio 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 dalcompilatore)

MacchinaInput

Output

Problema

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: 0Out degree: 1 In degree: 1

Out degree: 0

Diagrammi di flusso (2) Operazioni di lettuta (input) e scrittura

(output)

Leggi Dato Scrivi Dato

In degree: 1Out degree: 1

In degree: 1Out degree: 1

Diagrammi di flusso (3) Istruzioni imperative (azioni oppure

operazioni)

Calcola: 10+2

In degree: arbitrarioOut degree: 1

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)

Può cambiare nel tempo

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

ES: X, X+1 X+(Y*3)

Istruzione di assegnamento: “” VariabileEspressione ES: Z3 ZX+3

Esempio Descrivere mediante diagrammi di flusso,

un algoritmo che calcoli la somma di due numeri letti in input

Diagramma di flusso: Somma

Inizio

Leggi X

Leggi Y

ZX+Y

Scrivi Z

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

Leggi Y

AuxY

YX

XAux

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

Digrammi di flusso (4) Istruzioni condizionali

Condizione

Vero

Falso

In degree: arbitrarioOut degree: 2

I connettori OutSono 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

Leggi Y

X>Y

Scrivi Y

Scrivi X

Falso

Vero

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

Resto=0Scrivi

N è pari

ScriviN è dispari

Vero

Supponiamo lo 0 sia un numero pari

Falso

Fine

Esempio Descrivere, mediante diagramma di flusso,

un algoritmo che scriva 10 volte “Ciao Mondo!”

Diagramma 10 volte “Ciao Mondo”

Inizio

X1

X<=10Scrivi

“Ciao Mondo!”

Vero

Falso

Fine

XX+1

- Ciclo- Ripetizione- Fino a Quando- Per 10 Volte

Strutture di controllo

While Do-While If-else

No/Si

Si/No

Input

Output

Input

No/Si

Si/No

Si/No No/Si

Output Output

Input

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)

Algoritmo

Programma

Linguaggio 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 dalcompilatore)

MacchinaInput

Output

Problema

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)

Algoritmo

Programma

Linguaggio 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 dalcompilatore)

MacchinaInput

Output

Problema

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

Assembly

C/C++

Linguaggi Naturali

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

assemblylinguaggi 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 Base Derivati

Strutture di controllo Selezione (strutture decisionali) Iterative

Costrutti di decomposizione del programma 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

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;

Statement 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

Si affiancano a dichiarazioni di variabili o parti del programma per indicarle lo scopo e l’utilizzo (leggibilità e mantenimento delle applicazioni)

Parentesi Graffe 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”);

Appartiene alla libreria di I/O 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 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

int main(){

int i;

i=10;printf(“Valore della variabile: %d”,i);return val;

}

Inclusione delle librerie

Definizione delle Costanti

Corp

o d

el p

rogra

mm

a

Definizione delle Variabili

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

Scelta in base ad una condizione switch

Vari casi di scelta while

Ciclo secondo il valore di una condizione for

Ciclo ripetuto esattamente un numero n di volte

if - else

if (espressione_bool){

istruzione1;istruzione2;

:}else{

istruzione1; istruzione2;

:}

If-else

Si/No No/Si

Output

Input

L’espressione viene valutata in esecuzione;Se vera viene eseguito il blocco if altrimenti viene eseguito il blocco else

op

zion

ale

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)

}

switchswitch (espressione-variabile){

case espressione-costante:{

istruzionibreak;

}case espressione-costante:

{istruzioni

}case espressione-costante:

{istruzionibreak

}default:

{istruzionibreak;

}}

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: esempioswitch (n){

case 0: { printf(“zero”); break;}

case 1: { printf(“uno”); break;}

default: { printf(“numero maggiore di uno”); break;}

}

whilewhile (espressione_bool){

istruzioni}

While

Si/No

Input

Output

L’espressione viene valutata; se il suo valore èvero viene eseguito il blocco di istruzioni e vienevalutata nuovamente la condizioneSe l’espressione è falsa, l’esecuzione del Programma riprende dalla prima istruzione dopoil while

forfor(espr_1; espr_2; espr_3){

istruzioni}

Inc; count

count

Vero

Input

Output

Falso

istruzioni

In generale:espr_1 è un assegnamentoespr_2 è una espressione relazionaleespr_3 incrementa la variabile “contatore”

for: esempiofor(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

Leggi N

Fatt=1

i=2

i<=n

Fatt=Fatt*i

i=i+1

vero

falso

Scrivi Fatt

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)

Algoritmo

Programma

Linguaggio 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 dalcompilatore)

MacchinaInput

Output

Problema

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)

Algoritmo

Programma

Linguaggio 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 dalcompilatore)

MacchinaInput

Output

Problema

Riepilogo delle fasi di programmazione Dato un problema1. Individuare l’algoritmo2. Scrittura/Modifica del programma 3. Compilazione4. Esecuzione5. Debug e ritorno al punto 26. Consegna Prodotto

Strumenti per la programmazione Dato un problema1. Esperienza e Capacità2. Editor3. Compilatore4. 5. Debugger6.

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