Appunti Informatica B

Infobinformatica: scienza dell'informazione

Capire i dati, quali sono importanti e cosa farci. L'informazione può essere concreta o astratta.

Cosa fare con informazione?

• Rappresentarla - sotto forma di immagine, suono, parola, ecc.
• 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)
• Costrutto condizionale (istruzioni eseguite a volte alcune, a volte altre)
• Costrutto iterativo (ripetizione di più volte della stessa operazione)

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 seguiti dall'alto in basso, quindi devono avere coerenza e ordine temporale. 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 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'è.

Programmi e calcolatori

Ma noi vogliamo usare il calcolatore, quindi da algoritmo dobbiamo passare al codice. Il calcolatore è rapido: grandi quantità di informazioni. Preciso: non commette mai errori. Non ha spirito critico. Ha programmi: comprensibili da un calcolatore. Algoritmi codificati in linguaggi. Lingua molto formale, errori di ortografia/sintassi/grammatica possono compromettere il tutto.

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

Il calcolatore capisce solo 0 e 1, ovvero stati di tensione 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⁸ (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 posso scrivere 10^m numeri differenti. Se abbiamo in base 2 con m cifre, 2^m numeri diversi.

Conversione

"2123₁₀₀₁₀ 22 2⁰ 811 2 1 + 0 + 0 + 0 = . =. .1 Byte = 8 bit = 2³ bit 1 Kilobyte (kB) = 10³ Byte (in realtà 1024 Byte, ovvero 2¹⁰ Byte, 2¹³ bit) 1 Megabyte = 10⁶ Byte (1024 Kilobyte, ovvero 2²⁰ Byte, 2²³ bit) 1 Gigabyte = 2³³ bit 1 Terabyte = 2⁴³ bit.

Lettere: ASCII

Ogni carattere alfanumerico è associato a un 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

Ogni pixel è associato a un numero. Alto –> bianco; basso –> scuro (es. nero = 00000000). Ogni pixel: 1 Byte (WB) 8 bit = 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. In RGB ci sono 256³ colori diversi, ovvero 2²⁴.

Non per forza la codifica è scritta (bitmap). Spesso conviene codifiche che riducono le dimensioni, in due modi: lossless: senza perdere informazioni - permettono di comprimere l'immagine. Lossy: perdita di qualità - comprimono l'immagine ma con una 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, sotto forma di dati in esecuzione e la sequenza di celle:

Ogni cella di memoria ha un numero massimo di bit detto “parola” o “word”. Ogni cella ha un indirizzo: 2^k spazi. Se abbiamo 1024 celle abbiamo bisogno di 1024 indirizzi diversi. Ci sono diversi tipi di memoria:

• RAM (random access memory), è volatile.
• ROM (read only memory, c'è solo in certi casi) è permanente, non è volatile, 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:

• Registri di stato: verificano se operazione è andata a buon fine o meno.
• Registri operando: dove vengono inseriti i dati per eseguire certa operazione (es. somma).
• Registri di lavoro: contengono altre informazioni utilizzate di frequente.

Bus di sistema

Insieme di connessioni tra due entità funzionali che trasferiscono informazioni. Ogni informazione passa attraverso il bus di sistema.

Ci sono solo due tipi di connessione:

• CPU (leader) <-> MM (follower)
• CPU (leader) <-> Interfaccia periferica (follower)

La CPU è l'unica che può dare istruzioni perché tutto passa da lei ed è il leader. 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 l'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. La MM passa l'informazione sul bus dati.
4. La MM dice che ha inviato l'informazione (bus controlli).

Scrittura:

1. Passo l'indirizzo dove vogliamo scriverla, quindi inviamo l'informazione che voglio scrivere (bus dati).
2. Passo l'informazione che voglio scrivere (bus dati).
3. Dico di scrivere (bus controlli).
4. La MM scrive e dà l'ok su bus controlli.

Interfacce

Collegano il calcolatore alle periferiche esterne. 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.

Programmi nella macchina di Von Neumann

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

Divise in:

• Codice operativo (4 bit): indica il tipo di istruzione, cosa fare.
• Due zeri (00)
• Indirizzo operando (10 bit): indica 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 un'operazione

1. Fetch: Acquisizione dell'istruzione dalla MM
   • Trasferimento dell'indirizzo della cella contenente l'istruzione da eseguire da PC a AR.
   • Lettura istruzione dalla MM nella cella all'indirizzo in AR.
   • Spostamento istruzione da DR a CIR poiché è l'istruzione in esecuzione.
   • Incremento PC.
2. Decodifica: il CIR legge il codice operativo.
3. Esecuzione: dipende dall'istruzione specifica.

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

Linguaggi di programmazione

Permettono ad un calcolatore di eseguire le istruzioni.

Basso livello: linguaggio macchina

È un linguaggio vicino al calcolatore, con poche istruzioni, difficile da codificare algoritmi e interpretare codice

• Preciso
• Controllo completo di tutte le risorse

Alto livello: linguaggio comune

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 al linguaggio naturale, più comprensibile.

Traduzione: eseguita da programma detto compilatore: alto livello –> linguaggio 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 solo due periferiche, un solo input e un solo output.

Variabili

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

• Ogni variabile ha un nome (lettere, cifre, _ : carattere iniziale esclusivamente lettera; no spazi). Linguaggio è “sensibile” alle maiuscole/minuscole (case sensitive).
• “Variabili” perché gli si può cambiare nome/valore.
• Posso utilizzare il nome dato alla cella per eseguire le operazioni su di essa.

Bisogna definire il tipo di dato che una cella può contenere (lettere, numeri interi/decimali, ecc.):

• Così posso conoscere:
  • Operazioni eseguibili per quella cella.
  • Dimensione di quella cella (se è presente un solo carattere, la cella dovrà contenere solo 8 bit).

Fortemente tipizzato

Il C è fortemente tipizzato, poiché devo sempre specificare il tipo di una variabile.

Tipi semplici

• char: caratteri della tabella ASCII, corrisponde a una lettera o un numero compreso tra 0 e 255.
• int: numeri interi il cui massimo e minimo dipendono dalle dimensioni della parola della macchina.
• float: numeri decimali a singola precisione (quanti numeri posso esprimere).
• double: numeri decimali a doppia precisione rispetto a float.

Dichiarare variabile

Bisogna riservare una parte di memoria per la cella. Bisogna definire:

1. Tipo variabile
2. Nome variabile

Inizializzare: dare valore a variabile, altrimenti randomico.

Istruzioni

Frasi eseguibili del linguaggio; ogni istruzione termina con simbolo “;”.

Assegnamento valore a variabile: simbolo “=” seguito da valore accettabile o espressione. Ogni volta che assegno un valore a una variabile, la cancello quello che c’era prima. Assegnamento fa due cose in ordine:

1. Valuta espressione e legge eventuali variabili richieste.
2. Memorizza il risultato nella cella in questione.

ATTENZIONE: “=”: assegnamento, “==”: confronto logico. Divisione tra int dà un int, per un float deve esserci almeno un float nell’espressione. “%” (modulo): per ottenere il valore del resto della divisione intera.

Input e output

Istruzioni in ingresso e in uscita, visibili nel TERMINALE:

• printf: scrivere a schermo
• scanf: leggere dei dati

Esempio:

1. printf (stringaControllo); //stringaControllo è sequenza di caratteri racchiusa da doppi apici “...”.
2. scanf ("%d", &a); //& è l'indirizzo della variabile a, non la variabile a.

Il C è un linguaggio sequenziale: dall’alto al basso. Commenti: servono a spiegare ciò che si fa, il programma non li legge, li ignora. Due modi:

• /* ... */ su più righe
• // su una riga

#include serve a includere le librerie, ovvero dei codici pre stabiliti per utilizzare le varie funzioni.

void main() non restituisce valori alla fine int main() restituisce un valore di controllo, return 0 è il termine del programma. La prima parte è dichiarativa: dichiaro tutte le variabili che mi servono poi nel programma.

• %d —> int
• %f —> float
• %c —> char
• %s —> stringa (sequenza di caratteri)