[IV] - Fondamenti di Informatica 2

Download PDF appunti

• [PDF] parte A
• [PDF] parte B
• [PDF] parte C
• [PDF] parte D

Algoritmi

• Approccio algoritmico. Metodo risolutivo, semialgoritmo, algoritmo. Proprietà. Tipologia dei problemi. Strategia vincente dei giochi finiti.

Macchina di Turing

• Funzionamento e struttura, matrice funzionale, applicabilità. Composizione di matrici. Ipotesi fondamentale degli algoritmi. Algoritmo di imitazione. Problema della codifica. Insieme semidecidibile e decidibile. Indecidibilità della terminazione.
• Struttura e funzionamento della macchina di Von Neumann.

Grafi e alberi

• Grafo e grafo diretto. Cammino e sua lunghezza, ciclo. Grafo connesso, fortemente e debolmente. Albero e albero diretto. Implementazioni (plessi, liste multiple, matrici di adiacenza, liste di adiacenza). Attraversamenti (breadth-first e depth-first). Grafo pesato. Algoritmo di Dijkstra. Chiusura transitiva. Algoritmo a matrice di adiacenza. Algoritmo di Warshall. Albero ricoprente e minimo albero ricoprente. Algoritmo di Prim. Algoritmo di Kruskal.

Metodi di ricerca

• Ricerca lineare: tabella ordinata e non ordinata, costro con equiprobabilità, distribuzione di Ziff, legge di Helsing.
• Ricerca logaritmica: metodo standard, metodo con interpolazione.
• Albero binario di ricerca: albero bilanciato (AVL), perfettamente bilanciato, quasi perfettamente bilanciato, fattore di bilanciamento, teorema AVL, algoritmi di bilanciamento.
• Ricerca hash: concetto di funzione hash, hash perfetto e non perfetto, hash per chiavi alfanumeriche, risoluzione delle collisioni (catene interne ed esterne), risoluzione collisioni "open" (scansione lineare, scansione quadratica normale e pesata, scansione random), double hashing, strategie di cancellazione, valutazione metodi hash.

Modelli per memoria secondaria

• Memorie secondarie: unità a nastro, unità a disco, metodi di accesso, organizzazione sequenziale e ad accesso mirato (ordinamento per posizione, per chiave, struttura sequenziale ordinata e non).
• File Hash: funzionamento a blocchi, recupero overflow, hash dinamico.
• File indicizzati: organizzazione secondaria, concetto di indice e principio di guadagno, ISAM (overflow interno ed esterno).
• B-alberi: alberi AVL in memoria secondaria (strategia lineare, raggruppata e ottima), definizione di B-albero, criterio di ricerca, evoluzione di un B-albero, esplorazione ordinata, gestione di overflow, analisi delle prestazioni, costo di inserzione, pregi e difetti, albero B+ e B*.

Complessità

• Tipologia di macchine di Turing. Macchina di Turing non deterministica. Definizione di complessità in tempo. Macchina Ram e formato delle istruzioni.
• Complessità computazionale: criterio del costo uniforme e logaritmico, ipotesi della teoria della complessità e teorema di Ram-Turing, operazione dominante, complessità asintotica e regole di composizione.
• Modelli per linguaggi di alto livello: regole dei costi (I/O, cicli, test, sequenze), valore di taglio e tirannia della crescita, formule di ricorrenza (selection sort, ricerca binaria, quicksort perfetto e medio).
• Algoritmi ottimali di ordinamento: albero binario esteso (EPL, IPL), albero quasi perfettamente bilanciato (EPL), concetto di albero di decisione come algoritmo, limite minimo dell'ordinamento, enumerazione, backtracking, backtracking ricorsivo, branch and bound.
• Modelli di calcolo: correlazione tra modelli, problemi polinomialmente decidibili (P e NP), riducibilità dei problemi.

Linguaggi

• Assemblatore: necessità, istruzioni, pseudoistruzioni, macroistruzioni, tavola delle macroistruzioni, codici operativi, simboli, a due passi e ad un passo.
• Linguaggi formali: Sintassi, semantica e linguaggio, operazione concatenazione, teorema di Cantor, grammatica e produzioni, progetto di generazione diretta e linguaggio formale, produzione (albero sintattico e grafico sintattico), operazioni sui linguaggi (unione, intersezione, differenza, potenza ennesima, chiusura), classificazione di Chomsky (tipo 0,1,2,3), grammatiche equivalenti e non ambigue.
• Automi a stati finiti: automa deterministico con grammatiche regolari, automa non deterministico, trasformazione di automi.
• Analisi sintattica: obiettivi e strategie, concetto di analisi top-down, eliminazione backtracking, concetto di analisi bottom-up, grammatica a operatori a precedenza, teorema di Floyd e applicazione.
• Struttura del compilatore: compilatore e interpreti, analisi lessicale, sintattica e semantica, sintesi del programma.