Appunti Informatica: teoria e Python

LABORARIO DI INFORMATICA

01 - Introduzione

Informatica

Dal dizionario Treccani:

l’insieme dei vari aspetti scientifici e tecnici che sono specificamente applicati alla raccolta e al trattamento

Informàtica:

dell’informazione e in particolare all’elaborazione automatica dei dati, come sussidio e supporto alla documentazione, alla ricerca

e allo studio nei vari settori della scienza, della tecnica, delle attività economiche, sociali, e anche pratiche.

Definizione della Association for Computing Machinery:

L’informatica è lo studio sistematico degli algoritmi che descrivono e trasformano l’informazione: la loro teoria, analisi, progetto,

efficienza, realizzazione e applicazione.

Un po’ di storia…

Costruire sistemi automatici di calcolo è sempre stata una grande ambizione dell’uomo, per necessità, come:

Astronomia e navigazione;

• Commercio e agricoltura;

• Architettura;

• Strumenti bellici…

• 1837: La macchina analitica di Babbage: prima macchina programmabile e quindi pensata per eseguire compiti generici. Utilizzava un

- linguaggio simile al moderno codice assembly. Venne costruita soltanto alla fine del 900.

1938: Konrad Zuse progetta e realizza lo Z1, calcolatore programmabile meccanico binario ad azionamento elettrico, con limitate

- funzionalità.

1941: Konrad Zuse progetta e realizza lo Z3, il primo calcolatore elettromeccanico programmabile binario con tecnologia a relè.

- 1946: J. Presper Eckley e John Mauchly guidano il progetto di ENIAC, primo calcolatore elettronico programmabile non specifico.

-

Informazione

L’informatica studia la rappresentazione e l’elaborazione dell’informazione:

Dati numerici;

• Dati testuali;

• Immagini, suoni, video.

•

Nei calcolatori tutti i dati sono rappresentati in forma digitale, quindi discreta, ed elaborati tramite algoritmi.

Algoritmi

Che cos’è un algoritmo?

Una sequenza finita di passi effettuabili per risolvere una classe di problemi in un tempo finito;

• Il nome deriva da quello del matematico persiano Al-Khuwarizmi (IX secolo) che introdusse il numero zero e la

• notazione posizionale in occidente;

Nel Medioevo, il termine algorismus indicava la tecnica di effettuare calcoli con numeri arabi.

•

Elementi di un algoritmo:

Passi elementari: azioni atomiche non scomponibili in azioni più semplici;

• Processo (esecuzione): sequenza ordinata di passi;

• Dati in ingresso: istanza del problema;

• Dati in uscita: soluzione.

•

Proprietà degli algoritmi:

Finitezza: numero finito di passi elementari;

• Non ambiguità: i risultati non variano in funzione di chi (macchina o persona) esegue l’algoritmo;

• Realizzabilità: eseguibile con le risorse disponibili;

• Efficienza: preferibile uso minimo delle risorse.

•

Algoritmo:

Metodo per la risoluzione di un problema Programma;

• Traduzione di un algoritmo in un linguaggio di programmazione interpretabile dal calcolatore;

• Processo;

• Programma in esecuzione sul calcolatore.

•

Macchina di Turing

Alan Turing (1912-1954) è un matematico inglese, tra i fondatori dell’informatica. Che costruì la “Macchina di Turing”:

Modello matematico di una macchina capace di eseguire calcoli su numeri e simboli sulla base di un insieme di regole

• che definiscono il comportamento;

Prima idea di calcolatore generale programmabile.

•

Computabilità

Tesi di Church-Turing: non esiste alcun formalismo capace di risolvere una classe di problemi più ampia della macchina di Turing.

Quindi… Se un problema non può essere risolto dalla macchina di Turing, allora non è risolvibile.

La macchina di Turing può essere considerata un modello formale dei computer moderni.

Esistono classi di problemi irrisolvibili:

Teorema di incompletezza di Godel;

• Esistono proposizioni né dimostrabili né confutabili.

•

Anche tra i problemi risolvibili ci sono problemi più o meno difficili ovvero che richiedono molto tempo o molte risorse

computazionali per essere risolti:

Problemi risolvibili vs. non risolvibili (computabilità);

• Problemi trattabili vs. non trattabili (complessità).

•

I calcolatori moderni

Evoluzione tecnologica:

Dall’analogico al digitale;

• Dalle valvole termoioniche ai transistor;

• Legge di Moore: il numero di transistor presenti su un microchip raddoppia ogni 18 mesi.

• LABORARIO DI INFORMATICA

02 – Calcolatori e algoritmi

Modello di Von Neumann John Von Neumann (1903-1957):

• Matematico, fisico, informatico ungherese, poi

naturalizzato americano;

• Uno dei padri fondatori dell’informatica;

• Progettò il calcolatore EDVAC, basato su un modello che

implementava la macchina di Turing.

Stored-program computer:

• La memoria contiene sia i dati sia le istruzioni;

• Il comportamento dipende dal programma.

Architettura generale

Evoluzione del modello di Von Neumann:

• Bus invece di collegamenti punto-punto.

CPU

La CPU (Central Processing Unit) è il cuore del calcolatore, ed è costituita da due unità

fondamentali:

• Unità di controllo o Control Unit (CU);

• Unità logico-aritmetica o Arithmetic Logic Unit (ALU).

Control Unit:

• Determina l’ordine di esecuzione delle istruzioni;

• Interpreta le istruzioni della macchina;

• Si occupa di recuperare gli operandi;

• Governa il flusso di esecuzione nel sistema, inviando comandi ai vari componenti.

Arithmetic-Logic Unit:

• Esegue tutte le operazioni logiche e aritmetiche;

• Opera utilizzando il sistema binario;

• Circuiti logici che implementano l’algebra di Boole.

Registri:

• Celle di memoria ad accesso diretto e molto rapido;

• Spesso si trovano sullo stesso chip della CU;

• Servono a memorizzare e trasferire dati e istruzioni.

Memoria

Nell’architettura di Von Neumann la stessa memoria viene utilizzata per i dati e le istruzioni:

• L’interpretazione dipende dai segnali di controllo, ovvero dal momento in cui i byte sono letti;

• Le istruzioni sono memorizzate in un array lineare;

• Ogni cella ha un indirizzo che ne indica la locazione all’interno della memoria.

Nei calcolatori moderni si distinguono due memorie:

• RAM (Random Access Memory);

• ROM (Read-Only Memory). RAM:

• Volatile;

• Usata per memorizzare dati e programmi;

• Ogni cella ha lo stesso tempo di latenza.

ROM:

• Memoria persistente, in sola lettura;

• Contenuto fisso e immutabile;

• Usata per memorizzare programmi di sistema (boot).

Gerarchia della memoria

• Registri della CPU;

• Memoria cache;

• Memoria centrale (RAM);

• Disco rigido;

• Dischi di memorizzazione esterni.

Località in memoria

Principio di località spaziale:

• Quando la CPU esegue una certa istruzione, è probabile che le successive istruzioni da seguire saranno in posizioni

vicine in memoria.

Principio di località temporale:

• Durante l’esecuzione di un programma, si accede molto frequentemente alle stesse zone di memoria.

BUS

Bus Dati:

• Dati da utilizzare come operandi.

Bus Comandi:

• Comandi dalla CPU verso i vari dispositivi.

Bus Indirizzi:

• Indirizzi di memoria (es. dove leggere/scrivere dati).

Architettura generale

Algebra di Boole

Nel 1854 il matematico e logico britannico George Boole pubblica il trattato “Le leggi del pensiero”.

Si tratta di un trattato che ha lo scopo di studiare le leggi del ragionamento umano attraverso la logica, dando alla logica una veste

algebrica.

Formalismo che opera su variabili dette booleane:

• Le variabili booleane posso assumere soltanto due valori: vero e falso;

• Sulle variabili booleane si possono definire delle funzioni, dette funzioni booleane;

• Anche le funzioni booleane possono assumere soltanto i due valori vero e falso;

• Le funzioni o operatori booleani di base sono and (congiunzione), or (disgiunzione) e not (negazione).

Tabella di verità:

• Definisce una funzione booleana, indicando il valore risultante per ogni

configurazione degli ingressi.

Operatori logici fondamentali:

• L’algebra di Boole si basa su operatori che possono essere combinati in espressioni per definire funzioni.

Operatori e porte logiche:

Instruction Set Architecture

Come si coordinano hardware e software?

Come posso sapere quali istruzioni sono disponibili?

Instruction Set Architecture (ISA):

• Interfaccia ben definita tra hardware e software;

• Definisce tutto ciò che è necessario per scrivere programmi in linguaggio macchina;

• Costituisce il vocabolario delle possibili istruzioni.

Linguaggi di programmazione

I programmi sono scritti in linguaggi di programmazione, che sono linguaggi formali con cui

è possibile dare istruzioni ad un computer.

Un computer esegue istruzioni definite secondo una certa ISA: questo è il linguaggio macchina (il livello più vicino all’hardware,

ovvero una sequenza di bit).

Abbiamo bisogno di rappresentazioni più astratte!

Linguaggi di basso livello (es. Assembly):

• Generalmente corrispondenza biunivoca con il linguaggio macchina, specifico di un’architettura, quindi non portabile.

Linguaggi di alto livello (es. C, C++, Java, Python, …): • Linguaggio più astratto e distante dall’hardware;

• Non c’è un linguaggio migliore di un altro;

• Tipicamente tutti computazionalmente equivalenti.

Compilatori e interpreti

Come si traduce un linguaggio di alto livello in

linguaggio macchina eseguibile dal calcolatore?

Questa operazione può essere effettuata tramite un

compilatore o un interprete a seconda del linguaggio:

• Linguaggi compilati (C, C++);

• Linguaggi interpretati (Javascript, Matlab);

• Linguaggi compilati su bytecode (Java, Python).

La distanza tra codice di alto livello e codice di basso livello viene

solitamente definita semantic gap ed è colmata dal compilatore.

Il processo di compilazione non è univoco: ad esempio, ci sono molti

compilatori per il linguaggio C.

Ogni compilatore riesce a compiere diverse forme di ottimizzazione e quindi influenza le prestazioni!

Virtual Machine (VM):

• Il codice di alto livello viene tradotto da un compilatore Just-In-Time (JIT) in un bytecode che è simile al codice

macchina (poco più astratto);

• Il bytecode viene eseguito sulla VM, di cui esistono versioni per i diversi sistemi operativi;

• In questo modo si aumenta la portabilità del codice.

Vantaggi dei linguaggi interpretati e bytecode:

Sono indipendenti dalla piattaforma.

+

Svantaggi dei linguaggi interpretati:

Tipicamente meno efficienti di quelli compilati;

- I compilatori possono essere utili ai programmatori.

-

Compilatori

Quando si scrive un programma, posso presentarsi diverse tipologie di errore:

• Errori di sintassi;

• Errori di semantica statica;

• Errori di semantica dinamica.

Errori di sintassi: Si verificano quando si scrivono espressioni non legali, ovvero che non seguono le regole della

grammatica del linguaggio.

Questo tipo di errore è segnalato dal compilatore.

Errori di semantica statica:

Si verificano quando frasi sintatticamente corrette sono errate in quanto prive di significato.

In questo caso il compilatore può dare qualche aiuto.

Esempio: si utilizza una variabile non dichiarata…

Errori di semantica dinamica:

Si verificano quando all’esecuzione del programma si verifica un malfunzionamento (runtime errors).

In questo caso il compilatore non offre aiuto.

Sono gli errori più difficili da identificare e più critici.

Il programma può:

• …dare la risposta corretta;

• …dare la risposta corretta solo apparentemente;

• …terminare con errore (crash);

• …non terminare mai;

• …dare la risposta sbagliata.

Programmare

Un programmatore individua una sequenza di istruzioni per risolvere un dato problema, trasformandole in forma eseguibile da un

calcolatore.

Un calcolatore esegue istruzioni elementari:

• L’insieme di istruzioni elementari tipicamente varia da calcolatore a calcolatore (ISA)…

1. Analisi del problema; 1. Problema

2. Descrizione (informale) della soluzione; 2. Algoritmo

3. Codifica (formale) della soluzione; 3. Programma

4. Traduzione in codice eseguibile dalla macchina; 4. ISA

5. Esecuzione della soluzione. 5. Microarchitettura

6. Logica e circuiti

Algoritmi

Definizione di algoritmo:

• Sequenza finita di passi effettuabili per risolvere una classe di problemi in un tempo finito.

Algoritmo:

• Metodo per la risoluzione di un problema.

Programma:

• Traduzione di un algoritmo in un linguaggio di programmazione interpretabile dal calcolatore.

Processo:

• Programma in esecuzione sul calcolatore.

Strutture di controllo

Esistono tre tipi fondamentali di strutture di controllo:

• Concatenazione, o sequenza lineare;

• Esecuzione condizionata;

• Iterazione.

Teorema di Bohm-Jacopini (1966): qualsiasi algoritmo può essere formalizzato con queste tre sole strutture di controllo.

Una conseguenza del teorema di Bohm-Jacopini fu la dimostrazione dell’inutilità dell’istruzione goto che era allora ampiamente

utilizzata in molti linguaggi…

Con le tre strutture di controllo fondamentali si può realizzare qualsiasi algoritmo: definiscono un insieme:

• Componibile;

• Completo.

Diagramma di flusso

Formalismo grafico per rappresentare algoritmi.

Descrizione più efficace e meno ambigua di una descrizione a parole.

Costituito da due tipi di entità: nodi e archi.

È un grafo orientato per rappresentare i passi di un algoritmo e la loro sequenza.

Pseudo-codice

Linguaggio per descrivere algoritmi attraverso istruzioni simili a quelle di un linguaggio di programmazione:

• Non esiste uno standard universale;

• Esistono convenzioni tipicamente adottate;

È un linguaggio semplice e intuitivo, partendo dal quale si può facilmente scrivere in un linguaggio di programmazione sul

calcolatore. LABORARIO DI INFORMATICA

03 - Rappresentazione dei dati

Sistemi di numerazione

Notazione non posizionale:

• Numeri romani: i simboli hanno un ruolo che dipende dalla loro posizione relativa.

Notazione posizionale:

• Numeri arabi: i simboli hanno un ruolo che dipende dalla loro posizione assoluta.

Numero romano XIII:

• I tre simboli I corrispondono tutti al valore 1;

• Il simbolo X corrisponde al valore 10;

• Si sommano i valori, ottenendo quindi 13.

Numero romano IX:

• Il simbolo X corrisponde al valore 10;

• Il simbolo I corrisponde al valore 1, ma precede X;

• È necessario sottrarre 1 da 10, ottenendo quindi 9.

Sistema decimale: 2 1 0

• Numero 374 = 3 * 10 + 7 * 10 + 4 * 10

Sistema in base B: K-1 1 0

… c c = c * B +… + c * B + c * B

• c K-1 1 0 K-1 1 0

In base B l’alfabeto dei simboli è costituito da un numero B di cifre che vanno da 0 a B-1.

In base 2 l’alfabeto dei simboli è costituito soltanto dai due simboli 0 e 1.

In base 16 l’alfabeto dei simboli è costituito dai simboli 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

I calcolatori rappresentano qualsiasi tipo di informazione in base 2, ovvero con un codice binario.

Ogni elemento di una sequenza binaria è detto bit (binary digit), ed una sequenza di 8 bit è detta byte.

Esistono regole di conversione per trasformare un numero da una base in un’altra.

Sistema Internazionale, potenze del byte:

K-1 1 0

* B +… + c * B + c * B

n = c K-1 1 0

0 1 K-1

n = c * B + c * B + … + c * B

0 1 K-1

n = c + B * (c + B * (c + B * (…) ) )

0 1 2

La cifra c è il resto della divisione di n per la base B.

0

Le altre cifre si ottengono iterando il procedimento.

Le cifre vengono prodotte dalla meno significativa alla più significativa (least/most significant bit: LSB/MSB).

Esempio: (base B=2) Esempio: (base B=8) Esempio: Sistema esadecimale (base B=16)

Conversione da binario a esadecimale: Conversione da esadecimale a binario:

• Si raggruppano i bit a gruppi di 4; • Per ogni cifra esadecimale si generano 4 bit;

• Si sfrutta la tabella precedente; • Si sfrutta la tabella precedente;

= (6D7C) • • (A5E) = (101001011110)

• (0110110101111100) 2 2 2 2

Internamente ad un calcolatore, tutte le informazioni sono rappresentate come sequenze di bit.

Il valore che viene assegnato ad una sequenza di bit dipende dalla modalità (istruzione, programma, etc.) con cui si accede a tale

sequenza!

Una stessa sequenza di bit può essere interpretata come carattere, numero, istruzione, etc.…

Rappresentazione dei numeri

Rappresentazione binaria di un intero senza segno: K

• Dato il numero N, occorrono K bit dove 2 > N;

K -1.

• Con K bit posso codificare gli interi tra 0 e 2

Un calcolatore usa un numero fisso di bit:

• Ci sono quindi casi di valori non rappresentabili;

• Si parla di overflow e underflow. PRINCIPALMENTE PER NUMERI IN VIRGOLA MOBILE

Rappresentazione binaria di un intero senza segno:

• Un valore tipico di K è 32 (ovvero 4 byte); .

• Big Endian vs. Little Endian (ordine dei byte)

Byte più significativo a sinistra: Big-Endian.

Byte più significativo a destra: Little-Endian.

Rappresentazione binaria di un intero senza segno;

• Esempio su 4 bit;

• Massimo numero rappresentabile: (15) = (1111) .

10 2

Rappresentazione binaria di un intero con segno:

Soluzione 1: codifica con segno e valore assoluto

• Primo bit = 0 se il numero è positivo

• Primo bit = 1 se il numero è negativo

• Svantaggio #1: due codifiche per lo zero

• Svantaggio #2: operazioni non automatizzabili…

• Occorrono algoritmi ad hoc per fare le operazioni

• Esempio: (+6) + (-6) = -12???

Rappresentazione binaria di un intero con segno:

Soluzione 2: complemento a 2

K-1

• Il MSB ha peso -2

K-1 1 0

• n = - c * 2 +… + c * B + c * B

K-1 1 0 vale 1

• Il numero è negativo se e solo se c K-1

K-1 K-1

, 2 - 1]

• Rappresento tutti gli interi in [- 2

• Come si calcola il complemento a 2 di un numero?

• Si invertono tutti i bit (da 0 a 1 e da 1 a 0)

• Si aggiunge 1 al risultato

• Il procedimento inverso ricalcola il numero originario

NOTA: IL MINIMO NUMERO RAPPRESENTABILE (1000…0000) HA COME COMPLEMENTO A DUE SÉ STESSO

Esempio: Complemento a 2:

a = (30) = (00011110)

10 2C

b = (22) = (00010110)

10 2C

a - b = (8) = (00001000)

10 2C

= (11101010)

-b = (-22) 10 2C

a + (-b) = (00001000) 2C

Vantaggi del complemento a 2:

• Una sola rappresentazione dello zero;

• Unificazione del trattamento di somme e sottrazioni;

• Semplificazione dell’unità logico-aritmetica (Arithmetic Logic Unit, ALU) nel calcolatore.

Overflow nella rappresentazione in complemento a 2:

• In generale, si parla di overflow quando il risultato di un’operazione non è rappresentabile;

• Per gli interi senza segno, questo corrisponde ad avere valore 1 sul bit di riporto (bit di

overflow);

• Per gli interi con segno, questo corrisponde ad ottenere un numero positivo come somma di

due numeri negativi, o viceversa.

Con 4 bit posso rappresentare l’intervallo [-8,7] quindi i due valori 7+1 e (-4 + (-7)) eccedono la dinamica della rappresentazione.

Rappresentazione binaria dei numeri in virgola mobile:

• Come si codifica in base 2 una parte frazionaria? • Algoritmo delle moltiplicazioni successive

• Algoritmo delle moltiplicazioni successive

• Segno, mantissa, caratteristica (tipo di dato float)

Esistono più rappresentazioni dello stesso numero

Forma normale (standard IEEE754): m [1, B)

∈

Esempio: float nel linguaggio c (codifica su 32 bit)

• 1 bit per il segno (0=positivo, 1=negativo)

• 23 bit per la mantissa

• 8 bit per la caratteristica: intervallo [-127, 128]

Caratteristica polarizzata: si rappresenta e = c+127 in modo da codificare un numero tra 0 e 255

Casi speciali

• 0 è codificato con mantissa 0, esponente 0

• +/-Inf è codificato con mantissa 0, esponente 255

• NaN è codificato con mantissa ≠ 0, esponente 255

Esempio: Convertire il numero (-21,125) in base 2

10

1. Segno: s = 1

2. Converto la parte intera: (21) = (10101)

10 2

3. Converto la parte decimale: (0,125) = (0,001)

10 2

Riporto in forma normale: (1,0101001) • (2)

4. QUESTO “1” NON SI CODIFICA PERCHE’ È SEMPRE PRESENTE

2 4

5. Mantissa: 0101001

6. Caratteristica (polarizzata): (4+127) = (10000011)

10 2

Codifica float IEEE 754

1

1. Segno:

2. Caratteristica polarizzata: 10000011

3. Mantissa: 0101001 BISOGNA RIEMPIRE LA MANTISSA CON TANTI ZERI A DESTRA FINO AD ARRIVARE A 23 BIT

11000001101010010000000000000000

Problema di precisione finita:

• Errore di approssimazione nel rappresentare un numero razionale X come float

• s determina se X è positivo o negativo

• c determina l’intervallo [Bc, Bc+1] cui X appartiene

• m permette di rappresentare 223 valori per intervallo

STESSO NUMERO DI VALORI SU ORDINI DI GRANDEZZA DIVERSI LA DENSITA’ CON CUI SONO COPERTI I RAZIONALI NON È OMOGENEA

• L’errore assoluto non è invariante, quello relativo sì

Nota: per i double i bit di mantissa diventano 52 e i bit di caratteristica diventano 11 (sempre 1 bit per s)

Errori di aritmetica di precisione finita:

• L’insieme dei float non è chiuso rispetto alle operazioni di somma e di prodotto;

• Somma di due float: si uguagliano le caratteristiche e si sommano le mantisse (forma normale);

• Esempio: 4 cifre di mantissa. NOTA: NON ESISTE UN’UNICA

RAPPRESENTAZIONE DELLO

0, COME INVECE IN