Algoritmo di ricerca
left|WikiLettera
Questo articolo è solo un abbozzo (stub). Se puoi contribuisci adesso a migliorarlo secondo le convenzioni di Wikipedia.
Per l'elenco completo degli stub riguardanti l'informatica, vedi la relativa categoria
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.
L'ottimizzazione di algoritmi di ricerca è molto importante in ambito informatico.
Il problema della ricerca appena descrito è un problema appartenente alla classe P, per cui esistono algoritmi risolutivi di complessità polinomiale.
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