ALBERI BINARI
Definizione di albero binario:
• un albero vuoto, oppure
• è composto da un dato più due alberi Visite
Tre tipi di visite "standard" di un albero binario:
preordine: si visita la radice e poi i sottoalberi postordine: prima i sottoalberi e poi la radice
simmetrica: prima il sottoalbero sinistro, poi la radice e poi il sottoalbero destro -Teoria degli alberi binari
-ESERCITAZIONE JAVA
Riferimenti: http://www.dis.uniroma1.it/~liberato/laboratorio/alberi/alberi.html
TEORIA DEI CODICI
In telecomunicazioni la teoria dei codici è un ramo della teoria dell'informazione, o più in generale della matematica e dell'informatica, che studia i codici per la trasmissione di dati.
Esistono due classi di codici
1. Codifica di sorgente (Compressione dei dati) 2. Codifica di canale (Correzione degli errori)
La codifica di sorgente ha lo scopo di ridurre la lunghezza di un flusso di dati, senza per questo dover necessariamente comportare una perdita di informazione: ad esempio gli algoritmi lossless come lo zip permettono di ricostruire integralmente il flusso di dati originario a partire da un flusso di dati compresso. In breve una delle principali idee che sta dietro a questi algoritmi, in particolare alla codifica di Huffman, consiste nel codificare un alfabeto di simboli con un altro alfabeto di stringhe di bit dove i simboli più probabili sono codificati con meno bit: in tal modo non si ha una perdita di informazione ma si ha una riduzione della lunghezza media del singolo simbolo perché la media pesata delle lunghezze dei simboli sarà minore in quanto i simboli più frequenti sono anche i simboli più corti.
La codifica di canale ha lo scopo di rendere il flusso di dati più robusto agli errori di trasmissione che possono essere dovuti a un canale rumoroso. L'introduzione di ridondanze per aumentare la robustezza va esattamente in direzione opposta alla codifica di sorgente, perché tende ad aumentare la lunghezza del flusso di dati.
Questo non significa che le due codifiche si escludono l'una con l'altra, anzi, spesso vengono usate entrambe: prima con la codifica di sorgente si riduce la lunghezza del flusso di dati in modo da avere un flusso uniforme di bit equiprobabili con determinate proprietà stocastiche, poi con la codifica di canale lo si rende più robusto aumentandone nuovamente la lunghezza. La lunghezza del flusso risultante dopo questi due tipi di codifica potrebbe anche essere poco inferiore al flusso originale ma la robustezza complessiva sarà in generale maggiore.
