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, che elaborano informazioni.

Algoritmo: procedimento di calcolo per la risoluzione di un dato problema. Progettazione / efficienza / strutture dati / complessità.

Codifica: consiste nell’assegnare un bit alle alternative. Rumore: che avvicina sequenze di "1" ad insiemi di "1". Lunghezza fissa / lung. variabile. Flessibili ed efficienti. Compresso da elaborare.

Def. di computer

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

Tramite bit.

Algoritmo: procedimento di calcolo per la risoluzione di un dato problema.

La progettazione / efficienza / quantità dati / computabilità (ambiente) (si può calcolare o no?).

Codifica: consiste nell'assegnare un bit alle alternative.

Num. di arri: la sequenze di 1 ad insiemi di 0.

Lunghezza fissa / lung. variabile dipende dal n° di bit.

Flessibili ed efficienti.

Complesso da elaborare.

Programma

Programma: sequenza di istruzioni che, 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: analisi struttura 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

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

Rapp. complemento ad uno.

N^o positivi direttamente convertiti in base 2.

Negativi: 111...1 - |x| (inverto i bit di x).

341₁₀ 100010₂.

-341₁₀ 1111111 - 100010 = 11011101.

Problemi:

• 2 rapp. per lo zero.
• Operaz. aritmetiche non immediate.

Rapp. complemento a due

Rapp. complemento a due.

N° neg. convertiti direttamente in base 2.

1° neg. 111...1 (-1) + 1, ignorando overflow.

3410 00101010.

-3410 11111111 - 00101010 + 00000001 = 11011111.

Intorno allo 0 il comp. è naturale, le operazioni possono essere svolte tranquillamente ignorando l'overflow.

1 1 1 1 1 1 1 0 0 0 1 + 1 1 1 0 1 0 0.

Due numeri con n bit superano il limite 2ⁿ-1 esponenziale e quanto avviene si contano le n cifre meno significative.

Tecnica dell'eccesso

Tecnica dell'eccesso: sommo una costante a tutti i numeri.

0-> neg. 1-> pos.

Numeri non interi

Numeri non interi.

Tutti nell'IR razionale (Es: π, √2, 3/4, ...).

Rappresentiamo un sottoinsieme di IR.

Rapp. virgola fissa

Rapp. virgola fissa.

Separatore in una posizione fissa.

Parte della codifica indica la posizione del separatore.

• Quanti bit parte intera e parte frazionaria.
• Numero negativi complemento a due.

N₂ = x₁₀ × 2^k       k bit frazionari.

5,75    2³ = 4610   ⇒ 001011110₂.

Non adatto per il calcolo scientifico.

Operazioni efficienti.

2 - n° medio gradi / precario indipendente dal 1 x.

- 0 -> pos 1 -> neg.

- n° primo 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, 8, 23).
• Doppia precisione (64 bit, 1, 11, 52).
• (16 bit opera 128).

L=+1023.

Architettura

Architettura: insieme dei criteri di base ai quali è stato progettato sottosistemi costituenti loro rapporti interfunzionali.

Von Neumann, EDVAC 1945, general purpose.

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

CPU

CPU.

ALU (Unità aritm.-logica) - esegue le operazioni.

CU (Unità controllo) - decodifica istruzioni e coordina le altre componenti.

Input: BIT, istruzioni.

Output: segnali di controllo o dati estratti da istruzioni.

I registri

I Registri: insieme di elementi di memoria memorizzano temporaneamente dati ed istruzioni (agevolandone il passaggio).

Da cui un bit di controllo determina: lettura: output e il dato memorizzato; scrittura: dato memorizzato sostituito dai dati in ingresso.

Elementi logici bistabili formano i registri, la commutazione nello stato logica forma un cappio (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 farà accesso per leggere e scrivere.

CPU comunica con dispositivi I/O tramite apposite porte.

Instruction set

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 muove dati.
• Controllo di programma: modifica di istruzioni, tramite salti: - condizionati.

Modalità di indirizzamento

Modalità di indirizzamento: (riferiti alle istruzioni).

• Implicito: operando in posizione fissa.
• Immediato: operandi sono valori costanti.
• Diretto: istruzione al indirizzo codifica diretta di indirizzo di memoria.
• Indiretto: istruzione al indirizzo codifica di indirizzo di memoria.
• Indicizzato: combinazione di indirizzo base e valore di un registro.

Esecuzione istruzione

Esecuzione istruzione: si divide in microoperazioni.

• Fetch: contenuto dell'indirizzo memorizzato nel PC viene copiato nel IR (insieme registri).
• 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

Gerarchie di memoria.

Collo di bottiglia → + difficile da migliorare.

Caratteristiche memorie: latenza: tempo di pausa tra CPU e arrivo dati.

Larghezza di banda: quantità di dati trasferibili in tempo (bit x secondo) → facile da migliorare.

Tipologie di memorie: zpq - Ram - Rom.

Memoria statica: è ALTI e circuiti logici lidabili.

" dinamica: condensatori è BASSO.

Memoria gerarchica efficiente tramite:

• Principio località temporale: accedo ad un dato e poco dopo ancora.
• " " spaziale: accenno ad un dato ed ai dati vicini.

HIT => se il dato è presente nella cache.

Miss => se " " non è " " " " viene copiato dalla RAM nella cache.

Operazioni di scrittura:

• Write-through: i dati vengono realti 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 singole -> pipelining -> parallelismo.

• SISD (Single Instruction Single Data) nessun parallelo.
• 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

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 (monocromia).

Metodi di compressione

Metodi di compressione:

• Lossless: senza perdita di qualità originale = decompr.
• Lossy: con perdita di qualità originale ≠ decompr.
• A) Valore pixel - n° di volte da comprimere. Applicazioni di valori ed usato per immagini semplici. PNG/GIF/BMP.
• B) Tengono conto dei limiti visivo umano e vanno a comprimere lì. JPEG -> efficiente nelle foto. Divido l’immagine 8x8 e ciascun blocco contiene 64 elementi che l’ora rappresentano.

Immagini vettoriali

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

PDF/DXF/Ritaglio illimitato.

Programmazione

Programmazione.

bin(_DECIMALE) -> binario.

oct() -> ottario.

hex() -> esadecimale.

/_0b n^o binario -> decimale.

_0o n^o ottario -> "".

_0x n^o esadecimale -> "".

Ricerca lineare

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

Ricerca binaria.

Nel caso peggiore, e supponendo n = 2^k la dimensione dell'intervallo si riduce secondo lo schema.

n, n/2, n/4, n/8, ..., 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, I can't transcribe or interpret the content of this image.

Riepilogo degli algoritmi di ordinamento

Merge sort usa uno spazio aggiuntivo O(n).

Un algoritmo è stabile quando mantiene l'ordine tra elementi equivalenti 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).

Complessità sui grafi

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).

L’analisi è identica a quella della BFS.

Complessità

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à

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).

Classi e oggetti

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

def __init__(self, ...):

def __str__(self):

def __set__(self, ...):

def __get__(self, ...):

def __iter__(self)

def __next__(self)

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

class Car(object)

class Truck(Car)

Iteratori e generators

Iteratori: oggetti con le caratteristiche di un generatore.

(Restituisce di oggetti iterabili uno alla volta) => metodo next.

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

List comprehension

List comprehension: tecnica per creare liste nel linguaggio python.

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

>>> squares = [n ^xx 2 for i in mylist]

>>> squares (. . . . . . . .) -> generator comprehension

>>> [4, 16, 36]

Insiemi

Insiemi: collezione mutabile senza ordine di elementi duplicati.

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

>>>>> S = {} insieme vuoto.

>>>>> S = set () insieme vuoto.

Obiettivo: verificare se x è presente nell' insieme.

not 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 recendo il codice.

Ricerca lineare

Ricerca lineare.

17 48 26 53 56 57 60 65 67 74 68 68 85 57 98.

53 65 53 18 26.

50: 65 53 18 26.

12: 65 53 18 17.

Problema lineare 0 29 1 N 2 38 3 75 4 51 5 64 6 18 7 76 8 74 9 10 66 11 64.

74 -> 29 75 51 09 18 76 74.

72 -> 24 NONE.

85 -> 57 24 NONE.

Funzione hash / tabella

Funzione HASH / tabella.

1412 =>2833.

Alg. ricerca.

85 | 85 | NONE.

Alg ordinamento

Alg ordinamento.

Bubble sort.

1VS1.

Insertion sort.

Scala.

Selection sort.

Più grande vs tutti.

Shell sort.

Gap.

Merge sort.

Unione 2 parti (n log n).

Quick sort.

Pivot.

87 ↓

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

50     30.

73 87 88 94.

Alberi min heap

Alberi min heap.

26 71 72 58 62 81 51 82.

26587151626151 72.

Albero binario

Albero binario.

11, 20, 37.

20 5537646561305892.

Albero di ricerca

Albero di ricerca.

618130426237581864.

Grafi

Grafi.

Ordinamento topologico.

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

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

I.

Alg. di PRIM.

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

2330, 7, 33, 12.

30, 33, 12, 22, 13.

28, 28, 34.