[IV] - Fondamenti di Informatica 2

Download PDF appunti
fondamenti di informatica 2

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