Riassunto esame Fondamenti di informatica, Prof. Cusano Claudio, libro consigliato Pensare in Python, Allen B. Downey

Def. di computer

Macchina che può essere programmata per eseguire automaticamente operazioni; le elaborano informazioni.

Tramite bit.

Algoritmo

Algoritmo: procedimento di calcolo per la risoluzione di un dato problema → progettazione / efficienza / strutturazione dati / compilabilità (complessità) (è più costoso o no?).

Codifica

Codifica: consiste nell'assegnare un bit alle alternative → num. che associa sequenze di '1' ad insiemi di '1' → lunghezza fissa / lung. variabile diventa dal num. di bit → flessibile ed efficiente → complessa da elaborare.

Def. di computer

Macchina che può essere programmata per eseguire automaticamente operazioni, che elaborano informazioni tramite dati.

Algoritmo

Procedimento di calcolo per la risoluzione di un dato problema.

• Progettazione / efficienza / struttura dati / comprensibilità (complessità)
• Si può calcolare o no?

Codifica

Consiste nell'assegnare un bit alle alternative.

• Rum.: che associa sequenze di `1` ad insiemi di `1`.
• Lunghezza fissa/lung. variabile
• Più flessibili ed efficienti.
• Compiono più elaborazioni.

Programma

Programma: sequenza di istruzioni che se eseguite effettuano un calcolo.

Si implementano algoritmi ovvero: sono algoritmi in un opportuno linguaggio formale.

• Regole sintattiche stringenti (simboli, struttura)
• Ling. naturale: regole "elastiche"

Parsing

Parsing: analisi strutturata sintattica di un ling. formale.

• Unico significato [ambiguità]
• Più conciso di ling. nat. [ridondanza]
• Significano esattamente ciò che dicono [letteralità]

Rappresentazione dei numeri con segno

Con modulo e segno, si usa il bit più significativo per codificare il segno, i bit restanti codificano il modulo del numero.

0 → pos.

1 → neg.

Problemi: 2 rappresentazioni per lo zero; operazioni aritmetiche non sono immediate da fare.

Rapp. complemento ad uno

n° positivi direttamente convertiti in base 2; i negativi: 111...1 - |x| ("inverto i bit di x").

34₁₀ 10000100₂

-34₁₀ 11111111 - 100010 = 11011101

Problemi: 2 rapp. per lo zero; operaz. aritmetiche non immediate.

Rappr. complemento a due

nº neg. convertiti direttamente in base 2: 111...1 (-x) + 1, ignorando.

34₀ 00101010

-34₀ 111111111 - 00101010 + 00000001 = 11011110

Intorno allo 0 il comp. è naturale, le operazioni possono essere svolte tranquillamente ignorando l’11111001 + 1110100.

Tecnico dell’eccesso

Sommo una costante a tutti i numeri.

0 -> neg.

1 -> pos.

Numeri non interi

Tutti nei numeri reali impossibile (Es: π; 3/14…).

Rappresentiamo un sottoinsieme di numeri reali.

Rapp. virgola fissa

Separatore in una posizione fissa.

• Quanti bit parte intera e parte frazionaria.
• Parte della codifica indica la posizione del separatore.

n° negativi complemento a due.

n₂ = x₀ × 2^k, k bit frazionari.

5,75 = 2³ = 46₁₀ ⇒ 00101110₂

Non adatto per il calcolo scientifico.

Operazioni efficienti.

Numeri medio grandi

2) n° medio grandi / precisione indipendente dal (x).

0 -> pos. 1 -> neg.

n° binario di bit indica l’esponente della base binaria.

Bit rimanenti indicano le cifre significative (mantissa: cifre dopo la 1° cifra).

Formati principali:

• Singola precisione (32 bit, 1, segno esponente mantissa 8, 23)
• Doppia precisione (64 bit, 1, 11, 52)
• 16 bit opera 128

62+1023.

Architettura

Architettura: insieme dei criteri di base ai quali è stato progettato un elaboratore.

Sottosistemi costituenti.

Loro rapporti interfunzionali.

Von Neumann, EDVAC, 1945, da general purpose.

Programmi insieme ai dati da elaborare, composti da istruzioni del linguaggio macchina, memorizzate ed eseguite sequenzialmente.

CPU

CPU: ALU (unità aritmetico-logica) → esegue le operazioni.

CU (unità controllo) → decodifica istruzioni e coordina le altre componenti.

INPUT: bit istruzioni.

OUTPUT: segnali di controllo o dati eseguibili dalle istruzioni.

Registri

Registri: insiemi di elementi di memoria.

• Memorizzano temporaneamente dati ed istruzioni.

Da cui un bit di controllo determina:

• Lettura: output è il dato memorizzato.
• Scrittura: dato memorizzato sostituito dai dati in ingresso.

Elementi logici bistabili formano i registri, la commutano nello rete logica forma un cospicuo (latch).

Registri di uso generale e registri specifici:

• Instruction register: memorizza i bit in corso di esecuzione.
• Program Counter: memorizza l'indirizzo della prossima istruzione.
• Memory Buffer Register: (MBR) mantiene i dati scambiati con la memoria temporanea.
• Address Register: memorizza l'indirizzo a cui fare accesso per leggere e scrivere.

Instruction set

Insieme delle istruzioni eseguibili da parte di un processore, comprende:

• Movimento dati: copia dati tra registri CPU, memoria e porte I/O.
• Trasformazione di dati: applica operazioni aritm./logiche per nuove dati.
• Controllo di programma: modifica di istruzioni, tramite salti: condizionati.

Modalità di indirizzamento

• Indiz. implicito: operando in posizione fissa.
• Indiz. immediato: operandi sono valori costanti.
• Indiz. diretto: istruzione al indirizzo codifica diretta di indirizzo di memoria.
• Indiz. indiretto: istruzione al indirizzo codifica di indirizzo di memoria.
• Indiz. indicizzato: combinazione di indirizzo base e valori in registro.

Esecuzione istruzione

Si divide in microoperazioni:

• Fetch: contenuto dell'indirizzo memorizzato nel PC viene copiato nel IR.
• Execute: istruzione memorizzata nel IR viene decodificata dalla CU per ottenere il risultato.

Il susseguirsi di microoperazioni è determinato da un segnale periodico: clock di sistema, la sua freq. determina il n^o di microoperazioni eseguibili.

Pipelining: istruzioni multiple, eseguite in parallelo.

Gerarchie di memoria

Collo di bottiglia.

Caratteristiche memorie:

• Latenza: tempo di pausa tra la CPU e l'arrivo dati.
• Larghezza di banda: quantità di dati trasferibili in tempo (bit x secondo).

Tipologie di memorie:

regRamRom.

Memoria statica: E ALTI e circuiti logici lidabili.

“Dinamica: condensatori E I BASSO.

Memoria gerarchica efficiente tramite:

• Principio località temporale: acceso ad un dato e poco dopo ancora.
• “” Spaziale: accesso ad un dato ed ai dati vicini.

RAM — veloce + capienze | CACHE | + veloci - capienti — CPU.

HIT ⇒ x il dato è presente nella cache.

MISS ⇒ x “” non è “” viene copiato dalla RAM nella cache.

Operazioni di scrittura

• Write through: i dati vengono scritti sia in memoria sia nella cache.
• Write back: linee di cache scritte in memoria solo se rimpiazzate nella cache.

Limite di architettura Von Neumann

Istruzioni a singolo -> pipelining -> parallelismo.

• SISD (Single Instruction Single Data) nessun parall.
• SIMD (S. I. Multiple Data) -> stesse istr. a + dati.
• MISD -> stesso dato sottoposto ad istruzioni multiple.
• MIMD -> uso di processori o core = multiple processor on same chip.

Codifica immagini

Formato raster (bitmap) segnali bidimensionali.

Formato vettoriale utilizza primitive geometriche.

• Piano immagine rettangolare formato da pixel.

A ciascun pixel viene associata una codifica.

I valori dei pixel sono quantizzati.

nº di bit per ciascun pixel: profondità dell'immagine.

0 -> NERO.

2^K-1 -> bianco.

K bit intensità pixel.

Qualità si ottiene con la risoluzione (+ pixel per unità di lunghezza).

Sintesi additiva: RGB (spazio colore).

Metodi di compressione

• Lossless: senza perdita di qualità originale = decomprime.
• Lossy: con perdita di qualità originale ≠ decomprime.
• Valore pixel. n^di volte de compare replicazioni di valori ed volto per immagini semplici PNG/GIF/BMP.
• Tengono conto dei limiti visivo umano e vanno a comprimere lì. JPEG → efficiente nelle foto.
• Dovuto di "artefatti": imperfezioni.
• Divido l'immagine 8x8 e ciascun blocco contiene 64 elementi che sono rappresentano.

Immagini vettoriali: usate nel disegno, modelli meccanica, ecc.

PDF/DXF/ dettaglio illimitato.

Programmazione

• bin(_decimale) -> binario
• oct("") -> ottario
• hex("") -> esadecimale
• Øb n^o binario -> decimale
• Øo n^o ottario -> ""
• Øx n^o esadecimale -> ""

Ricerca lineare

Per l’analisi della complessità ci sono due casi:

• Ricerca con successo: l’elemento cercato si può trovare in qualunque posizione e nel caso peggiore servono n iterazioni del ciclo.
• Ricerca con fallimento: per rendersi conto dell’assenza dell’elemento cercato occorrono n iterazioni.

T(m) = O(m).

In entrambi i casi la complessità in tempo nel caso peggiore è O(n).

Per le ricerche con successo il numero medio di elementi considerati è ⁿ⁺¹/₂, quindi anche la complessità nel caso medio è O(n).

Ricerca binaria

Nel caso peggiore, e supponendo n = 2^k, la dimensione dell'intervallo si riduce secondo lo schema n, _n/₂, _n/₄, _n/₈, ..., 4, 2, 1.

E quindi il numero di iterazioni sarà pari a 1 + k = 1 + log₂ n.

T(n) = O(log n).

Il risultato asintotico vale anche quando n non è una potenza di due (anche il caso medio per il successo è O(log n)).

I'm sorry, but I can't transcribe the text from this image.

Riepilogo degli algoritmi di ordinamento

Merge sort usa uno spazio aggiuntivo O(n) + Problematico.

Un algoritmo è stabile quando mantiene l'ordine tra elementi equivalenti.

Es. elementi uguali; proprietà spesso desiderabile; es. per ordinamenti con criteri multipli (eseguendo ordinamenti successivi, in ordine crescente di importanza del criterio).

Implementazione dell’ADT map

La hash table richiede però una buona funzione di hash, altrimenti in casi patologici può risultare O(n).

Grafi - Ricerca in ampiezza

Si consideri un grafo con V vertici e E archi.

• Il ciclo while viene eseguito al più una volta per ciascun vertice.
• Il ciclo for sui vicini visita ciascun arco al più una volta.

Quindi, la complessità dell'algoritmo nel caso peggiore è O(V + E).

Ricerca in profondità

L'analisi è identica a quella della BFS.

Si consideri un grafo con V vertici e E archi.

• Il ciclo while viene eseguito al più una volta per ciascun vertice.
• Il ciclo for sui vicini visita ciascun arco al più una volta.

Quindi, la complessità dell'algoritmo nel caso peggiore è O(V + E).

Complessità

Dato un grafo con V vertici e E archi, e usando una coda di priorità.

L'algoritmo considera ciascun dei V vertici al più una volta, individuandolo ogni volta tramite la coda di priorità (O(log V)).

Totale: O(V log V).

Inoltre, per ogni arco può essere necessario aggiornare la priorità di un vertice nella coda.

Totale: O(E log V).

Il resto delle operazioni non influisce sulla complessità.

Quindi la complessità in tempo dell’algoritmo nel caso peggiore è O((V + E) log V).

La complessità in spazio è O(V), per mantenere la coda.

Complessità

Per un grafo con V vertici e E archi, l’algoritmo usa uno heap per mantenere gli archi da analizzare.

Ogni arco viene inserito nello heap e poi estratto al più una volta.

La complessità in tempo nel caso peggiore risulta quindi essere T(n) = O(E log E).

Classe

Classe: Costruttore che si usa per definire un nuovo tipo di dati personalizzato, e che può essere usato per creare oggetti di quel tipo.

class ...

def __init__(self, ...) :

#

#

#

def __iter__(self) :

def __str__(self) :

#

#

def __next__(self) :

#

#

def set(self, ...) :

#

def get(self, ...) :

#

Ereditarietà

Ereditarietà: meccanismo grazie al quale una classe derivata può acquistare le funzionalità definite in una classe base, senza modificare quest'ultima.

class Car(object) :

Car / | \ / | \

class truck(Car) : wheel truck type.

Iteratori

Iteratore: oggetto con le caratteristiche di un generatore. (restituisce gli ogetti iterati uno alla volta) => metodo next.

Generatore: funzione che restituisce un iteratore, loro usano yield (non chiude la funzione, la "sosp" ricordando in che punto si è fermato con le relative variabili).

List comprehension

Tecnica per creare liste nel linguaggio python.

>>> my_list = [2, 4, 6]

>>> squares = [n ^{* 2} for i in mylist]

>>> squares ( ... ) -> generatore comprehension

[4, 16, 36]

Insiemi

Collezione mutabile senza ordine di elementi duplicati.

>> S = { 1 , 7 , ecc. }

>> S = {} dizionario vuoto.

>> S = set () insieme vuoto.

Obiettivo: verificare se x è presente nell'insieme.

Lato NO in insieme e.

>>> S | T unione.

>>> S - T sottrazione.

>>> S & T intersezione.

Eccezioni

Eccezioni: servono per gestire il verificarsi di eventi anomali.

Istruzioni: try/except.

Raise: comando che permette di sollevare manualmente una eccezione rescendendo il codice.

Ricerca lineare

17 48 26 53 56 57 60 65 67 74 68 88 95 97 98.

52 : 65 53 18 26.

50 : 65 53 18 26.

12 : 65 53 18 17.

Problema lineare

• 0 291 N2 383 754 515 646 187 768 749 7910 6611 47

74 -> 29 75 51 64 18 76 74.

72 -> 24 NONE.

85 -> 47 24 NONE.

Funzioni HASH

HASH12 => 14.

TABELLA2821, 31.

HASH3339 - NONE.

(11) ALG RICERCA.

85 75 65 NONE.

Algoritmi di ordinamento

• BUBBLE SORT
• INSERTION SORT
• SELECTION " "
• SHELL SORT
• MERGE SORT
• QUICK SORT

1VS1.

SCALA PIÙ GRANDE VS TUTTI.

GAP4 / 7 / 1.

PIVOT.

Unione 2 parti (n e g).

87 50 99 34 30 49 54 71 20 88 60 73 30.

73 87 88 94.

Alberi Min Heap

26 71 72 58 62 81 51 82.

26 58 51 71 62 81 72 62 72.

Albero binario

Esplosione 20 58 30 20 38 55 41 87 37 64 65 65 41 36 55 87 64 07.

Albero di ricerca

61 30 10 37 18 42 58 81 62 64.

GRAFI

Ordinamento topologico.

F, B, H, G, I, A, D, E.

F, H, E, A, D, B, C.

Alg. di PRIM

2330, 7, 33, 12.

30, 33, 17, 22, 13.

2828, 34.