Appunti Informatica B

Info b. Eseg. M. Informatica

Scienza dell’informazione. Capire i dati, quali sono importanti e cosa farci.

L’informazione può essere concreta o astratta.

Cosa fare con informazione?

1. Rappresentarla - sotto forma di immagine, suono, parola, ecc.
2. Elaborarla - trovare modo per cui l’informazione diventi di valore per noi, tramite delle operazioni capire se l’informazione ha valore per noi, tipo diagnosi da radiografia.

Algoritmi

Algoritmo: qualcosa che trasforma ed elabora le informazioni.

Un algoritmo è eseguibile anche da un umano, ma usiamo il calcolatore perché è in grado di considerare tanti dati insieme e quindi svolgere velocemente l’algoritmo.

Definizione

Un algoritmo è una sequenza di operazioni, definite con precisione, non possono essere vaghe, che portano alla realizzazione di un compito preciso. Es. algoritmo per fare la pasta, non puoi dire solo “fai la pasta”, devi dare tutte le istruzioni precise in sequenza.

Le operazioni devono essere:

• Comprensibili —> No ambiguità.
• Eseguibili da strumento automatico, esecutore.
• Portare a realizzazione del compito in un tempo definito, numero finito di passi, ognuno con tempo definito.

Inizialmente useremo un linguaggio naturale, in italiano, ma comunque sarà caratterizzato da:

• Sequenzialità delle istruzioni, istruzioni scritte eseguite dall’alto in basso, ordine temporale.
• Costrutto condizionale, istruzioni eseguite a volte alcune, a volte altre, se... allora... sennò.
• Costrutto iterativo, ripetizione di più volte della stessa operazione, fai... finché.

Useremo “foglietti”, dove scriveremo i nostri valori.

Sempre, quando risolveremo un problema, passeremo dal linguaggio naturale, per capire e strutturare il problema, poi scriveremo in codice.

Rappresentazione a blocchi

Ogni blocco è un istruzione, blocchi eseguiti dall’alto in basso, quindi devono avere coerenza e ordine temporale costruito.

F è itercono f-. ← tt |L puoi essere esegue € anche solo K ciclo del ramo 'finché venatoria " diventa-continua falso oltre sto.

Esempio del pallottoliere: non posso dire sposto tutte le palline, devo dare precise istruzioni atomiche, ovvero sposto una pallina alla volta, fino a quelle che mi servono, in caso vedi slide.

Controlli in un algoritmo

In un algoritmo devo controllare:

• Correttezza: arriva alla soluzione del problema per cui è progettato.
• Efficienza: deve usare un numero minimale o ragionevole di risorse, ovvero il minor numero possibile di operazioni e utilizzare il minor spazio possibile del calcolatore, risparmiare spazio e tempo.

Algoritmi tipo

• Per scambiare il contenuto di due foglietti devo servirmi di un terzo foglietto.
• Per trovare il numero massimo, o minimo, prendo il primo a prescindere e lo scambio con eventuali altri più grandi, confrontando il numero che ho con tutti quelli che restano, importante: al primo istante prendo il primo valore.
• Per verificare se una condizione è vera per tutti gli elementi di una entità, insieme: appena ne trovo uno falsa mi interrompo e ho verificato che non è vera per tutti.
• Per cercare un elemento: utilizzando un archivio ordinato per autore, cerco libro in biblioteca. Ricerca scheda del libro, segnare su un foglio numero scaffale e posizione libro, raggiungere scaffale. Esamino una scheda e vedo se è quella che contiene il libro giusto, se non è quella vado avanti e rifaccio. Ma non è efficiente, le schede sono ordinate, quindi utilizzo N/2, dove N è il numero delle schede, e verifico se è quella, sennò confronto la lettera iniziale di N/2 con la mia, e vedo se prendere in considerazione la prima o la seconda metà dell’archivio, e di quella metà fare idem.

È un problema ripetuto su delle istanze più piccole e semplici. È un algoritmo ricorsivo, ripete le stesse operazioni ma su problemi sempre più semplici. Quando, se, N=0 mi fermo, posso non aver trovato il libro che quindi non c’è.

Ma noi vogliamo usare il calcolatore, quindi da algoritmo dobbiamo passare al codice.

Calcolatore

Il calcolatore è:

• Rapido: grandi quantità di informazioni.
• Preciso: non commette mai errori.
• Non ha spirito critico.

Programmi: algoritmi codificati in linguaggi comprensibili da un calcolatore.

Lingua molto formale, errori di ortografia/sintassi/grammatica possono compromettere il tutto.

Compito dell’informatico

Compito dell’informatico, strettamente in questo ordine:

• Ideare l’algoritmo: conoscere soluzione del problema con determinati passi, parte più difficile.
• Codificare l’algoritmo in un programma: tramite il linguaggio di programmazione, traduzione.

Passaggi:

• Capire e definire correttamente il problema.
• Ricavare l’algoritmo: difficile, richiede creatività e rigore.
• Scrivere il codice: è la parte più semplice ma deve essere corretto ed efficiente. Questi linguaggi sono una via di mezzo tra linguaggio umano e linguaggio del calcolatore.
• Compilazione: traduzione da linguaggio di programmazione a linguaggio macchina, eseguibile dal calcolatore, fa lui questa operazione.

Rappresentazione dell’informazione

0 1, stati di tensione. I calcolatori capiscono solo 0 e 1, ovvero bassa, 0V, e alta, 5V.

Non ci sono valori intermedi, es. 2.5V, perché potrebbe stararsi nel tempo.

Ogni 0 o 1 è un bit; 8 bit = 1 Byte = 2^8, può rappresentare 256 numeri diversi.

Noi usiamo solitamente la base 10, decimale.

La nostra notazione è posizionale: la posizione della cifra dà più o meno valore, significati diversi.

Abbiamo a disposizione 10 cifre, da 0 a 9. I numeri sono sequenze ordinate di cifre da 0 a 9.

Con m cifre in base 10 in un numero posso scrivere 10^m numeri differenti.

Se abbiamo base 2 con m cifre, posso fare 2^m numeri diversi.

Conversione: " 212310010 22 2° 811 2 1-+0+ 0 0+ +-= . =. .

• 1 Byte = 8 bit = 2^3 bit.
• 1 KiloByte (kB) = 10^3 Byte, in realtà 1024 Byte, ovvero 2^10 Byte, 2^13 bit.
• 1 MegaByte = 10^6 Byte, 1024 KiloByte, ovvero 2^20 Byte, 2^23 bit.
• 1 GigaByte = 2^33 bit.
• 1 TeraByte = 2^43 bit.

Lettere

Lettere: ASCII a 8 bit. Ogni carattere alfanumerico codifica specifico codice binario di 8 bit.

L’ASCII base non ha ad esempio i caratteri accentati, ha solo i caratteri base, byte che iniziano con lo 0, per gli altri caratteri si usano quelli che iniziano con 1 e ogni paese sceglie cosa farci, in base ai caratteri di cui necessitano.

Immagini

Immagini: ogni pixel è associato a un numero.

• Alto —> bianco; basso —> scuro, es. nero = 00000000.
• Ogni pixel: 8 bit = 1 Byte.
• Immagini pesanti perché ogni pixel pesa 1 Byte.
• Tre canali, colori, RGB, rosso - verde - blu: ogni canale 1 Byte, livello di saturazione del canale.
• Ogni pixel pesa 3 Byte. Più è alto il numero, più è saturato il colore.

Quindi in RGB ci sono 256^3 colori diversi, ovvero (2^8)^3, ovvero 2^24.

Non per forza la codifica è scritta pixel per pixel, bitmap.

Spesso conviene che codifiche riducono le dimensioni, in due modi:

• Lossless: codifiche permettono di comprimere l’immagine senza perdere informazioni.
• Lossy: codifiche comprimono l’immagine ma con perdita di qualità.

Ad esempio si possono esprimere funzioni per cui una certa zona è tutta di un certo colore, tipo jpg.

Sistemi informatici

Esecutore di un programma, pc, smartphone, sensori, server, ecc.

Sono costituiti da elementi complessi che comunicano tra loro, divisi in:

• Hardware: componenti fisici del sistema.
• Software: componenti non tangibili che vanno a utilizzare l’hardware, programmi.

Macchina o architettura di Von Neumann

Modello composto da quattro elementi funzionali:

• Unità di elaborazione, CPU: interpreta/esegue programmi, coordina la macchina, fa operazioni.
• Memoria centrale, MM, Main Memory: contiene dati e istruzioni, RAM, dati salvati temporaneamente. È una memoria volatile, informazioni restano solo su necessità.
• Interfacce delle periferiche: scambio di informazioni con mondo esterno, stampante, HDD, ...
• Bus di sistema: collegamenti tra gli altri elementi funzionali.

Memoria centrale

Contiene i programmi, sequenze di istruzioni, in esecuzione e i relativi dati.

Schema: sotto forma di sequenza di celle.

• Ogni cella di memoria h bit detti “parola”, “word”. h è il numero massimo di bit per ogni informazione.
• Ogni cella ha un indirizzo: servono altri k, numero di bit, per indicare gli indirizzi, 2^k spazi.

Se abbiamo 1024 celle abbiamo bisogno 1024 indirizzi diversi.

Nella cella: dati ed istruzioni.

Ci sono diversi tipi di memoria:

• RAM, random access memory, è volatile.
• ROM, read only memory, c’è solo in certi casi, non è volatile, è permanente, non si può cambiare.
• EPROM è intermedia, rimangono le informazioni ma sono riprogrammabili.

CPU

Sottoparti:

• CU, unità di controllo: preleva/decodifica le istruzioni da MM e invia segnali per eseguire istruzioni.
• Clock di sistema: sincronizza operazioni della CPU, determina l’ordine e il “quando”.
• ALU, unità aritmetico logica: esegue le operazioni logiche e aritmetiche.

Registri: memorie molto molto veloci che registrano informazioni utili alle operazioni:

• Registro dati, DR, lungo h bit, come word, memorizza il dato che arriva da MM.
• Registro indirizzi, AR, lungo k bit, memorizza indirizzo che arriva da MM.
• Registro istruzione corrente, CIR: lungo h bit, registra l’istruzione in esecuzione.
• Registro contatore di programma, PC: dice dove siamo arrivati nel programma.
• Registro interruzioni, INTR: indica stato delle periferiche, per rilevare i segnali.
• Registri intermedi: per capire cosa succede nella ALU.
• Registri di stato: verifica se operazione è andata a buon fine o meno.
• Registro operando: dove vengono inseriti i dati per eseguire certa operazione, es. somma.
• Registri di lavoro: contiene altre informazioni utilizzate di frequente.

Bus di sistema

Bus di sistema: insieme di connessioni tra due entità funzionali che trasferiscono informazioni.

Ogni informazione passa attraverso bus di sistema.

Ci sono solo due tipi di connessione:

• CPU, leader, <-> MM, follower.
• CPU, leader, <-> Interfaccia periferica, follower.

CPU è leader perché tutto passa da lei ed è l’unica che può dare istruzioni.

Non esiste connessione diretta tra MM e periferica.

Tre tipi di linee per scambiare tre tipi di informazioni differenti:

• Bus dati.
• Bus indirizzi.
• Bus controlli, si occupa di controllare gli stati delle operazioni, se andate a buon fine.

Lettura e scrittura su memoria

Lettura:

1. Passo indirizzo da cui voglio leggere tramite bus indirizzi.
2. La CPU dice alla MM di leggere l’informazione in quell’indirizzo con bus controlli.
3. MM riceve l’istruzione e passa l’informazione sul bus dati.
4. MM dice che ha inviato l’informazione, bus controlli.

Scrittura:

1. Passo il dove vogliamo scriverla, quindi inviamo l’informazione indirizzo.
2. Passo il dato che voglio scrivere, bus dati.
3. Dico di scrivere con bus controlli.
4. MM scrive e dà l’ok su bus controlli.

Interfacce

Interfacce: collegano il calcolatore alle periferiche.

Ogni interfaccia ha registri per scambio dati con periferica:

• Registro dati della periferica, PDR: per scambio dati con periferica.
• Registro comandi della periferica, PCR: contiene comandi dati dalla periferica.
• Registro di stato, PCS: contiene informazioni sullo stato della periferica.

Vedi schemi vari sulle slide.

Programmi nella macchina di Von Neumann

Istruzioni: codificate in binario e sono salvate in parole nella MM.

Divise in:

• Codice operativo, 4 bit: indica il tipo di istruzione, cosa fare.
• Due zeri, 00.
• Indirizzo operando, 10 bit: indica il dove eseguire l’operazione.

Codici operativi, istruzioni eseguibili da CPU:

• Lettura da periferica.
• Scrittura su periferica.
• Load: caricare dato da MM a Registro CPU.
• Store: salvare dato su MM da Registro CPU.
• Operazioni aritmetiche.
• Istruzioni di salto: per cambiare flusso di esecuzione del programma.

Tre fasi per eseguire operazione

Fetch:

1. Acquisizione dell’istruzione dalla MM.
2. Trasferimento da PC a AR dell’indirizzo della cella contenente l’istruzione da eseguire.
3. Lettura istruzione dalla MM nella cella all’indirizzo in AR.
4. Spostamento istruzione da DR a CIR poiché è l’istruzione in esecuzione.
5. Incremento PC.

Decodifica: legge dal CIR il codice operativo.

Esecuzione: dipende dall’istruzione specifica.

Ricorda: due istruzioni carica possono avere codici diversi a seconda del luogo di riferimento.

Es.

• 0000 —> carica nel registro A.
• 0001 —> carica nel registro B.

n

Linguaggi di programmazione

I linguaggi di programmazione permettono ad un calcolatore di eseguire le istruzioni.

• Basso livello: linguaggio vicino al linguaggio macchina.
• Alto livello: linguaggio vicino alla lingua comune parlata.

~ Linguaggio macchina: poche istruzioni, difficile codificare algoritmi e interpretare codice.

È un linguaggio:

• Preciso.
• Dotato di controllo completo di tutte le risorse.

~ Alto livello:

• Rimane preciso, ma più sintetico, tipo: fai la somma, senza registri ecc.
• Riferimenti simbolici, non dico ogni volta dove certo dato, ma solo come si chiama, es. ‘a’.
• Istruzioni vicine a linguaggio naturale, più comprensibile.

Traduzione: eseguita da programma detto compilatore: linguaggio alto livello —> macchina.

Linguaggio C (1972)

Pensato per scrivere sistemi operativi, poi adottato anche per programmi “generici”.

Si interfaccia all’hardware in un modo ancora più semplice della macchina di Von Neumann, sempre solo due periferiche, un solo input e un solo output.

Utilizziamo variabili, equivalenti dei fogliettini visti in precedenza: corrispondono a una cella di memoria nella macchina C.

Ogni variabile —> nome: lettere, cifre, _ : carattere iniziale esclusivamente lettera; no spazi.

Case sensitive, mai