School notes

Hello there again! This will be the site where I'll push my notes on various courses I follow in my university, everything not uni-related will not be present here and it will be either on the main site or the writeup site. The notes are free and you can contribute in other folders (for example this folder), you can use these notes however you want!

Mind that this is technically a different site from the principal one, so I'm giving you this link in case you get lost and you are too lazy to edit the url.

Information theory

These notes are about the course "INFORMATION AND TRANSMISSION THEORY", which is a fundamental course to see the practical aspect of statistics, and it plays an important role in decision models and machine learning.

There are some mathematical aspects that need to be discussed in order to understand better the course, so I will cover some of it in the first post of this section.

Abstract algebra

The topics I'll cover in this post are a mere introduction to the topic of abstract algebra, this subject is a really deep branch of mathematics and its goal is to generalise stuff as much as possible. Basically if you prove a nice result in a general context, you won't need to prove the same result again in a more specific case.

Note that I will update the page whenever some aspects are mentioned further in the course.

Algebraic structures

This is a really simple definition, an algebraic structure is a tuple that is formed by a set and a binary operation in this set.

If you wonder what is a binary operation don't worry, this is also really simple: Let \(S\) be a set, let \(*\) a function, \(*\) is a binary operation on \(S\) if and only if it's defined this way: \(*: S \times S \to S\)

By this definition we have that \((S, *)\) is an algebraic structure.

Notation: given an algebraic structure \((S,*)\) and \(s_1, s_2 \in S\), we will say that \(*(s_1,s_2) = s_1*s_2\) to make things look nicer.

Monoid

Let \((S, *)\) be an algebraic structure, it's a monoid if and only if:

\(\exists e \in S\) \(\forall s \in S\) \(s*e=e*s=s\)
\(\forall a,b,c \in S\) \(a*(b*c) = (a*b)*c\) Proposition: the element \(e \in S\) such that property 1 holds is unique. Proof: Let \(e_1, e_2 \in S\) be elements such that property 1 holds, by substitution we have:
\(e_1*e_2 = e_2*e_1 =e_1\) by assumption \(e_2\) follows condition 1, we can obtain this by sobstituting \(s\) with \(e_1\)
\(e_2*e_1 =e_2\) by assumption \(e_1\) follows condition 1, we can obtain this by sobstituting \(s\) with \(e_2\)
From the first two passages it follows that \(e_1 = e_2\) by logic (If it's not clear why, see this) Since we proved the identity is unique, we can name it. Given a monoid \((S, *)\) its identity will be represented as \(1_S\)

Group

Let \((G, *)\) be a monoid, this is a group if and only if:

\(\forall g \in G\) \(\exists g^{-1} \in G\) \(g*g^{-1} = g^{-1}*g = 1_G\)

Porco dio

Pop eye

Porco dio

Questo è un coso

Porco dio

Italian Notes

These are not my notes, it's mainly stuff that was supposed to be in this repo but that I'm migrating in here in order to have an easy access in the web, this is also the same reason the name convention is not the same in this part of the tree.

Italian Notes

Introduzione al corso e nozioni matematiche basilari. Modello di canale con e senza rumore. Modello di sorgente. Codifica della sorgente. Codice univocamente decodificabile. Codice istantaneo. Disuguaglianza di Kraft. Codice di Shannon/Fano. Esempi di codice ottale, esadecimale e ASCII. Codice per la rilevazione dell'errore. Rumore bianco. Bit di parità. Rilevazione burst di errori. Compromessi tra ridondanza e capacità di rilevazione degli errori, Codici a ripetizione. Codici di Hamming. Compressione dei dati. Codice di Huffman. I due teoremi di Shannon. Entropia e le sue proprietà. Informazione mutua. Capacità del canale e le sue proprietà. Limiti nella capacità di trasmissione. BCH. Codici Reed-Solomon. Codici ciclici. Codici crittografici post-quantum.

E' un corso di teoria, basandosi prevalentemente su teorie e dimostrazioni

Dei materiali consigliati alcuni sono prontati per certi argomenti. Il moser è teoricamente il più semplice da comprendere, senza andare troppo in profondità, descrivendo però le basi matematiche. Il cover entra più in profondità anche a livello matematico.

La statistica è utile per capire quali sono gli errori più comuni e correggerli. Esempi: in un cd c'è più errore dove ci possono essere mani unte appoggite sul disco Esempio delle immagini: dove c'è importanza di dati sono errori più importanti da correggere

Esistono errori più e meno importanti

Il programma

Modello di canale con e senza rumore
Modello di sorgente
Codifica della sorgente
Codice univocamente decodificabile
Codice di rilevazione dell'errore
Rumore
Rilevazione di errori
Compromessi tra ridondanza e capacità di rilevazione degli errori
Compressione dei dati
Le teorie di Shannon
Entropia e le sue proprietà
I limiti del canale e della trasmissione

Italian Notes

Database management system è un software in grado di gestire collezione di dati che siano grandi, condivise e persistenti assicurando la loro affidabilitàa e privatezza. Una base di dati è una collezione di dati gestita da un DBMS.

(vedi anche [[DBMS - alternative]])

Su questi dati possiamo mettere vincoli e il DBMS garantisce che i dati siano coerenti con i vincoli.

In termini pratico è una connesione client server. Il database è uno strumento di astrazione. Il DBMS è colui che si occupa di memorizzare a livello fisico secondo una sua determinata logica. E' trasparente al programmatore.

Architettura a tre livelli

Livello Esterno (utente e applicazione) GUI

indipendente logica dei dati

Livello Logico (schema logico)

indipendente da come vengonono memorizzate in memoria fisica

Livello interno (fisico): storage

Mumbo jumbo dello schema funzionale

vedi schifo slide

marginalmente importante sulla amministrazione di un database Si toccherà principalmente il catalogo e il dizionario dei dati. Ovvero un'altra base di dati presente dentro il DBMS per catlogare i dati. Tramite il DDL si compila questo catalogo.

Con un DBMS si fanno le interrogazioni. Queste interrogazioni sono in programmazione dichiarativa è il DBMS che gestisce la richiesta tramite il linguaggio SQL. Si possono implementare in linguaggi esterni in vario modo.

Utenze di un DBMS

RICORDA: Su un dbms ci possono essere più database

DBA = amministratore database (di uno o più) Hanno diversi funzionailità tra cui DDL, DML, DQL , DCL (scaricare dati, modificare dati, fare query sui dati e concedere funzionalità ad altri utenti)

Il Superuser (in postgres si chiama POSTGRES) è il master di tutto, di ogni database e di quelli futuri.

DB user: utenti del database con privilegi specifici e limitati rispetto a un database. Un utente puo ad esempio essere uno script esterno per interrogare i dati

Ci sono diversi livelli di expertise per gli User, devel user, occasional (non-expert), casual user.

Accesso a un dbms

Client server comunication
Accesso sia da postazione locali o da remoto
GLi utenti utilizzano un software client che presentano : riga di comando, GUI e interfaccia web.

Al concetto di record si associano gli attributi Gli attributi appartengono ad un Dominio, ovvero insieme dei valori atomici possibili per un attributo Una tabella è un sottoinsieme del prodotto cartesiano dei domini degli attributi

Questo ci dice che tutto è una fottuta relazione matematica Esempio R c D1 x D2 (la relazione è un sottoinsieme del prodotto cartesiano) D1 = {Milano, Roma} (possibili valori) D2 = {1milione , 2 milioni, 3 milioni}


Roma	3 milioni
Milano	1 milione
un record sarebbe (D1, D2) e un record con i valori identici sono lo stesso record
Un record di una tabella è univocamente identificato dalla combinazione di tutti i suoi attributi.

Metodologie per i modelli

nota: capitolo 6 del libro di testo Paolo Atzeni

Un principio dell'ingegneria su cui ci basiamo per fare le basi di dati è quello di separare il cosa rappresentare in una base di dati dal "come" farlo.

Ci sono 3 fasi della progettazione

Progettazione Concettuale: fase in cui si ottiene schema concettuale in cui andiamo a rappresentare ad alto livello di astrazione, senza preoccuparci dell'implementazione, il modello concettuale dei dati e come essi sono organizzati.
Progettazione Logica: si mantiene un certo livello di astrazione e si trasforma lo schema concettuale in uno schema logico basato su un modello logico dei dati (esempio relazionale). Sempre nel contesto del modello relazione si può verificare tramite [[NORMALIZZAZIONE]] la qualità dello schema logico ottenuto. E' ad un livello inferiore di astrazione poichè i dbms si basano su un modello logico dei dati come appunto quello relazione, ma ne astriamo dalla sua implementazione effettiva.
Progettazione fisica: lo schema logico viene ultimato e implementato, specificandone i parametri fisici di memorizzazione (organizzazione dei file e indici).

Un modello concettuale che usiamo è il modello ER (Entità Relazione).

Modello concettuale ER

Si fanno uso di diagrammi per la rappresentazione. ![[Rappresentazione grafica dei costrutti.png]]

Entità : Rappresentato da un rettangolo e un nome univoco che lo rappresenta. Rispetto al modello relazionale una entità può esistere anche senza saperne i suoi "attributi". Non è la tupla di attributi che fa un'entità ma è l'entità stessa.

![[Esempio di entità.png]]

Associazioni: Rappresentate da un rombo (poi vedremo anche dalle sue cardinalità). Non hanno un "verso" e posso essere n-arie. Più comunemente le associazioni sono binarie, ricorsive, ternarie. Le associazioni nel modello E-R sono a tutti gli effetti un sottoinsieme del prodotto cartesiano tra le entità, la conseguenza è che non possono esserci delle occorrenze di n-uple ripetute. ![[associazione.png]] in una associazione di questo tipo non si può rappresentare un esame sostenuto più volte ( si dovrebbe modellare una entità Esame)

![[associazione ternaria.png]] ![[associazione ricorsiva.png]] Esempio di ricorsiva e ternaria

Attributi: Rappresentano proprietà elementari di un' entità o un'associazione. Possono essere atomici (esempio Età Nome o Cognome) o composti come ad esempio Indirizzo che è composto da via indirizzo cap civico. Si preferisce non usarli. Ogni attributo ha un suo dominio, i valori possibili, ad esempio Età può essere un numero naturale maggiore di 0 e inferiore a 100, non vengono rappresentati nello schema ma possono essere inclusi nella documentazione associata. ![[Attributi.png]]

Esempio di schema ER con questi 3 costrutti

![[Esempio di schema ER.png]]

Altri costrutti del modello ER

Cardinalità di una associazione: La cardinalità è un vincolo sull'associazione che descrive quanti entità possono essere in associazione con l'altra, ne descirve quindi il numero minimo e massimo di occorrenze a cui un'entità può partecipare. Possiamo distinguere delle associazioni uno ad uno (0,1)(1, 1), associazioni uno a molti (1, 1) (0, N) o associazioni molti a molti (1, N) (0, N) ![[cardinalità associazioni.png]] Questo si basa sulle associazioni binarie perchè le associazione multiple solitamente partecipano con cardinalità massima pari a N.

Cardinalità degli attributi: Anche gli attributi possono avere cardinalità. DI norma se non è specificata si intende che la cardinalità sia (1,1) inq uel caso si dice che è un attributo obbligatorio. Nel caso un attributo abbia una cardinalita da (0, n), quindi omettibile, si dice opzionale. Nel caso invece l'attrbuto può assumere più valori si dice multivalore. Si preferisce usarle con cautela i attributi multivalore che possono essere espressi con una associazione tra 2 entità ![[cardinalità attributi.png]]

Identificatori: Sono attributi che identificano univocamente un detemrinata occorrenza di un'entità. Può essere un identificatore atomico composto da un singolo attributo oppure da più attributi. Nel caso gli attributi appartengono all'entità si dicono identificatori interno (o chiave). Posso esserci identificatori esterni modellati da cioè da una relazione tra un'entità e un'altra, si dice anche che in questo caso sia una entità debole avendo bisogno di un identificatore esterno. ![[Identificatori o chiavi di un entità.png]]![[Identificatore esterno.png]] Entità debole e identificatore esterno

Generalizzazioni: Rappresentano legami logici tra entità, detta una genitore e entità figlie. Le generalizzazioni possono essere Totali, nel caso in cui l'occorrenza di entità genitore e almeno occorrenza di un'entità figlia, altrimenti si dice parziale. Si dice anche esclusiva se l'occorenza genitore è al massimo 1 occorenza di un'entità figlia, sovrapposta al contrario ![[Generalizzazioni.png]]

La caratteristica dei genitori vengono trasferite al entità figlia senza bisogno di specificarle. Le entità figlie in più hanno attributi aggiuntivi. Si può sempre rendere una generalizzazione totale esprimendo tutti gli altri casi.

Nel capitolo 7 si mostrano molti esempi e uno schema da seguire per la proggettazione di basi di dati.

Progettazioen Logica

La parte importante della progettazione logica è il ristrutturare lo schema ER ottenuto nella fase di modellazione concettuale. Poi si deve passare dal modello ristrotturato al modello logico.

Ristrotturazione del modello concettuale

Si può riassumere in queste fasi:

Analisi delle ridondanze
Eliminazione delle generalizzazioni
Partizionamento/accorpamento di entità e associazioni
Scelta degli identificatori principali

Analisi delle ridondanze

Le ridondanze in uno schema concettuale corrisponde alla presenza di un dato che può essere derivato da altri dati. Un esempio sono dati darivati da altri tramite operazioni, un derivato da un associazione in cui il dato può essere conteggiato e associazioni derivabili dallaa composizione di altre associazioni in presenza di cicli. ![[Schemi con ridondanze.png]] Esempi di ridondanze. Nella terza si possono contare il numero di persone in associazione per ottenere il numero di abitanti.

Eliminazione delle generalizzazioni

Le generalizzazioni non esistono un loro corrispettivo nello modello relazionale. Queste perciò devono essere rimodellate tramite entità e relazione e ci sono 3 metodi che si possono utilizzare:

Accorpamento delle figlie della generalizzazione nel genitore
Accorpamento del genitore della generalizzazione nelle figlie
Sostituzione della generalizzazione con associazioni ![[Esempio di schema.png]] PRendendo come esempio lo schema 8.10 queste sono le varie ristrotturazioni ![[Esmpi di ristroutturazioni di generalizzazioni.png]] Il caso 1) si può utilizzare e torna comodo quando le oiperazioni eseguite sulle 2 entità non fanno distinzione. Il caso 2) è possibile unicamente se la relazione è totale (quindi ogni elemento del genitore e almeno 1 elemento delle figlie) e torna comodo se ci sono operazioni che si eseguono o su una o sull'altra entità. Il caso 3) conveniente quando la generalizzazione non è totale (non necessario) e ci sono operazioni che si riferiscono solo a certe occorrenze delle entità E1 o E2 facendo distinzione tra le entità figlie e le entità genitore.

Partizionamento/accorpamento di concetti

Partizionare un'entità in più entita, eliminare attributi multivalore, accorpare entità sono tutte le operazioni in questo punto. Di seguito una serie di esempi con commenti ![[Pasted image 20240610174958.png]] Questa è una decomposizione verticale che divide un'entità in due sotto entità con i suoi attributi. In questo caso probabilmente nella nostra applicazione non utilizzeremo nelle operazioni tutti i dati dell'impiegato ma solo una sua sottoinsieme di essi. (notare come andiamo ad introdurre una generalizzazione a livello logico)

![[Pasted image 20240610174950.png]] GLi attributi multivalore come già detto prima non sono presenti nel modello relazionale e quindi vanno rimodellati.

![[Pasted image 20240610175011.png]] Nella nostra applicazione le operazioni che andremo ad eseguire richiederanno spesso accessi all'entità appartamento quindi per ridurne il carico sul sitema le accorpiamo.

Traduzione verso il modello relazionale

![[Pasted image 20240610181015.png]] ![[Pasted image 20240610181024.png]] con rinominazione di PARTECIPAZIONE ![[Pasted image 20240610181037.png]]

![[Pasted image 20240610181045.png]] ![[Pasted image 20240610181052.png]]

![[Pasted image 20240610181106.png]] ![[Pasted image 20240610181113.png]]

![[Pasted image 20240610181134.png]] Entità con identificatore esterno ![[Pasted image 20240610181148.png]]

![[Pasted image 20240610181211.png]] ![[Pasted image 20240626110332.png]] Varie opzioni

Questa fase è meccanica una volta completata la ristrotturazione e i sistemi CASE (Computer-aided software engineering) possono farlo in automatico.

Transazioni-e-controllo-di-affidabilità

[[Controllo degli accessi]] Obiettivi: segretezza, integrità, disponibilità

Tecniche:

Autenticazione: basati principalmente su username e password
Controllo dell'accesso : per ogni accesso ai dati si verifica che l'utente sia autorizzato (basato sul dbms)
Crittografia : cifrare dati

CONTROLLO ACCESSO

Politiche di sicurezza

Reference monitor modulo dbms che si occupa di verificare se una richeista viene (autorizzata) soddisfatta o meno

Politiche per l'amministrazione della sicurezza

Centralizzata: Un singolo utente (il database administrator) che gestisce l'intera base di dati
Decentralizzata: Più soggetti sono responsabili del controllo di porzioni diverse della base di dati.
Ownership: l'utente che crea un oggetto (proprietario) gestisce le autorizzazione sull'oggetto

Politiche per il controllo dell'accesso Need to know (minimo privilegio) : restrittivo permette ad ogni utente l'accesso solo ai dati strettamente necessari per eseguire le proprie attività. Maggiore garanzia Maximized sharing (massimo condivisione) : consente agli utenti il massimo accesso alle informazioni nella base di dati mantenendo comunque informazioni riservate. Non serve proprio tanta protezione.

Comandi per la sicurezza

Grant Revoke : solo privilegi che una persona ha grant

Delega dei privilegi

I cataloghi SYSAUTH e SYSCOLAUTH

Il dizionario di una base di dati è una base di dati essa stessa

Revoca ricorsiva , timestamp di quando viene garantito l'accesso

SQL nasce come linguaggio di interrogazione.

SQL = Structured Query Language DDL = Data definition language [[DML]] = data manipulation language DQL = data query language DCL (?) = Data control language Al presente siamo al SQL 3.0

Introduzione a sql

Di seguito una lista di comandi ricorrenti:

CREATE TABLE imdb.movie () tra le parentesi possiamo mettere tutti i CONSTRAINT e altri attributi
CONSTRAINT : dopo si possono esplorare diversi tipi di vincoli
PRIMARY KEY

All'interno del DBMS possiamo visualizzare tutti questi attributi

DML ovvero Data manipolation language è una parte di SQL che lavorano sui dati, NON sulla struttura dei dati/tabelle

Nel DML rientrano:

INSERT
UPDATE
DELETE

Insert, inserire un record

Ci sono alcune parole del linguaggi sql che sono attributi identificati dal linguaggi, come ad esempio character (che identifica un carattere). Nel caso nella nostra base di dati abbiamo un attributo dal nome character dobbiamo identificarlo tra due apici quindi: "character" . Non solo questo serve ma anche per identificare eventuali altri alias di attributo. Quando si usa il comando insert invece si usa il singolo apice ''

Quando si inserisce una nuova entry il dato non si troverà in fondo ma secondo un criterio di ordinamento, se presente, intrinseco di postgres (ad esempio). NON ESiSTE ORDINAMENTO

Di base insert bisogna specificare tutti i valori da inserire, se volessimo inserire solo alcuni valori invece possiamo usare sempre insert ma specificando, subito dopo la tabella in cui inserire il dato, specificando i valori che vogliamo inserire

Delete, eliminare un record

Esempio: delete from imdb.movie where id = 'asdka123' la where specifica un parametro da valutare in questo caso si verifica uno ad uno l'id. CANCELLA LiNTERA ENTRY

Altro esempio where year > '2010' .... Qui sopra si esprime una espressione e possiamo anche esprimere una espressione complessa con predicati and not or ecc...

Se si esegue delete from imdb.movie; è come dire delete... .... true ovvero elimina l'intera tabella. PERICOLO

Update, aggiornamento o modifica valore

update imdb.movie set year = '1974' where id = 'asdka123'

CTE è una Common Table Expression è una vista materializzata che svanisce dopo l'esecuzione della query.

La sintassi è with 'nome cte' as (query)

Una query ricorsiva include una cte che si auto-referenzia ![[Pasted image 20240613120201.png]]

Capitolo 5.5.1 di Atzeni

[[Sicurezza di un dbms]]

La base di dati sfrutta certe componenti del file system fornito dal sistemi operativo. Esistono delle possibilità in cui in futuro più funzioni del sistema operativo possano essere già orientate alle basi di dato.

La cosa importante da ricordare è il fatto che le tabelle non possono essere caricate tutte in memoria centrale essendo essa limitata ma quindi dovranno risiedere in memoria secondaria in strutture a blocchi(dischi, ssd ecc) ed è quindi importante utilizzare al meglio il buffer che trasporta i blocchi necessari in cui risiedono i dati. Possiamo dire che una volta che i dati sono arrivati in memoria centrale il costo delle operazione è trascurabile rispetto al tempo che impiega la memoria secondaria nel trovare il blocco giusto e copiarlo nel buffer. (Ricorda: le operazioni più costose in termini di interrogazioni sono le select e i join)

In breve il buffer

La struttura del buffer è gestita a pagine, che corrispondono alla dimensione di un numero intero di blocchi. La sua gestione è simile alle politiche di gestione della memoria centrale dei sistemi operativi. Per mantenere il numero di cambi di pagine al minimo si mantiene il principio di località dei dati in cui si assume che i dati recentemente usati saranno probabilmente richiamati in futuro, facendo in modo da avere solamente le pagine maggiormente usate all'interno del buffer.

La gestione dei dati fisici

Quando portiamo un blocco in buffer nella pagina andiamo a prendere sia i dati veri e propri sia dei dati di controllo, che discrovono come arrivare ad ottenere i dati veri. Qui descritto la struttura di una pagina: ![[Pasted image 20240613162800.png]] Il block header e il block trailer, rispettivamente all'inizio e alla fine della pagina contengono informazioni di controllo utilizzate dal file system. Il page header e il Page trailer contengono informazioni sulla struttura fisica, ovvero descrive come è fatta la struttura fisica dell'oggetto o strutture dati associate per accedere ai dati. Il bit di parità che indica se la pagina è correntemente valida o meno.

Blocking factor

Un fatttore importante da ricordare è il blocking factor (bfr) ![[Pasted image 20240613163219.png]] dal bfr possiamo ricavarci il numero di blocchi necessari per un file invertendo la formula

Strutture primarie per l'organizzazione dei file

Esistono varie varianti per l'organizzazione dei file:

sequenziale
calcolato
ad albero

Le strutture sequenziali a loro volta si suddividino in dati ordinati, non ordinati e array.

La Struttura non ordinata

anche detta seriale o disordinata sono le più semplici poichè i record vengono inseriti nel file nell'ordine in cui questi si presentano. Vengono detti heap*, o mucchi, implicando che i record arrivano senza essere toccati o sistemati secondo un ordine. L'inserimento di nuovi record è molto efficente poichè necessità solamente di un puntatore all'ultimo elemento inserito. Il suo svantaggio deriva dalla ricerca, che richiede di scandire alla peggio ogni elemento, il costo della ricerca è lineare al numero di blocchi del file in questo senso. Da sole questo strutture possono essere usate ma spesso sono supportate da strutture secondarie per favorire gli accessi.

Per la modifica e l'eliminazione dei dati basta trovare il dato e marcarlo o modificarlo direttamente, senza riorganizzare la struttura stessa.

Struttura sequenziale ad array

Possibile solamente se le tuple di una tabella sono di dimensione fissa. Se soddisfatta questa condizione si associa un numero n di blocchi contigui e ciascun blocco è dotato di un numero m di "posizioni" disponibile per le tuple, creando un array n x m in cui ciascuna tupla è associata un indice i all'interno di esso. Gli inserimenti e le ricerche sono efficienti avendo a disposizione l'indice della tupla che si sta cercando. (Un costo costante)

Struttura sequenziale ordinata

Detta anche clustered, prevede la memorizzazione dei record secondo un ordinamento fisico coerente con l'ordinamento di un campo detto chiave (in alcuni testi detto pseudochiave), che può essere composto da più attributti. Nel caso di parità di ordinamento sul primo si procede al secondo e così via. Seppur queste siano strutture ordinate è difficile fare una ricerca dicotomica perchè non sempre si hanno accesso a tutte le informazioni del file (per intenderci non abbiamo tutti i blocchi caricati), quindi queste strutture sono utilizzate in stretta associazione con indici. Le selezioni su intervalli sono semplici avendo gli intervalli memorizzati contiguamente, basta trovare il primo membro e poi si hanno di conseguenza gli altri consecutivamente. In modo analogo se si fanno operazioni aggregate e l'ordinamento e sui campi di aggregazione queste sono più semplici. Le eliminazioni potrebbero portare a spreco di spazio mentre gli inserimenti potrebbero causare la necessità di avere un file di "overflow" in cui non solo si perde la contiguità dell'ordinamento ma richiede spazio aggiuntivo. Per ovviare a questi problemi si fanno delle periodiche riorganizzazioni.

Strutture con accesso calcolato (funzioni di hash)

Basandosi sul valore di una pseudochiave si esegue una funzione hash che calcola una chiave, garantendo un accesso associativo ai dati. Un esempio pratico di quando viene utilizzato questo tipo di accesso rispetto ad un array: considerare le matricole degli studenti composte da 6 cifre (TANTI casi possibili), se volessimo memorizzare solo un sottogruppo, una classe ad esempio di 40 persone, sarebbe molto inefficente assegnare un array grande quanto tutti i casi possibili. Si decide quindi di usare meno spazio, ad esempio assegnamo 50 spazi per la memorizzazione e calcoliamo gli indici per su questi 50. Una dei problemi della funzione hash è la possibilità di collisioni di indice che diminuiscono al crescere dello spazio che allochiamo rispetto al numero che ci aspettiamo di riempire (si dice fattore di riempimento nel caso precedente 40/50 = 0.8). Per gestire le eventuali collisioni, che comunque possono accadere, possiamo allocare un blocco aggiuntivo collegato al precendente e il record che causa questa operazione viene messo all'interno. Questa operazione è ricorsiva, si vanno quindi a creare catene di overflow. ![[Pasted image 20240614094547.png]] Accesso puntuale, quello relativo ad uno specifico valore della chiave, lo possiamo considerare con costo quasi unitario , costante, in questo campo è molto vantaggiosa la funzione hash, al contrario degli accessi su intervalli che non è dato che valori simili siano adiacenti nel blocco, anzi molto spesso sono su blocchi differenti. Una limitazione della struttura hash è la sua scarsa dinamicità, su file che crescono si perde l'efficenza e bisognerà riorganizzare il file allocando un maggior numero di blocchi e o una diversa funzione hash.

piccola nota per quanto riguarda il testo che specifica che esistono strutture hash capaci di evolversi dinamicamente ma di cui non è trattato nulla.

Struttura ad albero o indici

Le strutture ad albero anche dette indici, sono strutture che permettono l'accesso in base a un valore di uno o più campi , come per le funzioni hash, mantenendo l'efficenze negli accessi puntuali ma anche a intervalli di valori.

Distinguiamo gli indici in strutture primarie che contengono i dati (record) e strutture secondarie che favoriscono gli accesso ai dati senza però avere i dati stessi. ( strutture di supporto/ausiliarie) Gli indici sono formati da una coppia di campi K, la pseudochiave su cui viene fatto l'ordinamento, ed il valore p che è il puntatore ad un'area di memoria.

Indici primari

Negli indici primari il valore p punta o all'inizio del blocco o ad un valore massimo o minimo nel blocco. Sono caratterizzati spesso dall'essere sparsi ovvero non compaiono tutti i valori della pseudochiave ma solo alcuni. Se abbiamo n blocchi il nostri indice primario sarà composto da n elementi, uno per ciascun blocco. ![[Pasted image 20240614101302.png]] ![[Pasted image 20240614101438.png]] Due esempi di indici primari Può esistere un unico indice primario (pensare ad un indice di un libro)

Indici secondari

E' una struttura dati di supporto all'indice primario. Qui le chiavi possono essere non ordinate , ordinate (non rispetto al campo di indicizzazione secondaria) o calcolate tramite hash. Gli indici secondari devono per forza essere densi, ovvero contenere ogni valore del campo che stiamo considerando Il campo k che stiamo considerando può essere anche su campi non chiave, a quel punto possiamo procedere con tre opzioni per memorizzare:

inserire più volte il medesimo valore k
Record a lunghezza variabile con più puntatori
Un ulteriore livello che contiene

![[Pasted image 20240614102612.png]] Esempio con ulteriore livello

Un file può avere più indici secondari (pensare ad esempio a indici analitici o a diversi indici in guide turistiche, una per i ristoranti una per gli hotel ecc...)

Veloci considerazione sugli indici in confronto alle hash

C'è da notare che le funzione hash sono quasi impareggiabili per l'efficenza negli accessi puntuali. Gli indici essendo implementati tramite alberi avranno, ed essendo essi ordinati anche, avranno un tempo di ricerca logaritmico (pensare alla ricerca dicotomica) in base al numero di blocchi, seppur questi permettono dei vantaggi per quanto riguarda accessi su intervalli.

Nota del libro: viene fatto notare come questa differenza è man mano minore dato la maggior capacità della memoria centrale che permette buffer di grandezza maggiore e quindi riducendo la disparità tra accesso via indici e hash.

Altre considerazioni sono il fatto che gli indici sono di gran lunga più piccoli rispetto al file stesso

Le Strutture ad albero, i b-tree e i b-tree+ (balanced tree)

Le strutture ad albero sono caratterizzate dall'essere bilanciati, per mantenere la profondità al minimo e quindi un accesso medio ai dati minore.

Ogni nodo dell'albero deve contenere sia dei puntatori p sia dei valori Ki ![[Pasted image 20240614104315.png]]

Gli alberi di ricerca contengono al massimo p-1 puntatori ( se p = 3 allora ogni nodo potrà avere al massimo 3-1=2 puntatori) All'interno del nodo i valori Ki sono ordinati in modo per cui K1< K2< K3 ecc..

![[Pasted image 20240614104522.png]] Albero con p=3

![[Pasted image 20240614104837.png]] Esempio di albero con puntatori e file dati a cui puntano Ogni elemento nel nodo è caratterizzato dai Puntatori dai valori K della chiave contenente il riferimento al blocco a cui si trova il dato

	hP1,(hK1, Pr1i), P2,(hK2, P r2i), . . . ,(hKq−1, P rq−1i), Pqi,

Il problema sorge quando dobbiamo andare ad inserire nuovi valori all'interno dell'albero che per mantenere il bilanciamento dovrà effettuare eventuali operazioni di divisione sul nodo che si estende ricorsivamente ai livelli superiori.

Gli alberi B-tree+ si differenziano dai b-tree normali perchè nei livelli intermedi contengono alcuni valori di k mentre i puntatori ai dati si trovano solamente nei nodi foglia dell'ultimo livello. Inoltre nei nodi foglia si hanno dei puntatori che puntano direttamente alla foglia successiva Apparentemente i B+ possono apparire più svantagiosi visto che non ci sono puntatori diretti ai dati nei nodi intermedi. Questo è controbilanciato dal fatto che nei nodi intermedi sono memorizzati più puntatori che comportano un vantaggio in termini di accesso al disco necessari per attraversare l'albero. Combina i vantaggi di un indice multivello (creare più indici primaria più livelli) con i vantaggi dell'accesso sequenziale indicizzato ![[Pasted image 20240614110126.png]] esempio di B+

	nota: tutta questa parte sui b-tree non è nelle slide di montanelli ed è preso dal libro

Conclusione sulla progetta fisica

La progettazione fisica è l'ultima parte di progettazione e si occupa del decidere come ogni singola relazione viene memorizzata. Per fare ciò si ragione sulla struttura dello schema logico e i tipi di relazione e tipi di dati che abbiamo, ragioanando anche in ottica di quali possibili operazioni possano essere eseguite e il loro carico sul sistema.

Queste sono anche scelte basate sul sistema e quello che ci viene fornito dal DBMS a nostra scelta. Nello standard SQL non si è ancora rggiunto un accordo su quali comandi fornire o uno standard per la progettazione fisica essendo essa difficilmente uniformabile. A livello commerciale ci vengono forniti questi insieme di comandi ![[Pasted image 20240614110942.png]] ![[Pasted image 20240614110954.png]] La "ListaAttributi" e quella su cui si eseguono gli ordinamenti, facendo prima l'ordinamento sul primo della lista, in caso di parità sul secondo e così via.

maggior parte degli appunti sono basati sul libro di testo "Basi di dati"[[_Paolo_Atzeni,_Stefano_Ceri,_Piero_Fraternali,_Stefano_Paraboschi.pdf]]

Integrati opportunamente con quello trovato dalle slide del prof. Montanelli e i suoi lucidi oltre che appunti delle lezioni. Alcune informazioni sono prese dalle slide del prof. Ferrara

nota: capitolo 3 del libro

Sono tutte quelle operazioni definite su relazioni che ritornano a loro volta delle relazioni.

Operatori di unione intersezione e differenza

Sono i classici operatori dell'insiemistica.

Unione su due relazioni r1 e r2 la loro unione è tutti quei oggetti appartenenti a r1 oppure r2, o appartenenti a entrambi.

intersezione su due relazioni r1 e r2 è una relazione r3 i cui componenti sono appartenenti sia a r1 sia a r2.

Differenza una differenza tra r1 - r2 conterrà le tuple che appartengono a r1 e non appartenenti a r2

Operatori di ridenominazione

Ci aiuta, come dice il nome, a rinominare il nome degli attributi di una relazione per poi comporre delle unioni. ![[Pasted image 20240611105542.png]]

![[Pasted image 20240611105714.png]]Esempio di ridenominazione poi seguita da un unione.

Operatore di selezione

Indicato dall'operatore sigma, è un operatore che prende una relazione e ne selezione un sottoinsiemi di tuple (facendo una sorta di taglio orrizontale). La selezione può essere espressa da una formula sugli attributi tramite gli operatori logici and, not, or e da un insieme di operazioni X definite sulle ugualianze e le disuguaglianze (maggiore, minore, uguale) che torni un valore di verità. ![[Pasted image 20240611110318.png]] Selezione di tutti gli impiegati che hanno età maggiore di 30 e stipendio superiore a 4000 dalla relazione impiegati

Operatore di proiezione

La proiezione segnato con il simbolo di Pi-greco definisce una operazione su una relazione in cui si vanno a selezionare un sottoinsieme di attributi della relazione, attuando una sorta di taglio verticale. L'operazione produce al più tante tuple quante ne contiene la relazione originale (caso in cui il sottoinsieme che stiamo proiettando è superchiave). ![[Pasted image 20240611110937.png]]

Considerazione tra proiezione e selezione

![[Pasted image 20240611111021.png]] Come si può vedere la proiezione effettua una decomposizione verticale sugli attributi, mentre la selezione restituisce un sottoinsieme della relazione di partenza.

Join, join naturale e theta-join

Il join ci permette di correlare dati in relazioni diverse tra di loro. Ne esistono due varianti il join naturale e il theta-join

Theta-join, ergo join con condizione. Equi join è un join in cui la condizione è una ugualianza tra due valori. Il join naturale può essere ricondotto ad un theta join in cui essenzialmente si verificano che alcuni valori siano uguali.

Il join naturale lavora su i VALORI simili tra due relazione e li mette in correlazione. Si può usare un outer join per includere anche le n-uple non correllate con i valori null che completano. I right e i left join vanno ad indicare quale delle due relazioni vogliamo considerare e un full considera entrambe. ![[Pasted image 20240613122137.png]]

Divisione

Divisione La divisione di applica solo a relazioni r(Z), s(X) in cui X ⊆ Z. Dato l’insieme di attributi Y = Z − X, la divisione r ÷ s e una relazione T(Y ) contenente tutte le tuple t tali che: - vi siano tuple tr in r con tr[Y ] = t, e - tr[X] = ts per ogni tupla ts di s. Intuitivamente, la divisione verifica una condizione o una corrispondenza fra una o piu tuple di r e tutte le tuple di s.

![[Pasted image 20240613122332.png]] x "soddisfa sia a che b"

Prima lezione

Basi di dati relazionale, lo scopo è capire come memorizzare una serie di dati. Diversi sistemi sia open source e non. (oracle)

Esistono anche basi di dati non relazionali. Nata da grandi volumi di dati che non hanno troppi vantaggi dal relazionarli. Sistemi a grafi, documentali (not sql)

Esistono diverse teorie di basi di dati.

Algebra relazionale: linguaggio usato sulla "carta" per domandarsi sui dati.

E' importante saper progettare la base di dati e i loro [[Record]]

Perchè usare le basi di dati

Bisogna dare un contesto interpretativo ai dati. Le basi di dati sono sempre relative ad un problema da affrontare. Esempio di memorizzare le vie: ad un servizio postale potrebbe tornare utile ricordare vari dati, dal civico al nome della via al cap ecc... mentre ad un uso più piccolo ad esempio basta solamente ricordarsi in una "colonna" la via e basta.

Da dove vengono i dati

Come si costruisce un db? I dati spesso arrivano da documenti. Dati non strutturati : di solito testo (ma anche audio e immagini). I dati possono anche essere rappresentati in maniera strutturata ma non esplicita. (Esempio una ricetta). Un utente umano riuscirebbe ad infeerire un significato ai dati ma non un computer. I dati non sono orientati ad organizzarli. Serviranno dei strumenti di parsing/manipolazione per usare questi dati in un db.

Formato json : semi strutturato. C'è una descrizione del dato che aiuta ad interpretare il dato, ma non ci sono dei vincoli precisi.

Spreadsheet: Ogni riga esprime un record ogni colonna una caratteristica. Questa è un modo coerente per le basi di dati. Questi sono dati apparentemente strutturati.

L'operazione di join: mettere in relazione tabelle diverse che hanno delle corrispondenze

Per memorizzare i dati si usa un software il [[DBMS]]

	Capitolo 4 del libro di Atzeni

Domini Elementari

Character permette di rappresentare stringhe o singoli caratteri ![[Pasted image 20240612163559.png]]

Tipi numerici esatti ![[Pasted image 20240612163908.png]] scala per numeric è opzionale al contrario che per decimal La precisione indica da quante cifre è composto il numero

Per i numeri reali usiamo invece questi ![[Pasted image 20240612164009.png]]

Lo standard SQL fornisce anche dei tipi per la rappresentazione di dati temporali, sia di intervalli sia di istanti. ![[Pasted image 20240612164117.png]] ![[Pasted image 20240612164127.png]]

Altri tipi introdotti in SQL 3 sono:

Booleani (true o false)
Bigint
BLOB e CLOB che sono utile per dei file binary molto estesi o stringhe molto estese (tipo un capitolo di un libro). Rispettivamente Binary Large Object e Character large object. Il sistema lo memorizza solo senza poterci eseguire query.

Create tables e create schema

Lo schema è una collezzione di oggetti, tra cui tabelle, domini e viste.

![[Pasted image 20240612164837.png]]

Per creare una tabella invece usiamo questa funzione in cui andiamo poi a specificare quale sia l'attributo della primary key, i vincoli sugli attributi ecc ![[Pasted image 20240612164950.png]]

Più in generale questa è la sua sintassi ![[Pasted image 20240612165003.png]]

Domini

Possiamo specificare noi un dominio tramite una funzione SQL ![[Pasted image 20240612165213.png]]

questo ci permette di ripetere senza definire ogni volta i vincoli un dominio su attributi simili.

Vediamo anche come il valore di default lo possiamo definire noi ![[Pasted image 20240612165358.png]] ![[Pasted image 20240612165412.png]]

Vincoli intrarelazionali

Not Null

Il valore nulla è un particolare valore assegnato quando mancano informazioni, e supera determinati vincoli di attributo. Quando un valore ha come vincolo not null vogliamo intendere che il valore non potrà assumere il valore nullo

Unique

Si applica un vincolo di unique su un attributo o su più attributi per intenderli come (super)chiave. Il valore null non viola questo vincolo e può comparire su più righe. Esempio: ![[Pasted image 20240612165801.png]]

Primary key

Va ad indicare un attributo o più attributi come chiave primaria ed implica un vincolo di not null. Può essere espressa come nella sintassi di prima con primary key (Attr1, Attr2)

Vincoli Interrelazionali

IL più comune dei vincoli interrelazionali è il vincolo di foreign key o chiave esterna, ovvero un attributo che referenzia dei valori di un'altra tabella. I valori referenziati devono essere parte della chiave primaria. ![[Pasted image 20240613093230.png]]

Dobbiamo definire cosa avviene quando il valore referenziato dalla tabella cambia ![[Pasted image 20240613094026.png]] queste si applicano sia che il valore venga eliminato o modificato ![[Pasted image 20240613094140.png]]

Interrogazioni base in sql

Una interrogazione in sql è solitamente formata da queste tra clausale:

select
from
where ![[Pasted image 20240613094720.png]] as indica che stiamo rinominando lo stipendio e lo mostriamo come Salario

Clausola select

Select specifica gli elementi/attributi dello schema che mostriamo nel risultato. select 'asterisco' indica che selezione tutti gli attributi della tabella nella clausola from

Nella select possono comparire delle espressioni generiche sul valore degli attributi. ![[Pasted image 20240613095036.png]]

Clausola from

Per interrogazione che richiedono dati da più tabelle le andiamo a specificare nella from . ![[Pasted image 20240613095622.png]] Nella select andiamo a specificare prima del nome dell'attributo da quale tabella viene estratto il dato.

Clausola where

Ammette come argomento uno espressione composta dagli operatori and, not, or e dalle uguaglianze e disuguaglianze. ![[Pasted image 20240613100003.png]] Oltre a questi predicati di confronto relazionali, SQL fornisce il predicato like per il confronto di stringhe. Nel predicato like compaiono i caratteri speciali "underscore" e "%" che rispettivamente rappresentano un qualsiasi carattere e una stringa qualsiasi ![[Pasted image 20240613100442.png]] indica una qualsiasi stringa che inizia con "ab" seguito da una qualsiasi stringa (anche nulla) e prima dell'ultimo carattere (segnato dal trattino) è preceduto da ba

Altri concetti di sql

Distinct

Al contrario dell'algebra relazione in cui elementi duplici non possono comparire, in sql questo non è automatico. Se vogliamo mostrare valori non duplicati di una tabella mettiamo nella select prima dell'attributto il distinct ![[Pasted image 20240613100949.png]] ![[Pasted image 20240613100959.png]] ![[Pasted image 20240613101010.png]] a sinistra cosa accade senza il distinct e a destra con distinct.

Join interni e esterni

Al posto di specificare il join nella clausala di where si può usare direttamente una sintassi che la esplicita nella from

![[Pasted image 20240613101310.png]] I tipi di join sono i seguenti:

right/left (outer) join
inner join (sarebbe il theta join nell'algebra relazionale)
full (outer)

Ordinamento

![[Pasted image 20240613101900.png]]

Operatori aggregati

Gli operatori aggregati non possono essere utilizzati sullo stesso attributo e sono:

count conta tutte il numero di istanze
max e min restituiscono il massimo o il minimo di un attributo che compare
sum somma tutti i valori
avg fa la media (difatto divide il sum per il count)

Raggrupamento e having

Se vogliamo raggruppare secondo un attributo abbiamo la operazione di group by. Se poi volessimo operare per estrarre un certo tipo di dato sul raggruppamento dobbiamo usare la clausala having ![[Pasted image 20240613102700.png]] ![[Pasted image 20240613102713.png]] ![[Pasted image 20240613102800.png]] ![[Pasted image 20240613102847.png]] risultato intermedio del group by

Se volessimo selezionare solo la somma degli stipendi maggiore di 100 (quindi Amministrazione e direzione da sopra) avremmo bisogno di operare sul risultato finale tramite la clausola having ![[Pasted image 20240613103040.png]] ![[Pasted image 20240613103047.png]]

Se al posto di selezionare la somma degli stipendi per dipartimento avessimo voluto fare la somma degli stipendi maggiore di 41 e raggrupparli per dipartimento avremmo semplicemente messo la clausola where Stipendio>41

Riassunto di una query sql base

![[Pasted image 20240613104358.png]]

Interrogazioni di tipo insiemistico in SQL

Sono gli operatori di union, execpt, intersect che sono analoghi pari pari agli operatori insiemistici in algebra relazionale mantenendo anche la proprietà di eliminazione dei duplicati per essere più affine al loro significato insiemistico. ![[Pasted image 20240613104814.png]] ![[Pasted image 20240613104829.png]] aggiungendo all manteniamo anche i duplicati.

Interrogazioni nidificate

Per query nidificate intendiamo query che per ottenere un risultato richiedono il confronto con un'altra query. Per fare ciò estendiamo l'uso degli operatori all e any nella clausola where che andranno rispettivamente a significare che la query restituisce un risultato se la riga soddisfa la condizione per tutti gli elementi della query nidificata, mentre any indica che per almeno un elemento della query nidificata è soddisfatta la condizione. ![[Pasted image 20240613105803.png]] ![[Pasted image 20240613105836.png]] Stessa risultato prima usando un aggregato e dopo esprimendolo con una singola query

Query nidificate complesse

Se andiamo a introdurre delle variabili nelle nostre query queste hanno una certa visibilità. ![[Pasted image 20240613110747.png]] D1.città non è visibile nella seconda query nidificata perchè definita in quella prima. Query: estrarre le persone che hanno degli omonimi ![[Pasted image 20240613110843.png]] Esempio sia di visibilità sia di uso dell'operatore exists. P è visibile alla query nidificata perchè di un livello "superiore". Viene anche detto passaggio di binding, quando la query nidificata fa riferimento al contesto di una sua query esterna.

Exists è un operatore logico che accetta un'interrogazione nidificata e restituisce il valore vero solo se l'interrogazione fornisce un risultato non vuoto. Ha significato solo quando esiste un passaggio di binding.

La query precedente poteva essere eseguita anche tramite un join tra due istanze della stessa tabella. ![[Pasted image 20240613111339.png]] Esempio della query senza la query nidificata

Fare la query in cui si ricercano le persone che non hanno omonimi ci fa usare l'operatore not exists ![[Pasted image 20240613111534.png]]

Modificati dei dati

Sono ovvi... ![[Pasted image 20240613111707.png]] ![[Pasted image 20240613111717.png]]

![[Pasted image 20240613111756.png]] Cancella TUTTE le entry in Dipartimanto ![[Pasted image 20240613111812.png]] Ha lo stesso effetto della precendente ma cambia anche lo schema della base di dati eliminando tutto ciò che referenzia Dipartimanto

![[Pasted image 20240613111937.png]] Esempi di update ![[Pasted image 20240613111956.png]]

nota: capitolo 8 del libro di testo

Non ci ho capito un cazzo per il momento

Il Database management system è un insieme di programmi che permettono agli utenti di creare e mantenere una base di dati. Facilita il processo di definire, costruire manipolare e condividere basi di dati.

Italian Notes

Slide pubblicato passo passo dal professore Slide anno precendente da visionare prima delle lezioni

Libro da consultare per approfondimento [[Artificial.Intelligence.A.Modern.Approach.4th.Edition.Peter.Norvig. Stuart.Russell.Pearson.9780134610993.EBooksWorld.ir.pdf]]

Testi di esame

Programma

Il programma si articola come segue:

introduzione all'Intelligenza Artificiale, applicazioni e ambiti e comunità di ricerca;
agenti autonomi e razionali;
risoluzione automatica di problemi: formalizzazione del problema della ricerca su grafo, ricerca non informata, ricerca euristica;
presenza di avversari: giochi e strategie ottime, ricerca su albero di gioco;
Constraint Satisfaction Problems: definizione e risoluzione con algortimi di ricerca;
incertezza e decisioni sequenziali: Markov Decision Processes;
Reinforcement Learning;
introduzione ai paradigmi del Machine Learning e agli approcci risolutivi di base: alberi di decisione, regressione e classificazione, metodi non parametrici;
reti neurali: shallow e deep learning.

Il corso è un'introduzione alla Intelligenza Artificiale. Cosa non è AI (il corso)

Deep Learning
LLM

Il corso tratterà in generale AI per dare una base dei vari ambiti in cui questa si dirama. Al fine del corso si terrà un seminario con un esperto dell'argomento.

Cosa è una intelligenza artificiale?

Un esempio è il LLM di chatgpt. Alcuni "esperti" / esponenti del settore dicono che i LLM siano il "know it all" e la soluzione a tutta l'intelligenza artificiale. Questo perchè non hanno un modello di mondo, visto che il loro modello è basato su una mole di dati, tanti dati, ma non un modello esatto.

Le AI sono alla base di:

Robotica
Computer vision

Italian Notes

Libro di testo consigliato dal prof Fred Halsall, “Computer Networking and the Internet” ─ 5th edition, Addison-Wesley, 2005

[[computer-networking-and-the-internet-halsall-fred.pdf]]

Videolezioni del prof Gian paolo Rossi

HALSALL: CHAPTER 1 – Data communications and networking basics
1.1 Overview
1.2 Application and networking terminology
1.3 Digital communications basics Leggere - escluso "Satellites", "Terrestrial microwaves", "Radio" in 1.3.1 e Digitall Phase Lock Loop in 1.3.2 1.4 Protocol basics esclusi 1.4.7 1.5 Protocol stacks

HALSALL: CHAPTER 2 – Telephone networks and modems
2.6 Internet Service Providers

HALSALL: CHAPTER 3 – Local area networks and intranets
3.1 Introduction
3.2 Ethernet / IEEE 802.3
3.3 LAN interconnection technologies
3.4 High-speed LANs
3.5 Virtual LANs
3.6 LAN protocols

HALSALL: CHAPTER 6 – Internet Protocol
6.1 Introduction
6.2 IP datagrams
6.3 Fragmentation and reassembly
6.4 IP addresses
6.5 Routing algorithms al § 6.5.6 solo Spanning Tree Bcast 6.6 Routing in Internet esclusi 6.6.6, 6.6.7, 6.6.8, 6.6.10 multicast e mobile IP 6.7 QOS e MPLS escluso RSVP 6.8 IPv6
6.9 IPv6 / IPv4 interoperability

HALSALL: CHAPTER 7 – Transport protocols
7.1 Introduction
7.2 TCP/IP protocol suite
7.3 TCP escluso 7.3.4 specification 7.4 UDP

HALSALL: CHAPTER 8 – Internet applications
8.1 Introduction
8.2 Domain name system
8.3 Electronic mail
8.4 FTP (argomento non trattato nell'anno 2019-2020)
8.6 Internet telephony (argomento non trattato nell'anno 2019-2020)

HALSALL: CHAPTER 9 – The World Wide Web
9.1 Introduction
9.2.1 Overview
9.3 URLs and HTTP1/HTTP2

Fonte: capitolo 1 del libro

Prima di accedere all'internet, qualsiasi dispotivo utilizza un tipo di accesso e ne esistono di diversi. La LAN può andare dal semplice network universitario a un raggrupamento di diverse LAN (ad esempio di una azienda). Tramite dei cavi, di rame o fibbre ottiche o altri supporti si connettono comunemente ad un ISP (internet service provider) che li collega poi al Global Internet. Un'alternativa possono essere i cavi telefonici, una rete aziendale composta da diverse LAN oppure da connessioni wireless.

Grazie agli avanzamenti tecnologici nel campo della trasmissione dati, in particolare nella compressione di essi, tutti questi mezzi ora supportano diversi tipi di media (prima ad esempio i cavi telefonici potevano solo mandare caratteri alfanumerici).

Una fattore da tenere in considerazione quando si parla di trasferimento di dati attraverso un network, sopratutto di dati sensibili è la questione della sicurezza.

Applicazioni e terminologia del networking

Esattamente capitolo 1.2 del libro di testo

Tipi di dato e le loro caratteristiche

Esistono 3 tipi di Text :

testo non formattato (unformatted text)
testo formattato o richtext, un pdf un word con contenente anche eventuali immagini
ipertesto (hypertext) pagine web definite da link tra di loro, contenenti al loro interno testo formattato Ognuno, seguendo il corso di Sistemi Operativi, in locale ha un modo diverso di essere trasferito e memorizzato.

Le immagini si differenziano dalla loro provenienze, se sono immagini digitalizzate da supporti fisici oppure se prodotte al computer. Diventa irrilevante la loro provenienza poichè a livello di dato, queste vengono memorizzate in una matrice bidimensionale composta da pixel.

Ricordarsi che ad esempio un singolo pixel può essere espresso attraverso diversi canali, dagli 8 bit ai 24 e in su. Vedere il corso di Computer Graphics per approfondimenti.

La questione delle immagini prosegue per quanto riguarda i video. I video, oggi, sono principalmente una serie di immagini digitali in sequenza ognuno chiamato frame. Mandare questi frame manda anche il video essenzialmente. Per le televisioni, che funzionavano su supporto analogico, era importante prima digitalizzare su diversi formati (per diversi tipi di schermo) e poi riprodurre i frame digitalizzati in sequenza. Questo viene detto raw bit rate di riproduzione e per un televisore digitale è di 162 mbs.

L'audio è un caso particolare. L'audio è generato in foram analogica, da un microfono che registra l'ampiezza dell'onda di un suono nel tempo. Bisogna perciò digitalizzarlo attraverso un convertitore analogico a digitale (ADC analog-to-digital converter) e poi per riprodurlo bisogna ritrasformarlo attraverso la controparte, ovvero un convertitore da digitale a a analogico (DAC). La qualità del tutto dipende dalla frequenza di "sampling" dell'onda.

Per fare una comparazione della quantità di dati il libro riporta l'esempio delle linee telefoniche, che produce (ai tempi) 64 kbps di bit rate, che messo in confronto al bit rate di un cd fisico di altà qualità produce più di 100 volte questa quantità, ovvero 705.6 kbps. Questo aumento quasi al doppio, a 1.4 mbps, per gli stereo. Qui arriva l'importanza di un algoritmo di compressione efficace.

Metodi di trasmissione

Due metodi intuitivi. O uno stream continuo di dati, uno streaming, oppure un trasferimento di dati in blocco. Nello streaming si considera il bitrate della sorgente e il bitrate del ricevente, a loro volta si può avere un bitrate costante o un bitrate variabile (VBR e CBR). Un esempio è quello di un video che può essere prodotto a bitrate costante ma ricevuto, dopo la compressione, a bit rate variabile.

La modalità a blocchi invece permetti di ricevere le informazioni prodotte ad un tempo non ben determinato. Mentre nello streaming è in "diretta", qui si possono ricevere ad esempio e-mail non a distanza di poco tempo. Un altro metodo del ricezione a blocchi è il downloading che è un ibrido, permette di trasmettere blocchi di dati e scaricarli a bit rate variabili, dove però il tempo di risposta da quando si richiede un pacchetto a quando si riceva debba essere non più di qualche secondo. Viene chiamato round trip delay (RTD)

![[Pasted image 20240926162244.png]]

7h3 n0t4t10n 15 54v3d