Algoritmi e programmazione/Le tabelle di simboli

Da WikiAppunti.
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 8. Le tabelle di simboli.
Gtk-go-back-ltr.svg  7. Gli heap Gtk-home.svg  Algoritmi e programmazione 9. Alberi binari di ricerca (BST)  Gtk-go-forward-ltr.svg

2 tabella di simboli (o dizionario) = struttura dati formata da record, ovvero struct con dati aggregati di cui uno è la chiave.

4 Si può estrarre la chiave dal record e stabilire se una chiave è minore o uguale a un'altra determinando una relazione d'ordine.

Algoritmi di ricerca[modifica]

Gli algoritmi di ricerca, cioè le implementazioni delle tabelle di simboli, possono avere strutture lineari, ad albero o a tabella di hash.

Strutture lineari[modifica]

  • 5 array: ordinati o non ordinati;
  • liste: ordinate o non ordinate;
  • tabelle ad accesso diretto: l'insieme K contenente tutti i dati memorizzati è un sottoinsieme dell'insieme universo U:
    • 7 vantaggio: ogni dato in un suo sottoinsieme K ha un indice → l'accesso è diretto (ricerca indicizzata per chiave);
    • 9 svantaggio: il vettore dovrà avere un numero di celle pari alla cardinalità di U → rimangono delle celle vuote → spreco di memoria lineare nel numero di dati, soprattutto se la cardinalità di K è molto minore di quella di U.

Strutture ad albero[modifica]

  • 6 alberi binari di ricerca (BST): efficienti;
  • alberi bilanciati: (es. RB-tree) garantiscono che le operazioni siano sempre di complessità logaritmica e non degenerino in lineari.

Operazioni[modifica]

  • 3 data una chiave → inserimento di un nuovo elemento
  • data una chiave → ricerca di un elemento[1]
  • data una chiave → cancellazione di elemento specificato
  • dato un numero k → selezione del k-esimo elemento più piccolo
  • ordinamento della tabella di simboli in base alla chiave
  • unione di due tabelle di simboli

Complessità di caso peggiore[modifica]

11-12 La complessità dell'inserimento di un nuovo elemento all'interno di una lista o di un array varia a seconda se gli elementi sono ordinati:

  • non ordinati: l'inserimento ha un costo unitario (per es. inserimento sempre in testa);
  • ordinati: l'inserimento ha un costo lineare, perché bisogna inserire il nuovo elemento mantenendo l'ordinamento:
    • array: bisogna spostare tutti gli elementi di una cella per far spazio al nuovo elemento;
    • liste: l'inserimento implica una ricerca per scansione.

13 La ricerca binaria si deve effettuare su un array ordinato → può essere inefficiente se l'array varia molto e bisogna ordinarlo spesso.

Complessità di caso medio[modifica]

15 Nel caso medio:

  • le operazioni sulle strutture lineari sono quasi sempre lineari nel numero dei dati;
  • le operazioni sulle strutture ad albero sono quasi sempre logaritmiche nel numero dei dati (nel caso peggiore sono lineari);
  • le operazioni sulle tabelle di hash hanno costo unitario, ma senza spreco di memoria come nelle tabelle ad accesso diretto.

Note[modifica]

  1. 15 Si distinguono le ricerche con successo (hit) e quelle con insuccesso (miss).
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 8. Le tabelle di simboli.
Gtk-go-back-ltr.svg  7. Gli heap Gtk-home.svg  Algoritmi e programmazione 9. Alberi binari di ricerca (BST)  Gtk-go-forward-ltr.svg