Il Sistema Operativo Rappresentazione dell’Informazione Cenni di Programmazione

Il Sistema OperativoIl Sistema Operativo Rappresentazione dell’Informazione Rappresentazione dell’Informazione

Cenni di Programmazione Cenni di ProgrammazionePolitecnico di Milano

Facoltà del Design – Bovisa

Prof. Gianluca PalermoDipartimento di Elettronica e Informazione

[email protected]://home.dei.polimi.it/gpalermo

Cultura tecnologica del progetto 2

Politecnico di Milano

IndiceIndice

Il sistema operativo– Software di sistema e applicativo– Architettura di un sistema operativo– Classificazione dei sistemi operativi– Bootstrap– Panoramica dei principali sistemi operativi

• MS DOS, MS Windows, UNIX, Linux, BSD, Mac OS Rappresentazione dell’informazione

– Numeri– Caratteri e testi– Audio– Immagini– Video

Cenni di programmazione– Linguaggi di programmazione– Fasi della programmazione– Paradigmi di programmazione– Costrutti elementari di un linguaggio di programmazione



Software: di sistema e applicativoSoftware: di sistema e applicativo

Di sistema: controlla il comportamento del sistema stesso – il più importante dei software di sistema è il sistema

operativo:• controlla le risorse del sistema • fornisce la base su cui costruire tutti gli altri programmi

Applicativo: risolve i problemi dell’utente, appoggiandosi sullo strato fornito dal sistema operativo



Il sistema operativoIl sistema operativo

Con il termine sistema operativo si intende l’insieme di programmi e librerie che opera direttamente sulla macchina fisica...– ... mascherandone le caratteristiche

specifiche...– ... e fornendo agli utenti un insieme di

funzionalità di alto livello



Sistemi OperativiSistemi Operativi

MS-DOS MS-Windows (95, 98, 2000, XP, Vista) Unix

– Commerciali: Sun Solaris, IBM AIX, HP-UX,…– Linux– BSD

Mac OS– Mac OS X

Altri (IBM AS/400, Symbian,…)



Architettura di un S.O. - 1Architettura di un S.O. - 1

Un moderno S.O. è organizzato secondo una architettura “a strati” (a cipolla)

Ogni strato implementa una macchina virtuale più potente del precedente– Appoggiandosi alle funzionalità offerte dallo strato precedente

Tale approccio permette una chiara separazione tra interfaccia e implementazione delle diverse funzionalità

Ogni strato è costituito da un insieme di programmi e librerie– I meccanismi di chiamate tra livelli possono essere diversi

• chiamate a sottoprogrammi, interruzioni sincrone o asincrone, invio di messaggi a processi



Architettura di un S.O. - 2Architettura di un S.O. - 2

Macchina fisica

Gestore dei processi (nucleo)

Gestore della memoria

Gestore delle periferiche

Gestore del file system

Interprete dei comandi

Interfaccia grafica

Programmi utente

Gestori di risorse(kernel)

Interfacce utente



Il NucleoIl Nucleo

Il nucleo– Si appoggia direttamente sulla macchina fisica

– Effettua la gestione dei processi

– In un sistema multitasking realizza una macchina virtuale in cui ad ogni processo è assegnata un processore virtuale

– Comprende i principali programmi di risposta ad interruzione

– Realizza le primitive di sincronizzazione e scambio messaggi tra processi



Il nucleoIl nucleo

Memoriacentrale

Interfacciadelle

periferiche

Bus di sistema

Processorevirtuale

Processorevirtuale

Processorevirtuale

...

Disco

La macchina virtuale realizzata dal nucleo



Il gestore della memoriaIl gestore della memoria

Il gestore della memoria– Realizza le funzionalità di allocazione della

memoria• Supera i limiti della memoria fisica e mostra ai

processi uno spazio di memoria virtuale

– Partiziona la memoria tra i vari processi che la richiedono• Garantendo la protezione delle diverse zone di

memoria



Il gestore della memoriaIl gestore della memoria

La macchina virtuale realizzata dal gestore della memoria

Interfacciadelle

periferiche

Bus di sistema

Processorevirtuale ...

Disco

Processorevirtuale

Processorevirtuale

Memoriavirtuale

Memoriavirtuale

Memoriavirtuale...



Il gestore delle perifericheIl gestore delle periferiche

Il gestore delle periferiche– Maschera le caratteristiche fisiche delle periferiche

– Fornisce agli strati superiori un insieme di procedure di alto livello per l’accesso alle diverse periferiche

– Offre ad ogni processo la visibilità di un insieme di periferiche virtuali dedicate

– Gestisce, almeno in parte, i malfunzionamenti delle periferiche



Il gestore delle perifericheIl gestore delle periferiche

La macchina virtuale realizzata dal gestore delle periferiche

Interfacciaperiferiche

virtuali

Bus di sistema

Processorevirtuale

Disco

Memoriavirtuale

...Bus


virtuali

Processorevirtuale

Memoriavirtuale

Bus



Il gestore del file systemIl gestore del file system

Il gestore del file system– E’ responsabile della gestione delle periferiche

di massa• Hard disk• CD / DVD• Memory stick USB• ...

– Fornisce agli strati superiori un insieme di procedure per l’accesso al file system

– Garantisce la protezione nell’accesso ai file




Le funzioni di base che sono supportate da un file system sono– Il recupero di dati precedentemente

memorizzati– L’eliminazione di dati obsoleti– La modifica/aggiornamento di dati preesistenti– La copia di dati

• Tra supporti di memorizzazione diversi (ad es. da HD a CD)

• In cartelle diverse nello stesso supporto




I dati contenuti nella memoria di massa vengono strutturati e gestiti mediante una organizzazione in file

Un file è un contenitore logico identificato da un nome (filename)

I filename generalmente sono composti da due parti– ad es. curriculum_vitae.doc– Il filename vero e proprio (curriculum_vitae)– L’estensione (doc)




L’estensione è spesso associata al programma che ha generato il file e individua pertanto la tipologia del contenuto del file– .exe file eseguibili– .txt file di testo– .doc documenti di testo (MS Word)– .wav file audio– .bmp immagine in formato bitmap– ...

Ad ogni file sono poi associati dal sistema operativo altri dati– Data di creazione / modifica– Lunghezza del file (in byte)– Utenti/Gruppi che possono accedere ai file




I file vengono suddivisi in più contenitori logici, chiamati directory, cataloghi o cartelle (folders)

Le cartelle sono organizzate secondo una struttura ad albero

Il file system contiene una directory detta radice dell’albero che può contenere file o altre cartelle

Ciascun file è individuato univocamente dal suo nome completo o percorso assoluto– Ad es. D:\downloads\temp\002.part

Due file con lo stesso nome in due cartelle distinte, ad esempio– D:\Immagini\Compleanno\foto1.jpg– D:\Documenti\foto1.jpg

fanno riferimento a due file che in generale possono essere DIVERSI




D:

Documenti

Downloads

Incoming

Temp

...

...




La macchina virtuale realizzata dal gestore del file system


virtuali

Bus di sistema

Processorevirtuale

Memoriavirtuale

...Bus

File File...


virtuali

Processorevirtuale

Memoriavirtuale

Bus

File File...



L’interprete dei comandi e l’interfaccia L’interprete dei comandi e l’interfaccia graficagrafica

L’interprete comandi e l’interfaccia grafica– Costituiscono l’interfaccia verso l’utente

– Consentono l’interazione dell’utente con il s.o. e con i programmi applicativi in esecuzione• Permettono di accedere ai programmi conservati su

memoria di massa e mandarli in esecuzione– allocando la memoria necessaria e creando il processo

relativo

– Nel caso di un sistema multiutente forniscono ai diversi utenti la visione di una macchina virtuale dedicata



Una possibile classificazione dei Una possibile classificazione dei moderni S.O.moderni S.O. I moderni sistemi operativi possono essere

classificati in:– Sistemi monotask:

• Permettono l’esecuzione di un solo programma utente per volta (es. DOS)

• Il computer a disposizione del programma dall’inizio alla fine della sua esecuzione

• Coda dei job, gestita FIFO (first in, first out) e/o con priorità

– Sistemi multitask• Permettono l’esecuzione di più programmi utente

contemporaneamente• Classificazione ulteriore:

– Multitasking cooperativo (Windows 3.1, MacOS)– Multitasking preemptive (Windows 95/98/NT, Unix)

• Time sharing o meno



Svantaggi dei sistemi monoprocessore Svantaggi dei sistemi monoprocessore mono-taskingmono-tasking

Nessuna interazione utente-programma

Lentezza: la CPU non può essere usata da nessun processo mentre il programma in esecuzione svolge operazioni di I/O (molto piu’ lente di letture/scritture in Memoria)

Esempio: DOS è un SO monotasking; non si può fare niente altro mentre si formatta un floppy o si memorizzano dati su disco



Multitasking (time sharing)Multitasking (time sharing)

Ripartizione del tempo di CPU tra tutti i processi che la vogliono

Ogni job rimane in esecuzione solo per un quanto di tempo, poi l’esecuzione passa al prossimo job e il primo va in attesa Esecuzione globale più veloce

Durata del quanto di tempo tra 100 e 200 millisecondi granularità molto fine

A ciascun utente sembra di avere la CPU tutta per lui, solo più lenta



Stati di un processoStati di un processo

Processo in esecuzione

Processo in attesa

Processi pronti

Inizio esecuzio

ne

Selezione primo processo pronto e sua esecuzione

Termine quanto di tempo

Completamento operazione di I/O (evento esterno atteso)

Richiesta di operazione di I/O



AttesaAttesa

Se il processo richiede operazioni ad altri dispositivi (es. Operazioni di I/O), la CPU rimarrebbe inutilizzata – lo scheduler mette il processo in stato di attesa, – il dispatcher sceglie un nuovo processo tra i pronti dalla tabella,– quando l’operazione sarà finita, lo scheduler dichiarerà di nuovo

pronto il processo

Permette un utilizzo molto più efficiente delle risorse di elaborazione– Esempio:

• durante la digitazione di un documento di testo, l’utente compie molte pause per riflettere sul contenuto che sta scrivendo

• questo tempo è usato dal sistema per compiere altre operazioni in contemporanea (ad es. gestire la ricezione di e-mail)



Sistemi mono e multi-processoreSistemi mono e multi-processore

Time sharing in sistemi mono-processore: multi-tasking (più programmi in esecuzione con una sola CPU)

Sistemi multiprocessore: – le varie CPU possono lavorare

contemporaneamente su job diversi – ciascuna CPU opera in multi-tasking



Bootstrap: avvio del SOBootstrap: avvio del SO

All’inizio, la CPU ha in indirizzo fissato nel registro contatore di programma, che punta all’indirizzo nella ROM (Read Only Memory) ove inizia il programma di bootstrap che è sempre memorizzato lì

L’esecuzione del programma di bootsrap trasferisce il kernel del Sistema Operativo da una parte prestabilita della memoria di massa (hard-disk, floppy-disk, CD-Rom,…) in memoria principale

Quindi l’esecuzione prosegue con un salto all’area di memoria principale contenente il Sistema Operativo (che quindi viene mandato in esecuzione)

Tra le prime operazione del kernel del Sistema Operativo vi sono tipicamente quelle di caricamento di altri componenti software:– driver delle periferiche installate– programmi di sistema lanciati automaticamente all’avvio



BootstrapBootstrap



MS-DOSMS-DOS

Sviluppato dalla Microsoft nel 1981 per il PC IBM

Adottato da altri con PC IBM-compatibili

Molto limitato: – mono-utente, – mono-tasking

Circa 50 comandi per il SO:– DIR per vedere il contenuto di una directory– COPY per copiare file– DEL per cancellare un file– REN per cambiare il nome a un file– CD per muoversi in un altra directory– MD per creare nuove directory– RD per cancellare directory– Nome file: per eseguire il file (se eseguibile)– …



MS Windows – Elementi principaliMS Windows – Elementi principali

Interfaccia grafica Mouse che sposta un

cursore Cut & paste (copia e

incolla) Drag & drop (trascina e

lascia) Icone associate a file,

directory, dischi, … Directory come cartelle Pulsanti Finestre: cornici con

strumenti Menu di comandi



Breve storia di windows 1/2Breve storia di windows 1/2

Nel 1980 la Microsoft era una piccola società con 40 dipendenti, che fatturava 8 milioni di dollari.

Bill Gates venne contattato dall'IBM, che in quel periodo dominava il mercato degli elaboratori mainframe ed aveva appena iniziato la realizzazione di un personal computer, per scrivere un nuovo sistema operativo.

Nasce così l'MS DOS ed esplode il boom del computer per tutti. Due anni dopo Bill Gates annuncia la nascita di una prima versione di

Windows (1982). Non è un sistema operativo, ma una semplice interfaccia grafica attaccata al DOS molto rozza. Gli utenti cominciano a prendere confidenza con questa nuova dimensione.

A maggio, nel 1990, viene lanciato Windows 3.0 e un anno dopo esce Windows 3.1.

Nel '94 il fatturato è di 4,65 miliardi di dollari. Nel '95 viene lanciato Windows 95 e i dollari salgono a quasi 6 miliardi.

Internet Explorer comincia ad insidiare la posizione di leader tra i browser di Netscape.

Infine nel '98 esce la nuova versione di Windows (Windows 98) e nel frattempo la crescita del sistema operativo di rete, Windows NT, si consolida fino a creare serie minacce a ben più blasonati sistemi.



Breve storia di windows 2/2Breve storia di windows 2/2

Il successore di windows NT è Windows 2000. Windows 2000 compare in due versioni: la Professional e la Server. La prima è la soluzione ideale per applicazioni desktop mentre la seconda per la gestione e l’amministrazioni di reti, domini, ecc.

Con il nuovo millennio si registra l’uscita del nuovo Windows Millennium Edition (ME), praticamente un Windows 98 SE rivisto nella grafica, potenziato a livello di funzioni multimediali e nel quale fa la sua definitiva scomparsa il buon vecchio DOS.

Alla fine del 2002 viene presentato Windows XP nelle versioni Home, Professional e Server. La prima prenderà il posto di Windows ME mentre le altre due sostituiranno le analoghe versioni di Windows 2000.

Windows XP presenta un’interfaccia completamente ridisegnata, un ottimo supporto alle periferiche attualmente sul mercato e una grande supporto ai prodotti multimediali non ultimi i videogame grazie all’integrazione diretta delle DirectX.

Windows XP è presente sul mercato anche nella versione a 64 bit per processori Alpha.

Nel 2006 è stata rilasciato Windows Vista. Tra le principali novità: pieno supporto dei processori a 64 bit (funziona però anche a 32 bit); nuovo motore per l’interfaccia grafica; funzionalità avanzate di ricerca dei documenti archiviati; maggiore protezione rispetto agli attacchi informatici.



UnixUnix Sistema Operativo:

– multi-utente, – multi-tasking, con time-sharing

Nato negli anni ’60 con un progetto congiunto AT&T e MIT

Concepito per poter funzionare su diverse piattaforme hardware con adattamenti limitati

Interprete dei comandi: shell– testuale– più di 300 comandi, con opzioni

Disponibilità di interfaccia grafica (finestre, mouse, etc.) messa a disposizione da un insieme di moduli separati (sistema X Window)



LinuxLinux

Linux è una delle molte varianti di Unix con la peculiarità di essere open source (= il cui codice sorgente è liberamente disponibile)

La sua nascita è dovuta in parte alle restrizioni imposte da AT&T all’uso di del codice sorgente di UNIX per la didattica:– hanno indotto Andy Tanenbaum allo sviluppo di MINIX, un

implementazione di UNIX per scopi didattici– MINIX ha ispirato Linus Torvalds a realizzare una propria

implementazione del kernel UNIX – Il kernel sviluppato da Linus è stato combinato con una suite di

programmi UNIX, sviluppati nell’ambito del progetto GNU (iniziativa che ha originato il movimento open source), per formare la prima distribuzione di Linux e renderla disponibile su Internet come software open source

Oggi esistono innumerevoli distribuzioni di Linux, distinte per diverse combinazioni di kernel, interfacce grafiche (le più note sono Gnome e KDE) e programmi di utilità.



LinuxLinuxGnome

KDE



BSDBSD

BSD è un’altra versione open source del sistema operativo Unix, in questo caso nata alla University of California, Berkeley (USA)

Ritenuto più stabile di Linux (anche grazie ad un gruppo di sviluppo più ristretto, quindi più controllabile) ma il numero di applicazioni disponibili è più ristretto (principalmente applicazioni per i server)

Oggi esistono 4 distribuzioni principali di BSD:– 3 distribuzioni free: FreeBSD, OpenBSD, NetBSD– 1 distribuzione a pagamento, all’interno del

Sistema Operativo Apple MAC OS-X



MAC OS-XMAC OS-X

MAC OS-X è l’ultima generazione di S.O. per i personal computer prodotti da Apple

Abbandonato il precedente sistema operativo Apple ha costruito la nuova generazione del proprio S.O. a partire da una variante di BSD, chiamata Darwin, che rimane open source

A questo nucleo, Apple ha aggiunto componenti proprietari, dall’interfaccia grafica (Aqua) ad una suite di applicazioni e utilities.

Architettura MAC OS-X

Kernel, gestori di risorse e servizi di

base

GUI

Applicazioni



IndiceIndice



– Numeri– Caratteri e testi– Immagini– Video– Suoni




Codifica posizionale dei numeri: il sistema Codifica posizionale dei numeri: il sistema arabicoarabico

Il sistema di numerazione arabico sfrutta una codifica posizionale– Ogni cifra assume un valore particolare a seconda della

posizione assunta all’interno del numero– Esempio:

01 è diverso da 10

Il sistema arabico usa 10 cifre– Si parla di numerazione in base 10

Il valore di una cifra all’interno di un numero è pari a: x 10n

dove n è la posizione occupata dalla cifra all’interno del numero (si conta da destra partendo da 0)– Esempio:

1257 = 7 x 100 + 5 x 101 + 2 x 102 + 1 x 103



Codifica dati e istruzioniCodifica dati e istruzioni

Algoritmi = istruzioni + dati. Per scrivere un programma che descriva

un algoritmo è necessario rappresentare istruzioni e dati utilizzando un formato che il calcolatore sia in grado di:– Memorizzare– Elaborare– Trasmettere




Alfabeto dei simboli– Esempio: cifre 0,1– Esempio: cifre 0,1, 2, …, 9, separatore decimale (,),

separatore delle migliaia (.), segno positivo (+) e negativo (-).

Regole di composizione (sintassi) che definiscono le sequenze di cifre (parole) ammissibili:– Esempio: 1.234,5 è la rappresentazione di un numero

reale.– Esempio: 1,23,45 non lo è.




Codice (semantica): insieme di regole che ad ogni configurazione ammissibile associa un’entità di informazione – 1.234,5 = 1 x 103 + 2 x 102 + 3 x 101 + 4 x 100 + 5 x 10-1

– 1,23,45 = ?

Lo stesso alfabeto può essere utilizzato con codici diversi:– 123,456 = 1 x 102 + 2 x 101 + 3 x 100 + 4 x 10-1 + 5 x 10-2 + 6 x

10-3 (IT)– 123,456 = 1 x 105 + 2 x 104 + 3 x 103 + 4 x 102 + 5 x 101 + 6 x

100 (UK)



Codifica binaria dell’informazioneCodifica binaria dell’informazione

Il calcolatore utilizza un alfabeto binario: usiamo dispositivi elettronici digitali in grado di assumere due solo stati: acceso/spento, ON/OFF, 1/0, VERO/FALSO.

Un alfabeto binario non limita le funzionalità di un calcolatore.

Il simbolo o cifra binaria si indica con bit (da Binary digIT): quantità d’informazione che si ottiene selezionando una configurazione da un insieme che ne contiene due.

La risposta SI oppure NO a una domanda porta 1 bit di informazione.




Il calcolatore tratta diversi tipi di dati (numeri, caratteri, ecc.) tutti rappresentati con la codifica binaria.

Problema: assegnare un codice univoco a tutti gli oggetti compresi in un insieme predefinito.

Esempio: associare un codice binario ai giorni della settimana.




Quanti oggetti diversi posso codificare con parole binarie composte da k bit?– 1 bit: 21 = 2 stati (0, 1) 2 oggetti– 2 bit: 22 = 4 stati (00, 01, 10, 11) 4 oggetti– 3 bit: 23 = 8 stati (000, 001, 010, 011, 100, 101,

110, 111) 8 oggetti– …– k bit: 2k stati 2k oggetti




Se passiamo da una parola binaria di k bit ad una parola di k+1 bit si raddoppia il numero di oggetti che si possono rappresentare (2k+1).




Quanti bit mi servono per codificare N oggetti:– N 2k k log2 N k = log2 N

Ipotesi implicita: le parole di un codice hanno tutte la stessa lunghezza.



Definire un codiceDefinire un codice

Identificare due insiemi:•Insieme delle configurazioni

ammissibili;•Insieme degli oggetti da

rappresentare.Associare gli elementi dei due insiemi



EsempioEsempio

Associare una codifica binaria ai giorni della settimana.

Quanti bit devono avere le parole binarie usate per identificare i giorni della settimana (7 oggetti diversi)?– k = log2 7 = 3



EsempioEsempio

LUN MAR

VEN

GIO

MER

SAB DOM

Insieme degli oggetti da codificare

111 010

110011

001

101 100000

Insieme delle configurazioni ammissibili



EsempioEsempio

111 010

110011

001

101 100000

LUN MAR

VEN

GIO

MER

SAB DOM

Codice



ByteByte

bit rappresenta 2 stati: 0 oppure 1. Byte rappresenta 8 bit 28 = 256 stati KiloByte [KB] = 210 Byte = 1024 Byte 103 Byte MegaByte [MB] = 220 Byte = 1048576 Byte 106

Byte GigaByte [GB] = 230 Byte 109 Byte TeraByte [TB] = 240 Byte 1012 Byte …



Codifica binaria dei caratteriCodifica binaria dei caratteri

Quanti sono gli oggetti da rappresentare?– 26 lettere maiuscole– 26 lettere minuscole– 10 cifre– Circa 30 simboli d’interpunzione (, ; …)– Circa 30 caratteri di controllo (EOF, CR, …)

Totale circa 120 oggetti complessivi k = log2 120 = 7.



Codifica binaria dei caratteriCodifica binaria dei caratteri

Codice ASCII (American Standard Code for Information Interchange) utilizza 7 bit può rappresentare 27 = 128 caratteri detti caratteri ASCII Standard.

Codice ASCII esteso utilizza 8 bit (1 Byte) può rappresentare 28 = 256 caratteri detti caratteri ASCII estesi.– Tale codice comprende i caratteri ASCII standard e

alcuni caratteri semigrafici (cornici, lettere nazionali, simboli matematici, ecc.)

Codice UNICODE utilizza 16 bit (2 Byte)



Notazione posizionaleNotazione posizionale

Consideriamo i numeri interi assoluti (numeri naturali più lo zero).

Notazione posizionale in base b:Alfabeto: ci 0 … b-1

ck ck-1 … c1 c0 rappresenta:

N = ck x bk + ck-1 x bk-1 + … + c0 x b0 = (i=0… k) ci x b i

c0 bit meno significativo

ck bit più significativo



Notazione posizionaleNotazione posizionale

Basi più frequentemente utilizzate:base 2 : ci 0 , 1

base 8: ci 0 , 1, 2, 3, 4, 5, 6, 7

base 10: ci 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

base 16: ci 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F



Codifica binariaCodifica binaria

Numeri binari: base b = 2 Alfabeto binario: cifre ci 0 , 1

(ck … c1 c0)2 rappresenta: N = (i=0… k) ci x 2 i



Conversione binario Conversione binario decimale decimale

Dato il numero N espresso in base 2, basta riscriverlo secondo la notazione posizionale utilizzando cifre e potenze della base 10.

Esempi: N = 11012

N = 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20 = 1310

N = 1001012

N = 1 x 25 + 0 x 24 + 0 x 23 + 1 x 22 + 0 x 21 + 1 x 20 = 3710



Conversione decimale Conversione decimale binario binario Si calcolano i resti della divisione per due

finché il risultato di una divisione diventa zero:

Esempio: N = 2310

23 : 2 = 11 resto R0 = b0 = 1

11 : 2 = 5 resto R1 = b1 = 1

5 : 2 = 2 resto R2 = b2 = 1

2 : 2 = 1 resto R3 = b3 = 0

1 : 2 = 0 resto R4 = b4 = 1

2310 = 101112



Conversione decimale Conversione decimale binario binario

Esempio: N = 1810

18 : 2 = 9 resto R0 = b0 = 0

9 : 2 = 4 resto R1 = b1 = 1

4 : 2 = 2 resto R2 = b2 = 0

2 : 2 = 1 resto R3 = b3 = 0

1 : 2 = 0 resto R4 = b4 = 1

1810 = 100102



Codifica esadecimaleCodifica esadecimale

Utile per rappresentare sinteticamente i valori binari.

Numeri esadecimali: base b = 16 Alfabeto esadecimale:

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

(ck … c1 c0)16 rappresenta: N=(i=0… k) ci x 16 i



Conversione esadecimale Conversione esadecimale binario binario

Ogni cifra esadecimale corrisponde a quattro cifre binarie:0 [0000], 1 [0001], 2 [0010], 3 [0011]4 [0100], 5 [0101], 6 [0110], 7 [0111]8 [1000], 9 [1001], A[1010], B [1011]C [1100], D [1101], E [1110], F [1111]

E’ sufficiente ricordarsi (o derivare) la rappresentazione binaria su 4 bit dei numeri da 0 a 15 (ed eventualmente trascurare gli zeri più a sinistra).N = 35416

[0011] [0101] [0100] = 11010101002



04/21/23 Corso Informatica A - Allievi Gestionali - prof. C. Silvano 64

Conversione binario Conversione binario esadecimale esadecimale

Suddividere le cifre binarie (partendo da destra verso sinistra) tenendo conto che quattro cifre binarie corrispondono a una cifra esadecimale.N = 11010101002

[11] [0101] [0100] = 35416

N = 11001110012

[11] [0011] [1001]= 33916




Codifica binaria su n bitCodifica binaria su n bit

Con una sequenza di n bit si possono rappresentare 2n numeri interi assoluti da 0 a 2n-1.

Esempio: n = 4 bit 24 = 16 numeri interi assoluti da 0 a 15.

La lunghezza delle sequenze di bit adottate stabilisce il massimo numero che può essere rappresentato.




Codifica binaria su n+1 bitCodifica binaria su n+1 bit

Se passiamo da una sequenza di lunghezza n bit ad una sequenza di n+1 bit si raddoppiano i numeri che si possono rappresentare (2n+1).

Esempio: – n = 4 bit 24 = 16 numeri da 0 a 15.– n = 5 bit 25 = 32 numeri da 0 a 31.



Codifica dei caratteri e delle stringheCodifica dei caratteri e delle stringhe

Per la codifica dei caratteri e delle stringhe (sequenze di caratteri come parole e frasi) si sfruttano delle convenzioni che associano un valore numerico ad ogni carattere

Le più diffuse convenzioni sono:– La convenzione ASCII

• Sfrutta sette bit (otto nella versione estesa) per rappresentare un massimo di 128 (256) caratteri

– La convenzione UNICODE• Sfrutta 16 bit per rappresentare fino a 65.536 caratteri• Utile nel caso di alfabeti particolarmente complessi

quale quello cinese



Segnali audioSegnali audio

La pressione dell’aria varia in modo

sinusoidale con una frequenza di 440Hz

Esempio:

la nota LA



Analisi dei segnali audioAnalisi dei segnali audio

Tutti i suoni possono essere visti come la somma pesata di suoni semplici (sinusoidi)



Codifica audioCodifica audio

Onde sonore: segnali ‘continui’– Discretizzazione del tempo

• Campionamento: scelta di istanti in cui considerare il valore del segnale (discretizzazione)

– Discretizzazione delle ampiezze• Quantizzazione: codifica dei campioni con un numero

predefinito di bit



CampionamentoCampionamento

Si misura l’ampiezza del segnale analogico a intervalli regolari, ogni T secondi

T è detto periodo di campionamento (in secondi)

F = 1/T è detta frequenza di campionamento (in Hz)




Per segnali audio di tipo vocale (ad es. telefono), la frequenza di campionamento è tipicamente di 8 kHz

Per segnali audio musicali (ad es. CD audio), la frequenza di campionamento è tipicamente di 44.1 kHz

Un campionamento più fitto (ovvero con una frequenza di campionamento maggiore) consente di rappresentare i segnali analogici con maggiore fedeltà



QuantizzazioneQuantizzazione I campioni estratti con la quantizzazione

rappresentano le ampiezze con precisione arbitraria

Per poter essere rappresentato da un calcolatore, il valore dell’ampiezza deve essere espresso tramite un numero finito di bit

La quantizzazione suddivide l’intervallo dei valori ammissibili in 2k bit, dove k è il numero di bit per campione.

La figura mostra una quantizzazione a 3 bit / campione

001

000

010

011100



QuantizzazioneQuantizzazione

2 bit / campione 3 bit / campione




4 bit / campione 8 bit / campione




Esempio: brano musicale su CD– Frequenza di campionamento 44100 Hz – 16 bit / campione– 2 canali (destro e sinistro)– 2 x 16 x 44100 = 1411200 bit / sec 176 Kbyte /

sec– 1 canzone

• c.a. 5 minuti 176 Kbyte/s x 60 sec/min x 5 min c.a 52 Mbyte

– 60 min di musica • 176 x 60 x 70 c.a. 630 Mbyte

Un file mp3 di una canzone da 5 min sono c.a. 5 Mbyte fattore di compressione c.a. 10:1




L’accuratezza della ricostruzione dipende: – Da quanto sono piccoli gli intervalli di campionamento– Da quanti bit uso per descrivere il suono in ogni campione

nella fase di quantizzazione– Al solito… maggiore accuratezza significa maggior quantità

di memoria occupata!

Anche per i suoni si possono utilizzare tecniche (lossless o lossy) di compressione per migliorare l’occupazione di memoria della sequenza di campioni

Le tecniche più efficvaci (lossy) sfruttano le “debolezze” dell’orecchio umano– Es. MPEG-1/2 Layer 3 , detto anche MP3



Rappresentazione di immaginiRappresentazione di immagini

In generale le immagini sono un ‘continuo’ di informazioni– Non sono formate da sequenze di oggetti ben

definiti come le stringhe Bisogna quindi prima ‘discretizzarle’

ovvero trasformarle in un insieme di parti distinte che possono essere codificate separatamente come numeri

Tipologia:– Immagini scalari o raster, es. foto– Immagini vettoriali, es. un disegno geometrico



ImmaginiImmagini

Il calcolatore non può direttamente rappresentare in memoria informazione continua

Le immagini devono prima essere ‘discretizzate’ ovvero trasformate in un insieme di parti distinte, che possono poi essere codificate separatamente sotto forma di numeri

Azioni da fare:– Discretizzazione: scomposizione dell’immagine in

un reticolo di punti (pixel, picture element) – Quantizzazione: codifica di ogni pixel con un valore

numerico all’interno di un ben peciso intervallo




Rappresentare il disco seguente

Si sovrappone al disco una griglia

Si identificano i “quadratini” (in azzurro) che “discretizzano” il disco

Ogni quadratino si dice Pixel (da picture element)



RisoluzioneRisoluzione

Chiamiamo risoluzione dell’immagine la dimensione della griglia utilizzata per discretizzare l’immagine– es. 640x480

Aumentando la risoluzione (ovvero il numero dei pixel) e quindi diminuendo la dimensione del singolo pixel, la rappresentazione approssima meglio l’immagine originaria



Effetti della riduzione di risoluzioneEffetti della riduzione di risoluzione




Dopo aver discretizzato l’immagine occorre rappresentare ogni pixel con un numero

Tale numero dovrà rappresentare il colore associato al pixel, usando un certo range: si parla di quantizzazione

La rappresentazione ottenuta è nota come codifica bitmap

Nel caso di immagini in bianco e nero senza sfumature sono sufficienti due soli bit per ogni pixel:– 0 per rappresentare i pixel più bianchi– 1 per rappresentare i pixel più neri



Immagini b/n: Un esempioImmagini b/n: Un esempio

000000000000000000000000000000000011111111000000000000000010000010000000000000000010000100000000000000000010001000000000000000000010010000000000000000000010100000000000000000000011000000000000000000000010000000000000

Ogni pixel è rappresentato da un bit



Immagini in scala di grigi / coloriImmagini in scala di grigi / colori

Immagini in bianco e nero con sfumature– Si usa la rappresentazione in ‘toni di grigio’: un byte per

pixel, con 256 gradazioni di grigio per ogni pixel, o più byte per pixel, per avere più gradazioni possibili

Immagini a colori– Si usa la rappresentazione del colore secondo il modello

RGB (red, green,blu): sintesi additiva dei tre colori primari red, green, blu, ognuno con la propria codifica

– Profondità cromatica: numero di bit per ogni pixel (di norma 24, ovvero un byte per ogni colore)

RED 100 Codifica : 01000100GREEN 200 Codifica : 11001000BLU 200 Codifica : 11001000



Effetti della quantizzazioneEffetti della quantizzazione

4 bpp

2 bpp

1 bpp

3 bpp



Codifica di immaginiCodifica di immagini

La risoluzione e la profondità cromatica determinano la dimensione di memoria necessaria a memorizzare l’immagine– Esempio: 1024x768 pixel x 256 toni di grigio /

pixel = 1024x768 pixel x 8 bit / pixel = 768

Kbyte

Se l’immagine è a colori– Esempio 1024x768 pixel x 3 componenti / pixel x

256 toni / componente = 1024x768 pixel x 3 componenti / pixel

x 8 bit / pixel = 2304 Kbyte



Codifica di immaginiCodifica di immagini

In fase di codifica esiste la necessità di adottare tecniche di compressione per ottimizzare:– Occupazione di spazio di memoria– Velocità di trasmissione attraverso la rete

Tecniche di compressione senza perdita d informazione (lossless)– Reversibili

• Ad hoc per le immagini ad es. PNG• Applicabili a qualsiasi tipo di dato ad es. codifiche basate sulla frequenza

statistica dei dati: i dati più frequenti vengono codificati con sequenze di bit più brevi (ZIP)

Algoritmi con perdita di informazione (lossy)– Generalmente sono specifici di un certo campo e sfruttano le

caratteristiche degli oggetti da rappresentare per ‘buttare via’ informazione poco importanti

– Nel caso di immagini gli algoritmi usati nei formati GIF e JPEG sfruttano la caratteristica dell’occhio umano di essere poco sensibile a lievi cambiamenti di colore in punti contigui, e quindi eliminano questi lievi cambiamenti “appiattendo” il colore dell’immagine

– Generalmente è possibile specificare quanto siamo disposti a perdere attraverso alcuni parametri



Principali formati di compressione per Principali formati di compressione per immagini rasterimmagini raster

TIFF (Tagged Image File Format): uso di tag (etichette) descrittivi, 24 bit/pixel, compressione senza perdita

GIF (Graphics Interchange Format, Compuserve): più immagini nello stesso file, compressione senza perdita

PNG (Portable Network Graphics): compressione lossless, studiato per sostituire GIF (coperto da brevetti). Supporta solo grayscale e RGB. Studiato per trasmissione di immagini su Web

BMP (BitMaP, Microsoft e IBM): 1, 4, 8, 24 bit/pixel, compressione senza perdita (RLE)

JFIF (Jpeg File Interchange Format): compressione JPEG (meglio noto come “formato JPEG”)



Fattore di CompressioneFattore di Compressione

Esempio: – Fotocamera a 8 Mpixel c.a. 8.000.000 di pixel

Occupazione immagine non compressa a colori– 8.000.000 pixel x – 3 componenti / pixel x– 1 byte / componente =______________________– 24.000.000 byte c.a. 24 Mbyte

Salvo l’immagine in formato JPEG e ottengo un file mypicture.jpg di dimensione 2.4 Mbyte

Fattore di compressione dimensione originale / dimensione file compresso– 24 Mbyte / 2.4 Mbyte = 10:1



Esempio: Compressione jpegEsempio: Compressione jpeg

Compressione = 13.6:1

Compressione = 78:1

Compressione = 37:1

Compressione = 96:1

Cultura tecnologica del progetto


Immagine originale 8 bppImmagine originale 8 bpp

bpp bits / pixel



Immagine originale (dettaglio)Immagine originale (dettaglio)



Compressione JPEG 0.35 bppCompressione JPEG 0.35 bpp

Fattore di compressione– 8 bpp / 0.35 bpp = 22.8




Fattore di compressione– 8 bpp / 0.5 bpp = 16



Compressione JPEG 0.5 bpp (dettaglio)Compressione JPEG 0.5 bpp (dettaglio)



Immagini vettorialiImmagini vettoriali

Codifica simbolica di elementi grafici – es.:

Applicabilità limitata al mondo geometrico (non fotografie) Nessuna perdita di dettaglio ingrandendo o rimpicciolendo

l’immagine Formato principale: SVG (+ un vasto insieme di formati proprietari)

– forme geometriche, cioè linee costituite da segmenti di retta e curve e aree delimitate da linee chiuse;

– immagini della grafica raster e immagini digitali; – testi esplicativi, eventualmente cliccabili.

circle polyline …..



Formati vettoriali/bitmap (misti)Formati vettoriali/bitmap (misti)

PostScript (Adobe): misto bitmap-vettoriale, compressione con e senza perdita– È un linguaggio di descrizione di pagina utilizzato principalmente

nel mondo dell’editoria elettronica e del desktop publishing

EPS (Encapsulated PostScript): derivato da PostScript PDF (Portable Document Format): derivato da PostScript

– Utilizzato per rappresentare documenti 2D in modo indipendente dal dispositivo di rendering e della risoluzione dello stesso

– Ultima versione PDF 1.7 (2006)

– Contiene• Un sottoinsieme del linguaggio PS

• Un sistema per l’embedding/replacement dei font

• Un sistema per unire in modo strutturato contenuti di tipo differente (testo, immagini, font, grafica vettoriale)



Immagini in movimento: I VideoImmagini in movimento: I Video

Video: successione di immagini fisse (o frame) trasmesse con velocità sufficientemente elevata

Il movimento è rappresentato già in modo discreto nei media: con un numero abbastanza alto di fotogrammi fissi (15-30 al secondo) l’occhio umano percepisce il movimento come un continuo



Video interallaciato vs. progressivoVideo interallaciato vs. progressivo

Tradizionalmente, il segnale video di tipo televisivo utilizza un formato interallacciato

Prima vengono generate le righe pari, poi quelle dispari

Vengono generati 50 “semiquadri” al secondo

Nel formato progressivo, ogni frame è costituito sia dalle righe pari che da quelle dispari



Un esempio – video interallacciatoUn esempio – video interallacciato

Interallacciato (ad. es TV)– 720 punti / linea – 576 linee (288 linee pari, 288 linee dispari)– 50 semiquadri al secondo– 3 byte / pixel (RGB)– 720 x 288 x 50 x 3 = 31.104.000 byte / sec

c.a. 31 Mbyte/sec c.a. 250 Mbps

– 2h di film occupano (se non compressi) • 2x60x60x31 = 223.200 Mbyte c.a. 223 Gbyte

– Un DVD ha una capacità di c.a. 4.5 Gb avrei bisogno di un fattore di compressione pari a 223 / 4.5 = 50



Un esempio - video progressivoUn esempio - video progressivo

Progressivo (ad. es cellulare)– 320x240 pixel– 15 frame / secondo– 3 byte / pixel (RGB)– 320 x 240 x 15 x 3 = 3.456.000 byte / sec

c.a. 3.5 Mbyte/sec c.a. 28 Mbyte / sec– 1 minuto di video registrato occupa (se non

compresso)• 60x3.5 = 210 Mbyte



Codifica videoCodifica video

Potrei in principio codificare separatamente ogni fotogramma come immagine fissa

E’ la tecnica usata da molte fotocamere compatte, che salvano i filmati ripresi in formato Motion-JPEG (ogni frame è compressa con JPEG)

Si è in grado di ottenere rapporti di compressione dell’ordine 10-20 senza eccessiva perdita di qualità– Per mettere un film su DVD abbiamo bisogno di un

rapporto di c.a. 50...



Codifica videoCodifica video

Per ottenere rapporti di compressione più alti è necessario sfruttare la ridondanza temporale

Frame consecutivi in una sequenza di immagini sono simili l’uno all’altro

Codifico solo le differenze tra i frame successivi

E’ possibile ottenere rapporti di compressione di 50:1 fino a anche a 100:1 senza un degrado eccessivo della qualità



Immagine originale 1Immagine originale 1



Immagine originale 2Immagine originale 2



Differenza con pixel di destraDifferenza con pixel di destra



Differenza tra originaliDifferenza tra originali



Differenza a moto compensatoDifferenza a moto compensato



Standard di codifica videoStandard di codifica video

MPEG (Moving Picture Experts Group):– MPEG-1 Video CD– MPEG-2 TV digitale, DVD– MPEG-4 DivX, – H.264/AVC HD-DVD, Blue-ray DVD– Definisce anche la codifica dei dati audio (vedi slide seguenti) e la sincronizzazione con i dati video

ITU-T (International Telecommunication Union - Telecommunications Standardization Sector)– H.263 video-telefonia

AVI (Audio Video, Microsoft)– Formato “contenitore”. Può contenere audio/video compressi con formati diversi

1984 1986 1988 1990 1992 1994 1996 1998 2000 2002 2004

MPEGstandards

jointITU-T/MPEG

standards

ITU-Tstandards

H.261 H.263 H.263+ H.263++

H.262MPEG-2

H.264/AVC

MPEG-1 MPEG-4



IndiceIndice



– Numeri– Caratteri e testi– Immagini– Video– Suoni




Il linguaggio del calcolatoreIl linguaggio del calcolatore

Il calcolatore esegue programmi scritti in un opportuno linguaggio: il linguaggio macchina

Tale linguaggio differisce nei suoi dettagli da calcolatore a calcolatore– Da processore a processore



Le istruzioni macchinaLe istruzioni macchina

Un programma scritto in linguaggio macchina è formato da una sequenza di istruzioni appartenenti al set di istruzioni del particolare processore

Ogni istruzione è formata da:– Un codice operativo– Zero o più operandi

Tanto il codice operativo quanto gli operandi sono rappresentati nella memoria del calcolatore sotto forma di numeri binari

Data la difficoltà per l’uomo di interpretare numeri binari si usa l’assembler al posto del linguaggio macchina

codice operativo operando(i)



I programmiI programmi

Un programma consiste di due parti– La parte istruzioni contenente il codice del

programma– La parte dati costituita dalle celle di memoria

destinate a contenere i dati sui quali il programma opera

– Il processore esegue un programma dalla prima istruzione fino all’istruzione halt

LOAD 4, R1

LOAD 5, R2

SUB R1, R2

STORE R1, 7

50

40

0

1

2

3

4

5

istruzioni

dati



Programmi vs. processiProgrammi vs. processi

Un programma è un entità statica– Descrive semplicemente un algoritmo

Con il termine processo si indica un programma in esecuzione– Caratterizzato dal codice in esecuzione e da

uno stato• Lo stato di un processo è descritto dal valore assunto

dalla sezione dati del programma e dai valori assunti dai registri del processore

programma : processo = ricetta : attività del cucinare



Un esempio di programmaUn esempio di programma

Esempio: calcolare espressione (a + b) * (c + d)– Poni in memoria centrale, nelle celle 16, 17, 18 e 19 i valori di a, b, c, e

d;– Esegui l’addizione di a e b:

• Copia cella 16 in registro A• Copia cella 17 in registro B• Somma i due registri (l’operazione è eseguita dalla ALU)

– Immagazzina risultato (ora in registro A) nella cella 20– Esegui l’addizione di c e d:

• Copia cella 18 in registro A• Copia cella 19 in registro B• Somma i registri (l’operazione è eseguita dalla ALU)

– Esegui la moltiplicazione di (a + b) e (c + d):• Copia in registro B cella 20• Moltiplica il contenuto dei due registri

– Scrivi il risultato sul dispositivo di uscita:• Memorizza registro A, nella cella 20• Scrivi cella 20 nel registro dati della periferica

– Arresta l’esecuzione del programma



Contenuto della memoriaContenuto della memoria



Le istruzioni del programmaLe istruzioni del programma



Il linguaggio AssemblyIl linguaggio Assembly

La programmazione in linguaggio macchina è troppo complessa e noiosa per i programmatori

Al posto delle sequenze di numeri, è più comodo usare delle abbreviazioni simili all’inglese per rappresentare le operazioni elementari: Nasce il linguaggio Assembly

È necessario un programma (assembler) che traduca in linguaggio macchina i programmi scritti in linguaggio assembly



L’esempio in linguaggio assemblyL’esempio in linguaggio assembly

READ AREAD BREAD CREAD DLOADA A LOADB BADDSTOREA RISLOADA CLOADB DADD

LOADB RISMULSTOREA RISWRITE RISHALT

INT AINT BINT CINT DINT RIS



I linguaggi di alto livelloI linguaggi di alto livello

La programmazione in linguaggio macchina è improponibile per programmi di una certa complessità...

... e l’assembly oltre un certo limite non aiuta I linguaggi di alto livello facilitano la

programmazione dei calcolatori “Alto livello” = “Vicino al programmatore”

Ovviamente è necessario un programma(compilatore) che converta il programma scritto

nel linguaggio di alto livello in linguaggio macchina



L’esempio (frammento) in CL’esempio (frammento) in C

int a, b, c, d, ris;scanf("%d%d%d%d", &a, &b, &c, &d);ris = (a+b)*(c+d);printf("ecco il risultato %d", ris);



Linguaggi di alto livello: QualiLinguaggi di alto livello: Quali

COBOL (COmmon Business Oriented Language) LISP, PROLOG Fortran (FORmula TRANslator) Pascal Basic C / C++ JAVA C# …



Fasi della programmazioneFasi della programmazione

La preparazione di un programma scritto in un linguaggio ad alto livello, passa tra diverse fasi:

– editazione– compilazione– linking (collegamento)– caricamento– esecuzione



Fase di editazioneFase di editazione

Consiste nella scrittura del codice (testo del programma) in un file

Si esegue tramite un programma chiamato editor o Ambiente di sviluppo

Genera il programma sorgente



Fase di compilazioneFase di compilazione

Il codice sorgente viene passato al compilatore che si occuperà di tradurre il programma nel codice in linguaggio macchina

Genera il programma oggetto



Fase di linking (collegamento)Fase di linking (collegamento)

I programmi scritti in linguaggio ad alto livello, contengono dei riferimenti a funzioni definite altrove– Nelle librerie del linguaggio e/o del sistema operativo

Il codice oggetto prodotto dal compilatore conterrà dei “buchi” (riferimenti alle funzioni di libreria)

Il linker si occupa di collegare il codice oggetto con quello delle funzioni mancanti

Genera il programma eseguibile



Fase di Caricamento / EsecuzioneFase di Caricamento / Esecuzione

Fase di caricamento– Prima che possa essere eseguito, un

programma dovrà essere caricato in memoria– Il programma loader (parte del sistema

operativo) si occupa di questa operazione

Fase di esecuzione– Il computer esegue il programma, una

istruzione per volta



Linguaggi compilati e interpretatiLinguaggi compilati e interpretati

Il calcolatore “capisce” solo il linguaggio macchina

I programmi scritti in linguaggi di alto livello devono essere tradotti in linguaggio macchina prima di essere eseguiti– Di ciò si occupa il compilatore

In alternativa alcuni linguaggi di alto livello hanno associato un interprete– Si tratta di un programma capace di “capire” quel

particolare linguaggio e di eseguirne i programmi– Un’istruzione per volta



Paradigma ad oggettiParadigma ad oggetti

Il paradigma ad oggetti propone il superamento del dualismo dati procedure

Un oggetto è un’entità che incorpora sia una struttura dati (stato) che le procedure che agiscono su di essa (metodi)

Il termine oggetto è emerso quasi indipendentemente e quasi simultaneamente in diversi campi dell’informatica a cavallo fra gli anni 60 e 70, per indicare concetti apparentemente diversi ma in realtà strettamente correlati.

Tutti questi concetti infatti erano stati introdotti per gestire la complessità nei sistemi software.

Erano infatti componenti di sistemi decomposti modularmente oppure unità modulari di rappresentazione della conoscenza.



I fondamenti della programmazione ad I fondamenti della programmazione ad oggetti (object-oriented)oggetti (object-oriented)Diamo qualche definizione “classica” Che cos’è un oggetto?

– Un oggetto è un‘entità dotata di uno stato e di un comportamento

Quali sono i concetti fondamentali della visione object oriented?– Incapsulamento

• In base al principio di incapsulamento un oggetto è una “scatola nera” che racchiude una struttura dati (stato dell’oggetto). Questa struttura non può essere manipolata direttamente ma solo attraverso i metodi dell’oggetto

– Ereditarietà• E’ la sintesi del concetto di gerarchia (presente p.es. nel campo

dei database) e del concetto di descrizione differenziale proveniente dal campo delle scienze cognitive e dell’intelligenza artificiale

– Polimorfismo • Il polimorfismo è la capacità degli oggetti di avere

comportamenti diversi in risposta all’invocazione dello stesso metodo



Costrutti elementariCostrutti elementari

La programmazione in un linguaggio di alto livello (imperativo) è basata su tre costrutti fondamentali:– Sequenza– Selezione– Ripetizione

Sequenza: serie di istruzioni che vengono eseguite una dopo l’altra

Selezione: viene posta una condizione, se la condizione è verificata viene eseguito un blocco di istruzioni, altrimenti ne viene eseguito un altro

Ripetizione: uno stesso blocco di istruzioni viene eseguito a ripetizione fino a quando non viene verificata la condizione di uscita dal ciclo



Istruzione 1

Istruzione 2

Istruzione N

Esempio:

• Leggi un numero da tastiera

• Moltiplicalo per 2

• Stampalo a video

SequenzaSequenza



Istruzione 1

Istruzione 2

Esempio:


• Condizione: è un numero positivo?

• Se la condizione è verificata si incrementa il numero, altrimenti lo si decrementa

• Si stampa a video il numero

Condizione

Istruzione 3

Istruzione 4

SelezioneSelezione



Istruzione 1

Istruzione 2

Esempio:


• Decrementalo di 1

• Condizione uscita: il numero è uguale a 0?

• se la condizione è verificata il programma esce dal ciclo, altrimenti lo ripete

Condizione uscita

RipetizioneRipetizione



I tre costrutti fondamentali sono sufficienti aI tre costrutti fondamentali sono sufficienti adescrivere qualunque algoritmodescrivere qualunque algoritmo

I tre costrutti fondamentali sono sufficienti aI tre costrutti fondamentali sono sufficienti adescrivere qualunque algoritmodescrivere qualunque algoritmo

Detto in altre parole: dato un problema di complessità finita, è sempre possibile scrivere l’algoritmo che lo risolve utilizzando opportunamente i tre costrutti fondamentali presentati nei paragrafi precedenti

Per semplificare possiamo dire che un problema ha complessità finita quando esiste una soluzione calcolabile in un tempo finito

E’ ad esempio impossibile scrivere un programma in grado di indovinare con esattezza la schedina del totocalcio, o i numeri del lotto (queste funzioni non sono calcolabili)

Teorema di Böhm-JacopiniTeorema di Böhm-Jacopini

Il Sistema Operativo Rappresentazione dell’Informazione Cenni di Programmazione

Documents

Transcript of Il Sistema Operativo Rappresentazione dell’Informazione Cenni di Programmazione