4 Parte I - Fondamenti

(1)

Introduzione

Questa parte `e un’introduzione alle tecniche di progettazione e analisi degli algoritmi. `E stata ideata per presentare gradualmente il modo in cui specifichiamo gli algoritmi, alcune strategie di progettazione che saranno utilizzate in questo libro e molti dei concetti fondamentali dell’analisi degli algoritmi. Le parti successive del libro si fondano su queste basi.

Il Capitolo 1 è una panoramica degli algoritmi e del loro ruolo nei moderni sistemi di elaborazione dei dati. Questo capitolo definisce che cos’è un algoritmo e fornisce alcuni esempi. Ipotizza inoltre che gli algoritmi siano una tecnologia, esattamente come le unità hardware veloci, le interfacce grafiche, i sistemi orientati agli oggetti e le reti.

Nel Capitolo 2 presentiamo i primi algoritmi che risolvono il problema dell’ordinamento di una sequenza di n numeri. Ogni algoritmo `e scritto con un semplice pseudocodice che, sebbene non sia direttamente traducibile in uno dei linguaggi di programmazione convenzionali, presenta la struttura dell’algoritmo in modo sufficientemente chiaro per consentire a un programmatore di implementarla nel suo linguaggio preferito. Fra gli algoritmi di ordinamento esaminati figurano in- sertion sort, che usa un approccio incrementale, e merge sort, che usa una tecnica ricorsiva detta “divide et impera”. Sebbene il tempo di calcolo richiesto da ciascun algoritmo cresca con il valore di n, tuttavia il tasso di crescita di questo tempo va- ria fra i due algoritmi. Il Capitolo 2 descrive come calcolare i tempi di esecuzione degli algoritmi e presenta un’utile notazione per esprimerli.

Il Capitolo 3 definisce con esattezza questa notazione, che chiameremo nota- zione asintotica. Inizialmente, presenteremo varie notazioni asintotiche, che poi utilizzeremo per definire i limiti dei tempi di esecuzione degli algoritmi. La parte restante del capitolo `e essenzialmente una presentazione di notazioni matemati- che; lo scopo principale non `e quello di insegnarvi nuovi concetti matematici, ma bens`ı garantire che le vostre notazioni siano conformi a quelle adottate in questo libro.

Il Capitolo 4 tratta pi`u approfonditamente il metodo divide et impera introdotto nel Capitolo 2. In particolare, presenteremo i metodi per risolvere le ricorrenze, che sono utili per descrivere i tempi di esecuzione degli algoritmi ricorsivi.

Una tecnica molto efficace `e il “metodo dell’esperto” che pu`o essere impiega- to per risolvere le ricorrenze che derivano dagli algoritmi divide et impera. Gran

(2)

4 Parte I - Fondamenti

parte di questo capitolo `e dedicata alla dimostrazione della correttezza del metodo dell’esperto (potete comunque tralasciare questa dimostrazione senza alcun problema).

Il Capitolo 5 introduce l’analisi probabilistica e gli algoritmi randomizzati. Ti- picamente, l’analisi probabilistica viene utilizzata per determinare il tempo di esecuzione di un algoritmo nel caso in cui, per la presenza di una particolare distribuzione di probabilità, il tempo di esecuzione vari con input diversi della stessa dimensione. In alcuni casi, supponiamo che gli input siano conformi a una distribuzione di probabilità nota, in modo da mediare il tempo di esecuzione su tutti i possibili input. In altri casi, la distribuzione di probabilità non proviene dagli input, ma da scelte casuali effettuate durante lo svolgimento dell’algoritmo. Un algoritmo il cui comportamento è determinato non soltanto dai suoi input, ma anche dai valori prodotti da un generatore di numeri casuali è detto algoritmo randomizzato. `E possibile utilizzare gli algoritmi randomizzati per imporre una distribuzione di probabilità agli input – garantendo cos`ı che nessun input possa sistematicamente provocare una riduzione delle prestazioni – o anche per limitare il tasso di errore di algoritmi cui è consentito produrre risultati affetti da un errore controllato.

Le Appendici A-C trattano altri concetti matematici che vi saranno particolarmente utili durante la lettura di questo libro. `E probabile che conosciate gi`a molti degli argomenti descritti nelle appendici (sebbene le particolari notazioni da noi adottate possano differire in alcuni casi da quelle che conoscete), quindi potete considerare le appendici come materiale di riferimento. D’altra parte, potreste non avere mai visto molti argomenti della Parte I. Tutti i capitoli della Parte I e delle appendici sono scritti con la tipica forma dei tutorial.

(3)

Ruolo degli algoritmi

nell’elaborazione dei dati 1

Che cosa sono gli algoritmi? Perché è utile studiare gli algoritmi? Qual è il ruolo degli algoritmi rispetto ad altre tecnologie utilizzate nei calcolatori? In questo capitolo risponderemo a queste domande.

1.1 Algoritmi

Informalmente, un algoritmo `e una procedura di calcolo ben definita che prende un certo valore, o un insieme di valori, come input e genera un valore, o un insieme di valori, come output. Un algoritmo `e quindi una sequenza di passi computazionali che trasforma l’input in output.

Possiamo anche considerare un algoritmo come uno strumento per risolvere un problema computazionale ben definito. La definizione del problema specifica in termini generali la relazione di input/output desiderata. L’algoritmo descrive una specifica procedura computazionale per ottenere tale relazione di input/output.

Per esempio, supponiamo di dovere ordinare una sequenza di numeri in ordine non decrescente. Questo problema si presenta spesso nella pratica e rappresenta un terreno fertile per introdurre vari strumenti di analisi e tecniche di progettazio- ne standard. Il problema dell’ordinamento pu`o essere formalmente definito nel seguente modo:

Input: una sequenza di n numeria¹, a2, . . . , an.

Output: una permutazione (riordinamento) a^′¹, a^′₂, . . . , a^′_n della sequenza di input tale che a^′1 ≤ a^′² ≤ · · · ≤ a^′ⁿ.

Per esempio, data la sequenza di input31,41,59,26,41,58, un algoritmo di ordinamento restituisce come output la sequenza26, 31, 41, 41, 58, 59. Tale sequen- za di input `e detta istanza del problema dell’ordinamento. In generale, l’istanza di un problema `e formata dall’input (che soddisfa tutti i vincoli imposti nella definizione del problema) richiesto per calcolare una soluzione del problema.

L’ordinamento è un’operazione fondamentale in informatica (molti programmi la usano come passo intermedio), per questo sono stati sviluppati vari algoritmi di ordinamento. La scelta dell’algoritmo più appropriato a una data applicazione dipende – fra l’altro – dal numero di elementi da ordinare, dal livello di ordinamento iniziale degli elementi, da eventuali vincoli sui valori degli elementi e dal tipo di unità di memorizzazione da utilizzare: memoria principale, dischi o nastri.

Un algoritmo si dice corretto se, per ogni istanza di input, termina con l’output corretto. Diciamo che un algoritmo corretto risolve il problema computazionale dato. Un algoritmo errato potrebbe non terminare affatto con qualche istanza di input o potrebbe terminare fornendo una soluzione diversa da quella desiderata.

Contrariamente a quello che uno potrebbe aspettarsi, gli algoritmi errati a vol-

(4)

6 Capitolo 1 - Ruolo degli algoritmi nell’elaborazione dei dati

te possono essere utili, se il loro tasso di errore pu`o essere controllato. Vedremo un esempio di questo nel Capitolo 31 quando studieremo gli algoritmi per trovare i numeri primi grandi. Di solito, tuttavia, ci occuperemo soltanto di algoritmi corretti.

Un algoritmo pu`o essere specificato in lingua italiana, come un programma per computer, o perfino come un progetto hardware. L’unico requisito `e che la specifica deve fornire una descrizione esatta della procedura computazionale da seguire.

Quali problemi risolvono gli algoritmi?

L’ordinamento non `e affatto l’unico problema computazionale per cui sono stati sviluppati gli algoritmi (molti lo avranno intuito osservando la mole di questo libro). Le applicazioni pratiche degli algoritmi sono innumerevoli; ne citiamo alcune:

• Il Progetto Genoma Umano ha l’obiettivo di identificare tutti i 100.000 geni del DNA umano, determinando le sequenze di 3 miliardi di paia di basi chimi- che che formano il DNA umano, registrando queste informazioni nei database e sviluppando gli strumenti per analizzare i dati. Ciascuno di questi passaggi richiede sofisticati algoritmi. Sebbene le soluzioni di questi problemi esulino dagli obiettivi di questo libro, i concetti esposti in molti capitoli vengono utilizzati per risolvere tali problemi biologici, consentendo cos`ı agli scienziati di svolgere i loro compiti utilizzando in modo efficiente le risorse. Si rispar- mia tempo (di persone e macchine) e denaro, in quanto `e possibile estrarre pi`u informazioni dalle tecniche di laboratorio.

• Internet consente agli utenti di tutto il mondo di accedere rapidamente a grandi quantit`a di informazioni. Per fare ci`o vengono impiegati algoritmi intelligenti che gestiscono e manipolano enormi volumi di dati. Fra gli esempi di problemi che devono essere risolti citiamo la ricerca dei percorsi ottimali che i dati devono seguire (le tecniche per risolvere questi problemi sono descritte nel Capitolo 24) e l’uso di un motore di ricerca per trovare velocemente le pagine che contengono una particolare informazione (le relative tecniche sono trattate nei Capitoli 11 e 32).

• Il commercio elettronico consente di negoziare e scambiare elettronicamente beni e servizi. La capacit`a di mantenere riservate informazioni quali i codici delle carte di credito, le password e gli estratti conto `e essenziale alla diffusione su vasta scala del commercio elettronico. La crittografia a chiave pubblica e le firme digitali (descritte nel Capitolo 31) sono le principali tecnologie utilizzate e si basano su algoritmi numerici e sulla teoria dei numeri.

• Nelle attività industriali e commerciali spesso è importante allocare poche risorse nel modo più vantaggioso. Una compagnia petrolifera potrebbe essere interessata a sapere dove disporre i propri pozzi per massimizzare i profitti.

Un candidato alla presidenza degli Stati Uniti d’America potrebbe essere interessato a determinare in quale campagna pubblicitaria investire i suoi soldi per massimizzare le probabilit`a di vincere le elezioni. Una compagnia aerea potrebbe essere interessata ad assegnare il personale ai voli nel modo pi`u eco- nomico possibile, verificando che ogni volo sia coperto e che siano soddisfatte le disposizioni governative sulla programmazione del personale di volo. Un

(5)

1.1 Algoritmi 7 provider di servizi Internet potrebbe essere interessato a determinare dove al-

locare delle risorse addizionali per servire i suoi clienti in modo pi`u efficiente.

Tutti questi sono esempi di problemi che possono essere risolti utilizzando la programmazione lineare, che sar`a trattata nel Capitolo 29.

Sebbene alcuni dettagli di questi esempi esulino dagli scopi di questo libro, tuttavia `e opportuno descrivere le tecniche di base che si applicano a questi tipi di problemi. Spiegheremo inoltre come risolvere molti problemi concreti, inclusi i seguenti:

• Supponiamo di avere una carta stradale dove sono segnate le distanze fra ogni coppia di incroci adiacenti; il nostro obiettivo è determinare il percorso più breve da un incrocio all’altro. Il numero di percorsi possibili può essere enor- me, anche se escludiamo i percorsi che passano su sé stessi. Come scegliere il più breve di tutti i percorsi? In questo caso, creiamo un modello della carta stradale (che a sua volta è un modello delle strade reali) come un grafo (che descriveremo nel Capitolo 10 e nell’Appendice B) e cerchiamo di determinare il cammino più breve da un vertice all’altro del grafo. Spiegheremo come risolvere efficientemente questo problema nel Capitolo 24.

• Data una sequenza A¹, A2, . . . , An di n matrici, vogliamo determinare il loro prodotto A1A2· · · Aⁿ. Poich´e la moltiplicazione di matrici `e associativa, ci sono vari modi di moltiplicare. Per esempio, se n = 4, potremmo eseguire il prodotto delle matrici in uno dei seguenti modi: (A1(A2(A3A4))), (A1((A2A3)A4)), ((A1A2)(A3A4)), ((A1(A2A3))A4) o (((A1A2)A3)A4).

Se le matrici sono tutte quadrate (e quindi della stessa dimensione), il modo di moltiplicare le matrici non avrà effetto sul tempo richiesto per eseguire il prodotto. Se, invece, queste matrici hanno dimensioni differenti (ma compa- tibili con la moltiplicazione delle matrici), allora il modo di moltiplicare può determinare una differenza significativa. Il numero dei possibili modi di moltiplicare le matrici è esponenziale in n, pertanto provare tutti i possibili modi potrebbe richiedere un tempo molto lungo. Vedremo nel Capitolo 15 come utilizzare una tecnica generale, la programmazione dinamica, per risolvere questo problema in una maniera molto più efficiente.

• Data l’equazione ax ≡ b (mod n), dove a, b e n sono interi, vogliamo determinare tutti gli interi x, modulo n, che soddisfano l’equazione. Ci possono essere zero, una o pi`u soluzioni. Potremmo semplicemente provare x = 0, 1, . . . , n−1 nell’ordine, ma il Capitolo 31 descrive un metodo pi`u efficiente.

• Dati n punti nel piano, vogliamo determinare il guscio convesso di questi punti. Il guscio convesso `e il pi`u piccolo poligono convesso che contiene i punti.

Intuitivamente, possiamo immaginare ogni punto come se fosse rappresentato da un chiodo che fuoriesce da una tavola. Il guscio convesso potrebbe essere rappresentato da un elastico teso che circonda tutti i chiodi. Ogni chiodo attor- no al quale l’elastico fa un giro `e un vertice del guscio convesso (un esempio

è illustrato nella Figura 33.6 a pagina 805). Uno dei2ⁿ sottoinsiemi dei punti potrebbe essere formato dai vertici del guscio convesso. Conoscere i punti che formano i vertici del guscio convesso non è sufficiente, in quanto occorre sapere anche l’ordine in cui essi si presentano. Ci sono dunque molte possibilità di scelta per i vertici del guscio convesso. Il Capitolo 33 descrive due buoni metodi per trovare il guscio convesso.

(6)

Questo elenco non `e affatto esaustivo (come probabilmente avrete immaginato dalle dimensioni di questo libro), ma presenta due caratteristiche che sono comuni a molti algoritmi.

1. Esistono numerose soluzioni possibili, molte delle quali non sono ci`o che vogliamo. Trovare quella desiderata pu`o essere un’impresa ardua.

2. Esistono varie applicazioni pratiche. Fra i problemi precedentemente elencati, determinare il percorso più breve rappresenta l’esempio più semplice. Un’a- zienda di trasporti su strada o rotaie è interessata a trovare i percorsi minimi nelle reti stradali o ferroviarie, perché tali percorsi consentono di risparmiare costi di manodopera e carburante. Come altro esempio, potrebbe essere neces- sario un nodo di routing su Internet per trovare il percorso più breve nella rete che permette di instradare rapidamente un messaggio.

Strutture dati

Questo libro contiene anche diverse strutture dati. Una struttura dati `e un mo- do per memorizzare e organizzare i dati e semplificarne l’accesso e la modifica.

Non esiste un’unica struttura dati che va bene per qualsiasi compito, quindi `e importante conoscere vantaggi e svantaggi di queste strutture.

Tecnica

Sebbene possiate utilizzare questo libro come un “libro di ricette” per algoritmi, tuttavia un giorno potreste incontrare un problema per il quale non riuscite a trovare un algoritmo pubblicato (come molti esercizi e problemi di questo libro!). Il libro vi insegna le tecniche per progettare e analizzare gli algoritmi, in modo che possiate sviluppare i vostri algoritmi, dimostrare che forniscono la risposta esatta e valutare la loro efficienza.

Problemi difficili

Gran parte di questo libro è dedicata agli algoritmi efficienti. La tipica unità di misura dell’efficienza è la velocità, ovvero quanto tempo impiega un algoritmo per produrre il suo risultato. Ci sono problemi, tuttavia, per i quali non si conosce una soluzione efficiente. Il Capitolo 34 studia un interessante sottoinsieme di questi problemi, noti come problemi NP-completi.

Perché sono interessanti i problemi NP-completi? In primo luogo, sebbene non sia stato ancora trovato un algoritmo efficiente per un problema NP-completo, tuttavia nessuno ha dimostrato che non possa esistere un algoritmo efficiente per uno di questi problemi. In altre parole, non sappiamo se esistano algoritmi efficienti per i problemi NP-completi. In secondo luogo, l’insieme dei problemi NP- completi gode dell’importante proprietà che, se esiste un algoritmo efficiente per uno di essi, allora esistono algoritmi efficienti per tutti questi problemi. Questa relazione fra i problemi NP-completi rende molto più attraente la mancanza di soluzioni efficienti. In terzo luogo, molti problemi NP-completi sono simili, non identici, ai problemi per i quali conosciamo gli algoritmi efficienti. Una piccola variazione della definizione del problema può causare una grande variazione dell’efficienza del migliore algoritmo conosciuto.

E importante conoscere i problemi NP-completi perch´e spesso alcuni di essi si` presentano in modo inaspettato nelle applicazioni reali. Se vi chiedessero di creare

(7)

1.2 Algoritmi come tecnologia 9 un algoritmo efficiente per un problema NP-completo, rischiereste di sprecare

molto del vostro tempo in ricerche inutili. Se riuscite a dimostrare che il problema

`e NP-completo, allora potrete impiegare il vostro tempo a sviluppare un algoritmo efficiente che fornisce una buona soluzione, non la migliore possibile.

Come esempio concreto, considerate un’impresa di trasporti che abbia un magazzino centrale. Tutte le mattine un autocarro viene caricato presso il magazzino e poi indirizzato alle varie destinazioni per consegnare le merci. Alla fine della giornata l’autocarro deve ritornare al magazzino per essere pronto per il giorno successivo. Per ridurre i costi, l’azienda intende scegliere un ordine di ferma- te per le consegne che consenta all’autocarro di percorrere la distanza minima.

Si tratta del cosiddetto “problema del commesso viaggiatore” ed `e un problema NP-completo. Non esiste un algoritmo efficiente. Sotto opportune ipotesi, tuttavia, ci sono algoritmi efficienti che forniscono una distanza complessiva che non `e molto diversa da quella minima. Il Capitolo 35 tratta questi “algoritmi di approssimazione”.

Esercizi 1.1-1

Indicate un esempio nel mondo reale in cui si presenta uno dei seguenti problemi computazionali: ordinamento, determinare il modo ottimale di moltiplicare le matrici o trovare il guscio convesso.

1.1-2

Oltre alla velocit`a, quali altri indici di efficienza potrebbero essere utilizzati in uno scenario del mondo reale?

1.1-3

Scegliete una struttura dati che avete visto in precedenza e analizzatene vantaggi e svantaggi.

1.1-4

In che modo sono simili i problemi del percorso minimo e del commesso viaggiatore? In che modo differiscono?

1.1-5

Descrivete un problema del mondo reale in cui `e ammissibile soltanto la soluzione ideale. Poi indicatene uno in cui `e accettabile una soluzione che “approssima”

quella ideale.

1.2 Algoritmi come tecnologia

Se i computer fossero infinitamente veloci e la memoria dei computer fosse gra- tuita, avremmo ancora qualche motivo per studiare gli algoritmi? La risposta `e s`ı, se non altro perch´e vorremmo ugualmente dimostrare che il nostro metodo di risoluzione termina e fornisce la soluzione esatta.

Se i computer fossero infinitamente veloci, qualsiasi metodo corretto per risolvere un problema andrebbe bene. Probabilmente, vorremmo che la nostra implementazione rispettasse le buone norme dell’ingegneria del software (ovvero fosse ben progettata e documentata), ma il più delle volte adotteremmo il metodo più semplice da implementare. Ovviamente, i computer possono essere veloci, ma non infinitamente veloci. La memoria può costare poco, ma non può essere gra-

(8)

tuita. Il tempo di elaborazione e lo spazio nella memoria sono risorse limitate, che devono essere saggiamente utilizzate; gli algoritmi che sono efficienti in termini di tempo o spazio ci aiuteranno a farlo.

Efficienza

Algoritmi progettati per risolvere lo stesso problema spesso sono notevolmente diversi nella loro efficienza. Queste differenze possono essere molto pi`u significa- tive di quelle dovute all’hardware e al software.

Per esempio, nel Capitolo 2 esamineremo due algoritmi di ordinamento. Il pri- mo, detto insertion sort, impiega un tempo pari a circa c1n² per ordinare n elementi, dove c1 è una costante che non dipende da n; ovvero occorre un tempo all’incirca proporzionale a n². Il secondo algoritmo, merge sort, richiede un tem- po pari a circa c2nlg n, dove lg n sta per log2n e c2 è un’altra costante che non dipende da n. Insertion sort, di solito, ha un fattore costante più piccolo di merge sort (c1 < c2). Vedremo come i fattori costanti possano avere meno influenza sul tempo di esecuzione rispetto alla dimensione n dell’input. Quando merge sort ha un fattore lg n nel suo tempo di esecuzione, insertion sort ha un fattore n, che

è molto più grande. Sebbene insertion sort, di solito, sia più veloce di merge sort per input di piccole dimensioni, tuttavia quando la dimensione dell’input n diventa relativamente grande, il vantaggio di merge sort,lg n su n, compensa abbondan- temente la differenza fra i fattori costanti. Indipendentemente da quanto c1sia più piccola rispetto a c2, ci sarà sempre un punto oltre il quale merge sort è più rapido.

Come esempio concreto, mettiamo a confronto un computer veloce (computer A) che esegue insertion sort e un computer lento (computer B) che esegue merge sort. Entrambi devono ordinare un array di un milione di numeri. Suppo- niamo che il computer A esegua un miliardo di istruzioni al secondo e il computer B esegua soltanto 10 milioni di istruzioni al secondo, ovvero il computer A è 100 volte più veloce del computer B in termini di potenza di calcolo. Per rendere la differenza ancora più evidente, supponiamo che il miglior programmatore del mondo abbia codificato insertion sort nel linguaggio macchina del computer A e che il codice risultante richieda 2n² istruzioni per ordinare n numeri (in questo caso, c1 = 2). Merge sort, invece, è stato programmato per il computer B da un programmatore medio con un linguaggio di alto livello e un compilatore ineffi- ciente; il codice risultante richiede50n lg n istruzioni (c² = 50). Per ordinare un milione di numeri, il computer A impiega

2 · (10⁶)²istruzioni

10⁹ istruzioni/secondo = 2000 secondi mentre il computer B impiega

50 · 10⁶lg 10⁶istruzioni

10⁷istruzioni/secondo ≈ 100 secondi

Utilizzando un algoritmo il cui tempo di esecuzione cresce più lentamente, perfino con un compilatore scadente, il computer B è 20 volte più veloce del computer A!

Il vantaggio di merge sort è ancora più significativo se ordiniamo dieci milioni di numeri: insertion sort impiega più di 2 giorni, merge sort meno di 20 minuti. In generale, al crescere della dimensione del problema, aumenta il vantaggio relativo di merge sort.

(9)

1.2 Algoritmi come tecnologia 11

Algoritmi e altre tecnologie

L’esempio dimostra che gli algoritmi, come l’hardware, sono una tecnologia. Le prestazioni globali di un sistema dipendono tanto dalla scelta di algoritmi efficienti quanto dalla scelta di un hardware veloce. Analogamente a quanto `e avvenuto in altre tecnologie per calcolatori, anche gli algoritmi hanno avuto un loro rapido progresso. Qualcuno potrebbe chiedersi se gli algoritmi siano davvero cos`ı importanti per i moderni calcolatori alla luce di altre tecnologie avanzate, quali

• hardware con alte frequenze di clock, pipeline e architetture superscalari

• interfacce grafiche (GUI) intuitive e facili da usare

• sistemi orientati agli oggetti

• reti locali (LAN) e geografiche (WAN)

La risposta `e s`ı. Sebbene ci siano applicazioni che non richiedano esplicitamente un contenuto algoritmico a livello dell’applicazione (per esempio, alcune sempli- ci applicazioni web), molte richiedono una certa dose di contenuto algoritmico.

Per esempio, considerate un servizio web che determina come spostarsi da un sito all’altro (esistevano molti di questi servizi quando abbiamo scritto questo libro).

La sua implementazione dovrebbe fare affidamento su un hardware veloce, un’interfaccia grafica utente, una rete WAN e, possibilmente, anche su sistemi orientati agli oggetti; ma richiederebbe anche gli algoritmi per svolgere determinate opera- zioni, come trovare i percorsi (utilizzando un algoritmo per il percorso pi`u breve), rappresentare le mappe e interpolare gli indirizzi.

Inoltre, anche un’applicazione che non richiede un contenuto algoritmico a livello applicazione fa affidamento sugli algoritmi. L’applicazione fa affidamento su un hardware veloce? Il progetto dell’hardware utilizza gli algoritmi. L’applicazione fa affidamento su un’interfaccia grafica utente? Il progetto dell’interfaccia fa affidamento sugli algoritmi. L’applicazione fa affidamento sulle reti? Il routing delle reti impiega gli algoritmi. L’applicazione è stata scritta in un linguaggio diverso dal codice machina? Allora è stata elaborata da un compilatore, un inter- prete o un assembler, ciascuno dei quali utilizza ampiamente gli algoritmi. Gli algoritmi sono il nucleo delle principali tecnologie utilizzate nei moderni calcolatori. Grazie alle loro sempre crescenti capacità, i calcolatori vengono utilizzati per risolvere problemi più complicati che in passato. Come abbiamo visto nel pre- cedente confronto fra gli algoritmi insertion sort e merge sort, è con i problemi di dimensioni maggiori che le differenze di efficienza fra gli algoritmi diventano particolarmente evidenti.

Avere una solida base di conoscenza degli algoritmi e delle tecniche `e una ca- ratteristica che contraddistingue i programmatori esperti dai principianti. Con i moderni calcolatori, potete svolgere alcuni compiti senza sapere molto di algoritmi, ma con una buona conoscenza degli algoritmi, potete fare molto, molto di pi`u.

Esercizi 1.2-1

Indicate l’esempio di un’applicazione che richiede un contenuto algoritmico a livello dell’applicazione e descrivete la funzione degli algoritmi richiesti.

(10)

1.2-2

Supponete di confrontare le implementazioni di insertion sort e merge sort sulla stessa macchina. Con un input di dimensione n, insertion sort viene eseguito in 8n² passi, mentre merge sort viene eseguito in 64n lg n passi. Per quali valori di n insertion sort batte merge sort?

1.2-3

Qual è il più piccolo valore di n per cui un algoritmo il cui tempo di esecuzione è 100n²viene eseguito più velocemente di un algoritmo il cui tempo di esecuzione

`e2ⁿ sulla stessa macchina?

Problemi

1-1 Confronto fra i tempi di esecuzione

Per ogni funzione f(n) e tempo t della seguente tabella, determinate la massima dimensione n di un problema che pu`o essere risolto nel tempo t, supponendo che l’algoritmo che risolve il problema impieghi f(n) microsecondi.

1 1 1 1 1 1 1

secondo minuto ora giorno mese anno secolo

lg n√ n n nlg n

n² n³ 2ⁿ n!

Note

Ci sono molti testi eccellenti che trattano in generale gli algoritmi, fra i quali citiamo: Aho, Hopcroft e Ullman [5, 6], Baase e Van Gelder [26], Brassard e Bra- tley [46, 47], Goodrich e Tamassia [128], Horowitz, Sahni e Rajasekaran [158], Kingston [179], Knuth [182, 183, 185], Kozen [193], Manber [210], Mehlhorn [217, 218, 219], Purdom e Brown [252], Reingold, Nievergelt e Deo [257], Sed- gewick [269], Skiena [280], e Wilf [315]. Alcuni degli aspetti pi`u pratici della progettazione degli algoritmi sono descritti da Bentley [39, 40] e Gonnet [126].

I manuali Handbook of Theoretical Computer Science, Volume A [302] e CRC Handbook on Algorithms and Theory of Computation[24] riportano alcuni studi sugli algoritmi. Una panoramica sugli algoritmi utilizzati nella biologia computazionale si trova nei libri di testo di Gusfield [136], Pevzner [240], Setubal e Meidanis [272], e Waterman [309].