Algoritmo di ricerca
Da Wikipedia, l'enciclopedia libera.
Un algoritmo di ricerca è un algoritmo che permette di trovare un elemento avente determinate caratteristiche all'interno di un insieme di elementi.
Gli elementi dell'insieme sono caratterizzati da una chiave e da un gruppo di dati satellite. Nella descrizione degli algoritmi di ricerca, i dati satellite vengono tipicamente ignorati perché non sono utilizzati nella ricerca.
La chiave è quell'insieme di valori che identifica un elemento dell'insieme. Ha un ruolo fondamentale perché un algoritmo ricerca quell'elemento che possiede una certa chiave.
La chiave può avere un qualsiasi tipo di dato e può anche essere formata da un insieme di valori: dipende dal tipo di insieme che si vuole rappresentare. La chiave può essere univoca in tutto l'insieme di elementi, oppure multipla qualora sia consentito di condividerla tra più elementi distinti. In questo secondo caso è fondamentale specificare il corretto comportamento di un algoritmo di ricerca. Bisogna infatti decidere se sarà restituito il primo elemento dotato di una certa chiave, l'ultimo, uno qualsiasi o anche tutti.
[modifica] Tabella di simboli
Una tabella di simboli è una struttura dati formata da un record con chiave che supporta due operazioni di base: inserimento di un nuovo record e ricerca di un record avente una data chiave. La tabella di simboli viene spesso chiamata dizionario per l'analogia che ha con esso. Questo tipo di struttura permette di avere molta dinamicità sui dati con possibilità di modifiche elastiche nel tempo. Molti metodi di ricerca costruiscono strutture dati che consentono efficienti operazion di ricerca basate proprio su questo concetto di tabella di simboli.
L'ottimizzazione di algoritmi di ricerca è molto importante in ambito informatico.
[modifica] Tipologie di algoritmi
Il problema della ricerca appena descrito è un problema appartenente alla classe P, per cui esistono algoritmi risolutivi di complessità polinomiale.
- Ricerca sequenziale
- Ricerca con il metodo di Insert (InsertSort)
- Ricerca sequenziale con sentinella
- Ricerca su array ordinato
- Ricerca Hash
- Ricerca Ricorsiva
- Ricerca binaria o dicotomica
- Ricerca su alberi B-Tree
[modifica] Collegamenti esterni
- Una breve guida agli algoritmi di ordinamento e ricerca: http://epaperpress.com/sortsearchItalian/index.html (in italiano)
- C - esempi di programmazione: http://www.to.infn.it/groups/group4/mirror/linux/AppuntiLinux/AL-9.27.131.html