Silvia Rossi - cogrobotics.unina.it · – Deitel H.M., Deitel P.J. – C Corso completo di ... –...

Lezione n.

Corso di Laurea:

Insegnamento:

Email Docente:

A.A. 2016-2017

Silvia RossiPrime nozioni di Programmazione

1

Informatica

Programmazione I

[email protected]

Informazioni: docente/corso

Programmazione I

Contatto: – [email protected]

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

INFORMATICAInformazione + automatica = Informatica• L’informatica è una disciplina nata dalla necessità di velocizzare

le operazioni di calcolo matematico e per gestire le informazioniautomatizzate.

• Hardware: parola inglese il cui significato letterale è“ferramenta” (da Hard=duro e Ware=merce).In riferimento al computer indica l'insieme di tutto ciò checompone fisicamente il computer, ovvero tutto ciò che si puòtoccare con mano: monitor, tastiera, hard-disk, ecc., inclusi i cavielettrici.

• Software: parola inglese Soft=morbido e Ware=merce, che, nellinguaggio informatico, indica la parte “invisibile” del computer,cioè l'insieme dei programmi ed istruzioni che guidano unelaboratore e che gli consentono di risolvere i problemi che glisono 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• …

SOFT

WAR

EProgrammi applicativi(DBs, word processors, …)

Compilatore(Linguaggi di Programmazione)

HARDWARE

Sistema OperativoUtilities, 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)

c1 ... cms1s2

sn

alfabetoistruzioni

s2=c3c1c5c1

azioni

...a1a2

an

...

A S

C


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 (PG) è l’insieme finito di istruzioni

corrispondenti alle azioni dell’algoritmo G– E esegue PG (E calcola PG) significa:

• memorizzare e interpretare la sequenza di istruzioni PG

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

G=a3a2a3a7a1a3

a1a2

an

...

PG=s3s2s3s7s1s3

s1s2

sn

...

A Salgoritmo

programma

esecutore

input

esegue


Un esempio di esecutore: un braccio meccanico che disegna poligoni

A = insieme di azionimeccaniche delbaccio meccanico

S = insieme di istruzioni

Input xOutput xAlza la pennaAbbassa la pennaRuota la penna verso destra di x gradiRuota la penna verso sinistra di x gradiAvanti la penna di x quadrettiIndietro la penna di x quadretti

AbbassaAlza

x

Avanti di xRuota verso destra di xx


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

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

PG

Input xInput yAbbassa la pennaAvanti la penna di y quadrettiRuota la penna verso destra di 90 gradiAvanti la penna di x quadrettiRuota la penna verso destra di 90 gradiAvanti la penna di y quadrettiRuota la penna verso destra di 90 gradiAvanti la penna di x quadretti

G = insieme di azioni di A che risolvono il problema

xy

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 = sassolinocomputare = tagliare

ALUUnità logicoaritmetica

UCUnità

Di controllo

Memoria

INPUT

istruzionidati

OUTPUT

Registri

Memoria principale

Memoria secondaria

Il calcolatore: hardware

18

TastieraMouse

RAMMem. Principale

HDMem. Secondaria

CDROMMem. Secondaria

Stampante

MonitorScheda AudioScheda Video

CPUCache (L1/L2)Mem. Primaria

Il calcolatore: la piramide di memoria

Dispositivi di input/outputTastiera, Mouse, Scanner, VideoCamera,

Device Remoti, etc.

Memoria secondariaHard Drives (Dischi, CDROM, Floppy),

Drive Removibili, Network

RAMFisica Virtuale

CacheL1L2

RegistriCPU

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 2n valori diversi

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

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

bits

byte

word

210 = 1024 = 1 Kilo 1KB = 210 bytes = 213 bits = 8 Kbit220 = 1048576 = 1 Mega 1MB = 220 bytes = 223 bits = 8 Mbit230 = 1073741824 = 1 Giga 1GB = 230 bytes = 233 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 1 0 1 1 0V0 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 1o byte fa accedere all’area di memoria contenente l’informazione

5883

Registro Indice

0 0 1 0 1 1 0 0DE5884

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 0D/I OPCODE

REGISTER/CTRL

MEM ADDRESS

CPU 14322

…

dati

istruzioni

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 simboli0 1

Il sistema ottale utilizza otto simboli0 1 2 3 4 5 6 7

Il sistema esadecimale utilizza sedici simboli0 1 2 3 4 5 6 7 8 9 A B C D E F

Rappresentazione

25


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 107x103 + 2x102 + 3x101 + 7x100

7x1000+ 2x100+ 3x10 + 7x17000 + 200 + 30 + 7 = 7237

Il calcolatore: rappresentazione dati

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

dove ciascun ai rappresenta un numero compreso fra 0 e p-1, an è la cifra più significativa e a0 la meno significativa.

«N»p = an, an -1, …, a1, a0 (numerale)


27

å=

-- ´=´+´++´+´=

n

i

ii

oo

nn

nnp papapapapaN

0

11

11 ...............

01210 107108105587 ´+´+´=

Il sistema decimale

å=

-- ´=´+´++´+´=

n

i

ii

oo

nn

nnp papapapapaN

0

11

11 ...............

01031104

10

1010)12832(

021121220321420521

2

´+´

=

=+++

=´+´+´+´+´+´

=

43

43

101011

Il sistema binario

43 : 2 = 21 con resto di 121 : 2 = 10 con resto di 110 : 2 = 5 con resto di 05 : 2 = 2 con resto di 12 : 2 = 1 con resto di 01 : 2 = 0 con resto di 1

43 = 101011

Conversione decimale-binario

0 1

BIT

0 0 0 10 1 0 1

BYTE

Numero di bit Combinazioni Totale2 22 43 23 84 24 16… … …7 27 128

8 28 256


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 25Maiuscole 25Numeri 10Punteggiatura 15Simboli 6Comandi 34Caratteri speciali 13

Totale 128


• Problema

• Algoritmo di risoluzione

• Programma

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

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

PG

Input xInput yAbbassa la pennaAvanti la penna di y quadrettiRuota la penna verso destra di 90 gradiAvanti la penna di x quadrettiRuota la penna verso destra di 90 gradiAvanti la penna di y quadrettiRuota la penna verso destra di 90 gradiAvanti la penna di x quadretti

G = insieme di azioni di A che risolvono il problema

xy

Problema

1. INPUT lato2. abbassa la penna3. vai avanti di lato quadretti4. ruota verso destra di 90 gradi5. vai avanti di lato quadretti6. ruota verso destra di 90 gradi7. vai avanti di lato quadretti8. ruota verso destra di 90 gradi9. vai avanti di lato quadretti10. ruota verso destra di 90 gradi

Con un linguaggio più ricco:

1. INPUT lato2. abbassa la penna3. ripeti 4 volte le seguenti istruzioni:4. ruota verso destra di 90 gradi5. vai avanti di lato quadretti

45

1) INPUT lato2) abbassa la penna3) vai avanti di lato

quadretti

Lato = 20???

A

A

Con un linguaggio più ricco (2):

1. INPUT lato2. abbassa la penna3. ripeti 4 volte le seguenti istruzioni:4. ruota verso destra di 90 gradi5. 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 : 21 12 : 20 6 : 20 3 : 21 1

11001

Silvia Rossi - cogrobotics.unina.it · – Deitel H.M., Deitel P.J. – C Corso completo di ... –...

Documents

Transcript of Silvia Rossi - cogrobotics.unina.it · – Deitel H.M., Deitel P.J. – C Corso completo di ... –...