Silvia Rossi

Lezione n.

Corso di Laurea:

Insegnamento:

Email Docente:

A.A. 2016-2017

Silvia Rossi

Prime nozioni di Programmazione

1

Informatica

Programmazione I

silvia.rossi@unina.it

Informazioni: docente/corso

Programmazione I

Contatto:

– silvia.rossi@unina.it

Orario di Ricevimento:

– Martedì: 14:00-15:00 – PRISCA Lab (Edificio 8b, livello -1)

Libri di testo consigliati:

– Deitel H.M., Deitel P.J. – C Corso completo di programmazione, ed. Apogeo

– Kernighan B., Ritchie D. – Linguaggio C, Pearson Education Italia

Online:

– http://www.federica.unina.it/corsi/programmazione-1-sci/

– Facebook: Programmazione I gr.2

– http://wpage.unina.it/silrossi/index.html

Informatica

Per definire cosa è l’informatica è necessario definire le seguenti nozioni.

Informazione

Rappresentazione Elaborazione

Algoritmo

4

• Informazione: notizia, dato o elemento che consente di avere conoscenza più o meno esatta di fatti, situazioni, modi di

essere.

• Dato: elementi di informazione costituiti da simboli che debbono essere elaborati.

Informazione

5

• In generale ogni rappresentazione è una funzione che associa ad ogni elemento una sequenza di

simboli.

• Per ogni rappresentazione, oggetti (numeri) distinti devono avere differenti rappresentazioni e la

rappresentazione di ogni oggetto deve essere unica.

• Le rappresentazioni usate sui calcolatori impiegano tutte sequenze finite di simboli, tali quindi da

rappresentare insiemi finiti di naturali.

Rappresentazione

Elaborazione

L’elaborazione è una trasformazione:

– Y=F(X) – dove:

• X è l’insieme di dati iniziali o “di ingresso”

• Y è l’insieme dei dati finali o “di uscita”

• F è una regola che fa corrispondere Y ad X

• La trasformazione F si può ottenere attraverso una o

più azioni elaborative (o passi di elaborazione), cioè

trasformazioni elementari che devono essere eseguite

per ottenere una trasformazione.

Algoritmo

L’algoritmo è una sequenza finita di azioni

elaborative che portano alla realizzazione di un compito.

Un algoritmo deve essere:

– Comprensibile – Corretto

– Efficiente

INFORMATICA

Informazione + automatica = Informatica

• L’informatica è una disciplina nata dalla necessità di velocizzare le operazioni di calcolo matematico e per gestire le informazioni automatizzate.

• Hardware: parola inglese il cui significato letterale è

“ferramenta” (da Hard=duro e Ware=merce).

In riferimento al computer indica l'insieme di tutto ciò che compone fisicamente il computer, ovvero tutto ciò che si può toccare con mano: monitor, tastiera, hard-disk, ecc., inclusi i cavi elettrici.

• Software: parola inglese Soft=morbido e Ware=merce, che, nel

linguaggio informatico, indica la parte “invisibile” del computer,

cioè l'insieme dei programmi ed istruzioni che guidano un

elaboratore e che gli consentono di risolvere i problemi che gli

sono posti.

9

HARDWARE

• tutto quello che quando non funziona puoi prendere a calci

SOFTWARE

• tutto quello che quando non funziona puoi

solo imprecare

Il calcolatore

Il calcolatore è una entità (reale o astratta) in grado di accettare dati in input, immagazzinarli ed

elaborarli per lo svolgimento di un certo compito

A tale fine il calcolatore esegue una sequenza ordinata di comandi (istruzioni)

Il software è l’insieme di istruzioni che il calcolatore deve eseguire per svolgere un certo compito

L’hardware è l’insieme delle componenti fisiche

necessarie al calcolatore per eseguire le istruzioni

Il calcolatore: il software

Programmazione : realizzazione di software per diversi scopi:

• Tradurre un linguaggio in un altro (compilatore)

• Gestire l’intero hardware (sistema operativo) o un suo dispositivo (driver)

• Aiutare a scrivere testi (word processor)

• Gestire banche dati

• …

SO FTW A R E

Programmi applicativi

(DBs, word processors, …)

Compilatore

(Linguaggi di Programmazione)

HARDWARE

Sistema Operativo

Utilities, drivers

Il calcolatore come esecutore

Esecutore - qualsiasi entità E (umana o non) in grado di:

– Riconoscere un insieme finito S di istruzioni (linguaggio) scritte con l’uso di simboli di un alfabeto (C)

– Interpretare ogni istruzione associando a essa

una ben definita, univoca e finita azione di un insieme finito di azioni (A)

c ₁ ... c _m s ₁

s ₂ s _n

alfabeto istruzioni

s

=c

c

c

c

azioni

...

a ₁ a ₂ a _n

...

A S

C

Il calcolatore come esecutore

Definizione di Calcolo di E

– Un algoritmo (G) è un insieme finito di azioni di A tali che eseguite una per volta risolvono un problema dato

• Le azioni sono estratte da A anche con ripetizioni ma in numero finito

– Un programma (P

) è l’insieme finito di istruzioni corrispondenti alle azioni dell’algoritmo G

– E esegue P

(E calcola P

) significa:

• memorizzare e interpretare la sequenza di istruzioni P

• eseguire, in modo deterministico e in un numero discreto di passi, la sequenza di azioni di G a esse associate (eseguire l’algoritmo)

G=a

a

a

a

a

a

a ₁ a ₂ a _n

...

P

=s

s

s

s

s

s

s ₁ s ₂ s _n

...

A S

algoritmo programma esecutore

input esegue

Il calcolatore come esecutore

Un esempio di esecutore: un

braccio meccanico che disegna poligoni

A = insieme di azioni meccaniche del baccio meccanico

S = insieme di istruzioni

Input x Output x Alza la penna Abbassa la penna

Ruota la penna verso destra di x gradi Ruota la penna verso sinistra di x gradi Avanti la penna di x quadretti

Indietro la penna di x quadretti

Abbassa Alza

x

Avanti di x Ruota verso destra di x

x

Il calcolatore come esecutore

• Un esempio di esecutore: un braccio meccanico che disegna poligoni

• P (problema) = disegnare un rettagolo di base x e altezza y

P

Input x Input y

Abbassa la penna

Avanti la penna di y quadretti

Ruota la penna verso destra di 90 gradi Avanti la penna di x quadretti

Ruota la penna verso destra di 90 gradi Avanti la penna di y quadretti

Ruota la penna verso destra di 90 gradi Avanti la penna di x quadretti

G = insieme di azioni di A che risolvono il problema

x

y

Lo pseudocodice

Lo pseudocodice è un linguaggio artificiale e non del tutto

formalizzato per esprimere le (macro)azioni che costituiscono l’algoritmo

I programmi scritti in pseudocodice non sono destinati al computer ma ai programmatori

– Strumento valido per mettere nero su bianco gli algoritmi – Un linguaggio semplice di rapida traduzione nel linguaggio di

programmazione da usare (C)

leggi(input) if condizione:

fai_qualcosa() else:

fai_qualcosaltro()

stampa(messaggio)

Il calcolatore: architettura

CPU

calculus = sassolino computare = tagliare

Unità logico ALU aritmetica

Unità UC Di controllo

Memoria

INPUT

istruzioni dati

OUTPUT

Registri

Memoria principale

Memoria secondaria

Il calcolatore: hardware

18

Tastiera

Mouse

Mem. Principale RAM

Mem. Secondaria HD CDROM

Mem. Secondaria Stampante

Monitor

Scheda Audio

Scheda Video

Cache (L1/L2) CPU

Mem. Primaria

Il calcolatore: la piramide di memoria

Dispositivi di input/output

Tastiera, Mouse, Scanner, VideoCamera, Device Remoti, etc.

Memoria secondaria

Hard Drives (Dischi, CDROM, Floppy), Drive Removibili, Network

Fisica

RAM

Cache

L1L2

Registri

CPU

Il calcolatore: memoria RAM

• Informazione

– Una sequenza di bit

– Rappresenta dati o istruzioni

• Oggi le architetture più diffuse sono a 32 (e 64) bit

– Un registro a n bit può contenere 2

valori diversi

• può indirizzare una memoria RAM di dimensione fino a 2

bytes

0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 bits

byte

word

2¹⁰ = 1024 = 1 Kilo 1KB = 2¹⁰ bytes = 2¹³ bits = 8 Kbit 2²⁰ = 1048576 = 1 Mega 1MB = 2²⁰ bytes = 2²³ bits = 8 Mbit 2³⁰ = 1073741824 = 1 Giga 1GB = 2³⁰ bytes = 2³³ bits = 8 Gbit

0 0 0 1 0 1 1 0 1 1 1 1 1 0 1 1

1 1 1 1 1 0 1 1 0 0 1 0 1 0 1 1 0 0 0 1V0 1 1 0 0 0 1 0 1 1 0 1

Il calcolatore: memoria RAM

Random Access Memory (RAM)

– Memoria volatile

– Contiene informazioni (istruzioni e dati) codificate in byte contigui

• L’indirizzo del 1^o byte fa accedere all’area di memoria contenente l’informazione

5883

Registro Indice

0 0 1 0D1 1 0 0

5884 E

5885

P C P

0 1 1

RAM

0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 Registro Prossima Istruzione

0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 D/I OPCODE

REGISTER/CTRL MEM ADDRESS

CPU 14322

…

dat i is tru zio ni

1 0 01 0 1

22

Rappresentazione dell’informazione

• In generale ogni rappresentazione è una funzione che associa ad ogni elemento una sequenza di simboli.

• Per ogni rappresentazione, oggetti (numeri) distinti devono avere

differenti rappresentazioni e la rappresentazione di ogni oggetto deve essere unica.

• Una rappresentazione è strettamente correlata al tipo di “mezzo”

impiegato.

23

Rappresentazione Numerica

• Ogni sistema di rappresentazione dei numeri deve essere caratterizzato:

– da una base costituita da un insieme di simboli diversi (cifre);

– da un sistema (insieme di regole) che permette di associare

ai diversi numeri le diverse stringhe di simboli.

24

Il sistema decimale utilizza dieci simboli per rappresentare un numero

0 1 2 3 4 5 6 7 8 9

Il sistema binario utilizza due simboli 0 1

Il sistema ottale utilizza otto simboli

0 1 2 3 4 5 6 7

Il sistema esadecimale utilizza sedici simboli

0 1 2 3 4 5 6 7 8 9 A B C D E F

Rappresentazione

25

Rappresentazione dell’informazione Il sistema numerico decimale è un sistema di tipo

posizionale ovvero:

Le cifre che compongono un numero cambiano il loro valore secondo la posizione che occupano

7237 (settemiladuecentotrentasette) in base 10 7x10

+ 2x10

+ 3x10

+ 7x10

7x1000+ 2x100 + 3x10 + 7x1

7000 + 200 + 30 + 7 = 7237

Il calcolatore: rappresentazione dati

Un generico numero N in base p è rappresentato da una sequenza di cifre (numerale)

dove ciascun a _i rappresenta un numero compreso fra 0 e p-1,

a _n è la cifra più significativa e a ₀ la meno significativa.

«N» _p = a _n , a _{n -1} , …, a ₁ , a ₀ (numerale)

Rappresentazione dell’informazione

27

å = -

- ´ + + ´ + ´ = ´

+

´

= ⁿ

i

i i

o o

n n

n n

p a p a p a p a p a p

N

0 1

1 1

1 ... ...

0 1

2

10 5 10 8 10 7 10

587 = ´ + ´ + ´

Il sistema decimale

å =

- ´ - + + ´ + ´ = ´

+

´

= ⁿ

i

i i

o o

n n

n n

p a p a p a p a p a p

N

0 1

1 1

1 ... ...

10 0 1 3

10 4

10

10 ) 10

1 2

8 32

(

2 0 1 1

2 2 1

2 3 0

2 4 1

2 5 0

2 1

2

´ +

´

=

= +

+ +

=

´ +

´ +

´ +

´ +

´ +

´

=

43

43 101011

Il sistema binario

43 : 2 = 21 con resto di 1 21 : 2 = 10 con resto di 1 10 : 2 = 5 con resto di 0 5 : 2 = 2 con resto di 1 2 : 2 = 1 con resto di 0 1 : 2 = 0 con resto di 1

43 = 101011

Conversione decimale-binario

0 1 BIT

0 0 0 1

0 1 0 1

BYTE

Numero di bit Combinazioni Totale

2 2 ² 4

3 2 ³ 8

4 2 ⁴ 16

… … …

7 2 ⁷ 128

8 2 ⁸ 256

Rappresentazione dell’informazione

Somma binaria

Nel sistema di numerazione in base 2 esistono due soli simboli: 0 e 1 e quindi quando si effettua

l'operazione 1 + 1, non si ha un unico simbolo per rappresentare il risultato, ma il risultato è 0 con il riporto di 1, cioè 10 (da leggere uno, zero e non dieci).

Le regole per effettuare l'operazione di somma di due cifre binarie sono riassunte di seguito:

• 0 + 0 = 0

• 0 + 1 = 1

• 1 + 0 = 1

• 1 + 1 = 0 con riporto di 1

La somma dei due numeri interi 10001 e 11011 è pari a:

10001 + 11011 = --- 101100

Somma binaria

Moltiplicazione binaria

Le regole per la moltiplicazione sono:

• 0 * 0 = 0

• 0 * 1 = 0

• 1 * 0 = 0

• 1 * 1 = 1

Quale è il maggiore?

A) 1 0 1 0 1 0 1 0 B) 1 0 0 1 0 1 0 0

C) 1 0 1 0 1 0 1 1

Rappresentazione dei Caratteri

Oltre che le lettere (maiuscole e miniscole)

dell’alfabeto inglese e le cifre decimali, ci si riferisce con il termine caratteri anche ad altri caratteri quali:

– i caratteri di interpunzione (la virgola, il punto, i due punti, ecc.)

– caratteri di varia origine (il meno, l’asterisco, le parentesi, ecc.)

Per rappresentare l’insieme di tutti i caratteri sono

sufficienti 7 bit.

• I caratteri che costituiscono un testo vengono codificati tramite sequenze di bit, utilizzando un codice di traduzione.

• Un codice di traduzione è una tabella che stabilisce una corrispondenza tra un carattere e la stringa di 7 bit che la rappresenta.

• Poichè esistono numerose possibilità di costruire le tabelle di traduzione, per motivi pratici è opportuno sceglierne una di riferimento e utilizzare sempre

quella prescelta (standard).

• L’uso di un codice di traduzione standard consente a sistemi diversi di comunicare tra loro.

Rappresentazione dei Caratteri

Codice ASCII

7 bit ® 128 combinazioni diverse di numeri Lettere dell’alfabeto 25

Maiuscole 25

Numeri 10

Punteggiatura 15

Simboli 6

Comandi 34

Caratteri speciali 13

Totale 128

Rappresentazione dell’informazione

• Problema

• Algoritmo di risoluzione

• Programma

• Un esempio di esecutore: un braccio meccanico che disegna poligoni

• P (problema) = disegnare un rettagolo di base x e altezza y

P

Input x Input y

Abbassa la penna

Avanti la penna di y quadretti

Ruota la penna verso destra di 90 gradi Avanti la penna di x quadretti

Ruota la penna verso destra di 90 gradi Avanti la penna di y quadretti

Ruota la penna verso destra di 90 gradi Avanti la penna di x quadretti

G = insieme di azioni di A che risolvono il problema x y

Problema

1. INPUT lato

2. abbassa la penna

3. vai avanti di lato quadretti

4. ruota verso destra di 90 gradi 5. vai avanti di lato quadretti

6. ruota verso destra di 90 gradi 7. vai avanti di lato quadretti

8. ruota verso destra di 90 gradi 9. vai avanti di lato quadretti

10. ruota verso destra di 90 gradi

Con un linguaggio più ricco:

1. INPUT lato

2. abbassa la penna

3. ripeti 4 volte le seguenti istruzioni:

4. ruota verso destra di 90 gradi

5. vai avanti di lato quadretti

45

1) INPUT lato

2) abbassa la penna 3) vai avanti di lato

quadretti Lato = 20???

A

A

Con un linguaggio più ricco (2):

1. INPUT lato

2. abbassa la penna

3. ripeti 4 volte le seguenti istruzioni:

4. ruota verso destra di 90 gradi 5. se lato è minore di 10 allora:

6. vai avanti di lato quadretti

Scrivere in pseudo codice un algoritmo per trasformare numeri decimali in numeri binari.

Esercizio

Determinare il passaggio dalla numerazione decimale alla binaria. Prendiamo in considerazione il numero 25 e

dividiamolo per 2 più volte: ogni volta il quoziente viene sempre diviso per 2 finché l’ultimo quoziente è minore del divisore e diverso da zero (e quindi 1).

Il numero in base 2 cercato è uguale all’ultimo quoziente seguito da tutti i resti presi in ordine inverso (le cifre evidenziate in neretto):

25 : 2 1 12 : 2 0 6 : 2

0 3 : 2 1 1

11001