UD1

U.D. Algoritmi e Rappresentazionedell’Informazione

Prof. Fabio Cantaro

Obiettivi Questo modulo permetterà al discente di comprendere i concetti fondamentali delleTecnologie dell’Informazione e della Comunicazione (ICT) ad un livello generale conoscere le varie parti di un computer, quindi, sar à in grado di :

Comprendere cosa è l’hardware, conoscere i fattori che influiscono sulle prestazioni diun computer e sapere cosa sono le periferiche.

Comprendere cosa è il software e fornire esempi di applicazioni di uso comune e disistemi operativi.

Comprendere come vengono utilizzate le reti informatiche e cono scere le diversemodalità di collegamento a Internet.

Comprendere cosa sono le Tecnologie dell ’Informazione e della Comunicazione (ICT) efornire esempi della loro applicazione pratica nella vita quotid iana.

Comprendere le problematiche di igiene e sicurezza associate al l’impiego dei computer.Riconoscere importanti problematiche di sicurezza informatica a ssociate all’impiego dei

computer.Riconoscere importanti problematiche legali relative al diritto di riproduzione (copyright)

e alla protezione dei dati associate all ’impiego dei computer.

Algoritmo: definizione

In informatica, con il termine algoritmo siintende un metodo per la risoluzione di unproblema adatto a essere implementato sottoforma di programma.

Dunque, più dettagliatamente esso è:“una sequenza logica di istruzioni elementari(univocamente interpretabili) che, eseguite inun ordine stabilito, permettono la soluzione diun problema in un numero finito di passaggi ”.

Proprietà algoritmi

la sequenza di istruzioni deve essere finita; essa deve portare ad un risultato; le istruzioni devono essere tutte eseguibili

dall’esecutore; le istruzioni devono essere espresse in modo

non ambiguo.

Esempio: somma di duenumeri digitati dall’utente

INIZIOa) Ci vogliono i due numeri interi (ingredienti);b) Acquisisci il primo numero dalla tastiera;c) Acquisisci il secondo numero dalla tastiera;d) Somma i due numeri;e) Mostra il risultato sullo schermo.

FINE

Rappresentazione degliAlgoritmi prima di passare al codice (programma)

utilizzando un linguaggio di programmazione,si usa utilizzare un diagramma di flusso odiagramma a blocchi o flow-chart

Fa uso di: SIMBOLI GRAFICI (figure geometriche), per la

sequenza di Istruzioni DATI:

Costanti: stesso valore nell’esecuzione Variabili: possono variare durante l ’esecuzione

Simboli dei FLOW-CHART

Esempio

La somma di due numeri

Altro esempio Dato un numero n, calcolare il cubo se

n>0 il quadrato se è negativo

Start

Leggi n

N>0

Ris= n * n Ris= n * n* n

Scrivi Ris

End

VF

Rappresentazione dei Dati

UD 2

Informazione Tutto ciò che possiede un significato per l ’uomo e

che viene comunicato o conservato in vista di unautilità pratica.

Le informazioni si presentano in varie forme: Caratteri Numeri Immagini Luce suoni Ecc…

Trasmissione delleinformazioni

Affinchè 2 entità possano comunicare è necessario cheriescano a capirsi (esempio 2 persone che parlano linguediverse).

Allora occorre che siano stabiliti e rispettati: Il CODICE della trasmissione, cioè le regole secondo

cui viene TRADOTTO il messaggio prima dell ’invio (es.alfabeto comune e le parole in italiano)

La TECNICA di trasmissione (es. telefono) Il PROTOCOLLO della trasmissione, cioè le Regole

per uno scambio corretto delle informazioni (es. regolegrammaticali per creare frasi che abbiano un sensocompiuto in Italiano)

Esempio Giochiamo a carte: a poker

Il codice sono il tipo di carte (francesi) Il protocollo sono le regole del poker La tecnica: visualizzazione delle carte Se decido di giocare a Texas Holdem => modifico il protocollo

regole

Esempio 2 Giochiamo a carte: a briscola

Il codice è diverso (carte napoletane o siciliane) Il protocollo sono le regole della briscola Se decido di giocare a scopa => modifico il protocollo

regole

Trasmissione delle informazioni(2) I caratteri e i simboli che compongono il

Messaggio e che vengono trasformati perviaggiare sul mezzo trasmissivo sono dettiSEGNALI

I Segnali possono essere: DIGITALI: se associati a cifre binarie (0,1) ANALOGICI: se sono rappresentati da

grandezze che variano con continuit à neltempo

Trasmissione delle informazioni(3)

0110011001110011

Comunicazione Digitale

Comunicazione Analogica

Rappresentazione dei dati

Come rappresentare i numeri e le operazioninel pc? (sistemi di numerazione)

Come rappresentare i caratteri? E come rappresentare immagini, suoni,

ecc…?

Rappresentazione dei numeri Sistemi posizionali .

Es. Decimale, binario, esadecimale, ottale Sistemi non posizionali

Es. Romano

Rappresentazione dei numeri Sistemi non posizionali .

Esempio: Sistema NumerazioneRomano.

Esempio: MCD = CDMInfatti. 1000+100+500=100+500+1000

I = 1V = 5X = 10L = 50C = 100D = 500M = 1000

Rappresentazione dati

Sistemi posizionaliLa posizione è importante!!!

Esempio 853 358 (sistema decimale)

Infatti:853= 8*102 + 5*101 + 3*100 =800 + 50 + 3358= 3*102 + 5*101 + 8*100 =300 + 50 + 8

Posto 2 Posto 0Posto 1

Sistema Decimale

B=10 => A={0,1,2,3,4,5,6,7,8, 9 (=10-1) }

Ogni cifra decimale deve essere unadell’alfabeto

Sistema Binario B=2 => A={0,1} Il Sistema Binario è un sistema posizionale

basato su due sole cifre: 0 e 1 detti BIT(Binary Digit)

Esempi di numeri binari :

101

10010101

1010211 non è binario, infatti 2{0,1}

Perché il sistema binario?

I computer non parlano la nostra stessalingua, ma utilizzano un sistema formato dadue numeri 0 e 1 (On e Off, passaggio oassenza di corrente elettrica)

Conversione 2 -> 10Si moltiplica ogni cifra per la potenza di 2 in base alla posizi one occupata.

corrisponde a 1*23 + 0*22 + 1*21 +1*20 = (11)10 in decimale

• Esempio: convertiamo 1011 in decimale

esercizio

Convertire i seguenti numeri binari indecimale: 1101 10001 111

Soluzione

Convertire i seguenti numeri binari indecimale: (1101)2 = 1*23+1*22+0*21+1*20 =8+4+0+1=13 (10001)2 = (17)10

(111)2 = (1101)2

Conversione 10->2 Si divide ripetutamente il numero decimale per

2 e si prendono i resti in ordine inverso

Esempio: 20 in binario.

Esercizio

Convertire da decimale a binario i seguentinumeri: (15)10

(63)10

(64)10

(1045)10

Esercizio: SOLUZIONE

Convertire da decimale a binario i seguentinumeri: (15)10 = (1111)2

(63)10 = (11 1111)2

(64)10 = (100 0000)2

(1045)10 = (100 0001 0101)2

In windows Nei sistemi windows è possibile convertire un numero tra i principali sistemi

numerici : il binario(Bin), l’ottale (Oct). Il decimale (Dec) l’esadecimale (Hex).

Start/Tutti i programmi/Accessori/Calcolatrice scegliere menu Visualizza/Scientifica .

Rappresentare i caratteri in formabinaria

A seconda del sistema, per rappresentare uncarattere servono: 1 byte (8 bit), standard ASCII 2 byte (16 bit), standard UNICODE

Standard ASCII

Con 8 bit => 256 simboli => 2 8=256

Cioè

Sommando i singoli valori (1 + 2 + 4 + 8 + 16 + 32 + 64 + 128) si ottiene 255a cui, aggiungendo anche lo zero, abbiamo 256 possibili valori ottenibili.

256 possibili combinazioni di bit => posso associare a ognuna uncarattere

Sistema Esadecimale

I computer “parlano in bit” => per noi sarebbemolto complicato capire cose del tipo:

0000 10011110 01101001 0011

….=> Venne quindi creato il sistema

ESADECIMALE

Esadecimale

Usa 16 simboli A={0,1,2,…,9,A,B,C,D,E,F} Ogni cifra esadecimale “usa” 4 bit

Bit Hex Bit hex

I numeri decimali da 10 a 15 sono stati sostituiti con le prime 6lettere dell’alfabeto.

Rappresentazione dei caratteri

Si è creata una tabella in cui a ogni numerobinario (codice) fanno corrispondere uncarattere

Nella tabella sottostante sono riportati i simboli grafici di alcuni caratteri, la loro valenza binaria ed il corrispondente valore espresso sia in decimale che in esadecimale:

3737

LL’’INFORMAZIONE digitaleINFORMAZIONE digitale

Esercizi

Come si rappresentano i caratteri al PC? Quanti bit utilizza lo Standard ASCII Quanti caratteri puo’ rappresentare lo

standard ASCII Quanti bit utilizza lo Standard Unicode? Quanti bit prende la rappr. Esadecimale?

Descrivere le caratteristiche diuna immagine digitale L’immagine digitale è un’immagine bidimensionale

rappresentata da valori numerici. Fondamentalmente le immagini digitali sono di due tipi (in

base al tipo di rappresentazione): RASTER (o bitmap): matrice di punti elementari, chiamati pixel

(da picture element). VETTORIALE: insieme di nodi formanti linee e poligoni a loro volta

uniti in strutture più complesse.

40

Parentesi: Concetti di base

Che cos'è un pixel? un pixel è il più piccolo componente discreto di una

immagine sullo schermo normalmente un punto con colore

Che cos'è la risoluzione video? la risoluzione è il numero di pixel (o punti) per

pollice dpi (dots per inch)

Risoluzione

Esempio i mosaici

Più piccoli sono i tasselli maggiore è la qualitàl’immagine

Immagine Bitmap o Raster

Caratterizzata da 2 proprietà: Risoluzione: numero di pixel per centimetro

quadrato (DPI); Profondità di colore: numero di colori che si

possono usare. Si può avere profondit à: 16 colori (4 bit per pixel) 256 colori (8 bit per pixel) 65536 colori (16 bit per pixel) 16,77 milioni di colori (24-32 bit per pixel)

4343

LL’’INFORMAZIONE digitaleINFORMAZIONE digitale

Immagine Bitmap o Raster (2) Sono costituite da pixel Consentono una transizione graduale del colore Se ingrandite si perde in qualità Occupano molto spazio Possono essere salvate in diversi formati:

Compressione Lossless (senza perdita): BMP, TIFF,PNG, RAW, ecc…

Compressione Lossy (perdita): JPEG, GIF (256 colori)

Esempi bitmap

Immagine

Immagine ingrandita “sgranata”

IMMAGINI VETTORIALI Contengono infomazioni:

Circa le FORME che formano l’immagine(dimensione, posizione, ecc…)

Circa i COLORI da applicare a ogni forma RENDERING: processo di creazione

dell’immagine in PIXEL partendo da questeinformazioni

MOTORE DI RENDERING: programma cheesegue il rendering

Esempio Immagini

Immagine Originale

Immagine Vettoriale ingrandita 8x

Immagine Raster ingrandita 8x

Acquisizione Immagini

Catturandole da schermo (tasto stamp) Scannerizzarle da formato cartaceo importarle da fotocamere digitali Scaricarle da Internet o da CD OCR: scannerizzando un documento ottengo

una immagine => con OCR di nuovodocumento

Esercizi

Da cosa è caratterizzata una immaginebitmap?

Da cosa è caratterizzata una immaginevettoriale?

Quali sono i formati più comuni per unaimmagine raster?

Linguaggi Con il linguaggio vengono definite:

Il Lessico: insieme delle parole con relativo significato; La Sintassi: regole per costruire una frase in modo

corretto.

L’uomo utilizza il linguaggio naturale che è moltoricco di espressività ma è ambiguo:

Esempio: “la bella pesca” può essere interpretata in duemodi:

1. La bella ragazza che pesca2. Un bel frutto

Lunguaggio macchina

Un elaboratore non può però gestireinformazioni ambigue

Il linguaggio macchina è l’unico linguaggiocapito dal computer: risulta veloce nell’esecuzione ma ha lo svantaggio di una difficile e lunga

scrittura della sequenza di algoritmi (programma)e della loro messa a punto.

Linguaggi di programmazione Non è possibile realizzare traduttori dal linguaggio

naturale al linguaggio macchina => servono ilinguaggi di programmazione

essi sono comprensibili all ’uomo e, tramite untraduttore, vengono tradotti in linguaggio macchina

Linguaggio Naturale (Algoritmi)

Linguaggio Programmazione

Linguaggio macchina

CPU

Traduttori (compilatori, interpreti)

1000100011

Esercizi

Quali sono gli elementi del Linguaggiomacchina?

Il linguaggio naturale può essere usato per ilcomputer?

L’uomo programma oggi col linguaggiomacchina? Con cosa?

1.0.3.2 Distinguere il ruolo deiconnettivi logici (NOT, AND, OR)

Consideriamo le frasi:A=“Ho fame” B=”Ho i soldi”

Queste affermazioni possono vere o false I connettivi permettono di legare i due

suddetti enunciati e di crearne un terzo.Esempio: Se “ho fame” e “ho i soldi” allora “Vado al

ristorante” => A and B = C

Connettivo AND E vero solo se i due input sono veri.

111001010000CBA

In generale A and B = C è vera se:

In Algebra di Boole

Tabella di verità:Posso andare al ristorante

solo se ho i soldi e hoanche fame

Connettivo OR E vero se almeno uno i due input è vero.

111101110000

RistoranteSoldiFame

In generale A and B = C è vera se:

In Algebra di Boole

Tabella di verità:

111101110000

C= A and BBA

Anche se non ho fame, maho i soldi vado alristorante e viceversa,anche se non ho i soldima ho vado al ristorante

Connettivo NOT L’operazione NOT ha una variabile di input ed una

variabile di output. Il valore della variabile di output è l’opposto di quella

di input

In Algebra di Boole

0110

Not AA

Ripasso

A cosa serve AND? A cosa serve OR? A cosa serve NOT?

1.0.3.3 Distinguere fra linguaggiomacchina e linguaggi procedurali

I linguaggi di programmazione sono di due tipi: basso livello:

linguaggi assemblativi orientati alla macchina (comunicanodirettamente con il computer utilizzando il "linguaggiomacchina");

il "linguaggio macchina“ è l’unico linguaggio compreso dalcomputer

alto livello: orientati all’uomo fanno uso di uno pseudo linguaggio umano, utilizzando allo

scopo codici operativi in lingua inglese. Ogni linguaggio di programmazione ha bisogno di un

traduttore

I Traduttori: Compilatori eInterpreti trasformano un programma sorgente (espresso in

un linguaggio di programmazione), in un programmaoggetto (tradotto in codice binario).

dipendono dal linguaggio di programmazione edall’architettura del computer.

Linguaggi ad Alto Livello(Orientati all’uomo)

C, C++, Java, VisualBasic, Pascal, ecc…

Linguaggi ad Alto Livello(Orientati all’uomo)

C, C++, Java, VisualBasic, Pascal, ecc…

Compilatori o InterpretiCompilatori o Interpreti

Linguaggio Macchina(codice Binario)

Linguaggio Macchina(codice Binario)

Traduttore

Compilatori e Interpreti: le fasiI Compilatori: trasformano un programma “sorgente” (scritto in linguaggio di

programmazione) in un file “oggetto” (tradotto in linguaggio macchinama non ancora utilizzabile).

Per rendere “eseguibile” il risultato ottenuto è necessario che siaulteriormente trattato da un programma definito “linker” (o link editor),che collega, tra loro, i vari moduli tradotti ed i riferimenti e sterni (adesempio librerie di sistema), creando il programma eseguibile .

Gli Interpreti: leggono una istruzione alla volta => la traducono in codice macchina => e la eseguono => traduzione ed esecuzione sono contemporanei

Linguaggi Assemblativi edassemblatori I linguaggi assemblativi:

Sono linguaggi di tipo simbolico in quanto utilizzanodei nomi (simboli) per designare il codice operativo ele variabili che compongono il programma.

Gli Assemblatori sono i traduttori dei linguaggiassemblativi.

L’Assembly (assemblatore): è il primo linguaggio informatico utilizzato, è comprensibile agli utilizzatori umani, ma è talmente simile al linguaggio macchina che

rimane legato al processore su cui viene sviluppato ilprogramma

Tale programma non potrà essere eseguito sucomputer con processori diversi.

Linguaggi a basso Livello(orientati alla macchina)

Assembly

Linguaggi a basso Livello(orientati alla macchina)

Assembly

AssemblatoreAssemblatore

Linguaggio Macchina(codice Binario)

Linguaggio Macchina(codice Binario)

Alcuni linguaggi diprogrammazione Fortran (FORmula TRANslation): uno dei primi linguaggi di alto

livello ad uso scientifico

COBOL (COmmon Business-Oriented Language) ossia,letteralmente, "linguaggio orientato alle applicazioni commercia licomuni"

C, per uso ingegneristico. Usato per scrivere sistemi operativicome Linux

Java, per applicazioni web

PHP, per applicazioni web

PASCAL, per uso didattico

BASIC, inizialmente per applicazioni didattiche e scientifiche.Oggi Visual Basic

Scrivere un programma conPseudo linguaggio

È un modo alternativo per rappresentare glialgoritmi

Le istruzioni sono descritte tramite frasirigorose

Si usano parole chiave, operatori e nomi divariabili

Non è usabile direttamente => va tradotto inun linguaggio di programmazione

Esempio di pseudo linguaggio

Calcolare l’area di un quadrato dato il lato.Inizio

Fine

Leggi Lato

Scrivi Area

Area = Lato * Lato

PSEUDO LINGUAGGIO

PROGRAMMA AreaINIZIO

Leggi (Lato)Area Lato*LatoScrivi (Area)

FINE

Esercizi

Il linguaggio C è un linguaggio di alto livello? Differenza tra Interpreti e Compilatori? Cosa sono i Flow Chart? L’assembly è un linguaggio di alto livello? I compilatori traducono un file sorgente in

codice oggetto e quindi con il Linker sigenera il file eseguibile?

FINEU.D. Algoritmi e Rappresentazione

dell’Informazione