Strutture dati e algoritmi (in riga ingegneria Vol. 112) [repost]

Uno dei problemi fondamentali dell’informatica consiste nella modellazione dell’informazione secondo categorie che ne permettano la rappresentazione, l’elaborazione e la memorizzazione con sistemi automatici. Le informazioni sono rappresentate per mezzo di dati. Partendo da dati intrinsecamente primitivi, come per esempio i numeri interi o i caratteri, è possibile definire dati più complessi, aggregati dei precedenti, ottenendo così strutture dati sempre più articolate. Le esigenze di generalizzazione hanno portato addirittura a definire tipi di dati astratti, nei quali esiste una netta separazione fra l’implementazione interna e l’interfaccia che definisce le operazioni possibili sui dati. Per esempio, nel caso di una pila (stack) sono definite soltanto le operazioni di inserimento ed estrazione di un elemento. Gli elementi possono essere inseriti e rimossi solo partendo dalla prima posizione. L’astrazione della struttura dati si manifesta considerando che nella pila è possibile inserire e rimuovere dati di qualunque tipo. Sui dati vengono eseguite operazioni. Fra le operazioni normalmente necessarie in qualsiasi ambito applicativo, sono particolarmente importanti la ricerca e l’ordinamento dei dati. Un metodo di ricerca efficiente permette di ridurre il tempo e il costo computazionale necessari per identificare un dato. L’ordinamento dei dati ne favorisce la ricerca. Ricerca e ordinamento sono esempi di algoritmi, ovvero sequenze finite e ordinate di azioni elementari che descrivono la soluzione di un problema.

L’autore

Marco L. Ferrario, nato a Milano nel 1965, laureato in Ingegneria Elettronica lavora nello sviluppo di software per applicazioni industriali e per il loro supporto tecnico. È autore del romanzo Confessioni di un malandrino pubblicato con la casa editrice GoWare.

Sommario

1. INTRODUZIONE AGLI ALGORITMI E AI TIPI DI DATI
• 2. TIPI DI DATI PRIMITIVI
• 3. TIPI DI DATI DERIVATI - 3.1. Array - 3.2. Matrici - 3.3. Stringhe - 3.4. Record - 3.5. Strutture complesse - 3.6. Puntatori - 3.7. Liste - 3.8. Alberi - 3.9. Trasformazioni hash
• 4. RICERCA DI DATI - 4.1. Ricerca sequenziale - 4.2. Ricerca binaria
• 5. ORDINAMENTO DI DATI - 5.1. Ordinamento per inserimento - 5.2. Ordinamento per selezione - 5.3. Ordinamento per scambio a bolle - 5.4. Ordinamenti evoluti: shellsort - 5.5. Ordinamenti evoluti: quicksort
• 6. COMPLESSITÀ DEGLI ALGORITMI.

Estratto dal Manuale Cremonese di Informatica e Telecomunicazioni Zanichelli

L'autore
Marco L. Ferrario, nato a Milano nel 1965, laureato in Ingegneria Elettronica lavora nello sviluppo di software per applicazioni industriali e per il loro supporto tecnico. È autore del romanzo Confessioni di un malandrino pubblicato con la casa editrice GoWare.