IntroduzioneQuesta parte ` e unintroduzione alle tecniche di progettazione e analisi degli algo-ritmi.`E stata ideata per presentare gradualmente il modo in cui specichiamo glialgoritmi, alcune strategie di progettazione che saranno utilizzate in questo libroe molti dei concetti fondamentali dellanalisi degli algoritmi. Le parti successivedel libro si fondano su queste basi.Il Capitolo1` e una panoramicadeglialgoritmie delloro ruolonei modernisistemidi elaborazionedei dati.Questocapitolodeniscechecos` eun algori-tmo e fornisce alcuni esempi. Ipotizza inoltre che gli algoritmi siano una tecno-logia, esattamente come le unit` a hardware veloci, le interfacce grache, i sistemiorientati agli oggetti e le reti.Nel Capitolo 2 presentiamo i primi algoritmi che risolvono il problema dellor-dinamento di una sequenza di n numeri. Ogni algoritmo ` e scritto con un semplicepseudocodice che, sebbene non sia direttamente traducibile in uno dei linguaggidiprogrammazioneconvenzionali, presentala strutturadellalgoritmoin modosufcientemente chiaro per consentire a un programmatore di implementarla nelsuo linguaggio preferito. Fra gli algoritmi di ordinamento esaminati gurano in-sertion sort, che usa un approccio incrementale, e merge sort, che usa una tecnicaricorsiva detta divide et impera. Sebbene il tempo di calcolo richiesto da ciascunalgoritmo 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 esecuzionedegli algoritmi e presenta unutile notazione per esprimerli.Il Capitolo 3 denisce con esattezza questa notazione, che chiameremo nota-zione asintotica. Inizialmente, presenteremo varie notazioni asintotiche, che poiutilizzeremo per denire i limiti dei tempi di esecuzione degli algoritmi. La parterestante del capitolo` e essenzialmente una presentazione di notazioni matemati-che; lo scopo principale non ` e quello di insegnarvi nuovi concetti matematici, mabens` garantire che le vostre notazioni siano conformi a quelle adottate in questolibro.Il Capitolo 4 tratta pi ` u approfonditamente il metodo divide et impera introdottonel Capitolo2. Inparticolare, presenteremoimetodi perrisolverelericorren-ze, che sono utili per descrivere i tempi di esecuzionedegli algoritmi ricorsivi.Unatecnicamoltoefcace` e ilmetododellespertochepu` oessereimpiega-to per risolvere le ricorrenze che derivano dagli algoritmi divide et impera. Gran4 Parte I - Fondamentiparte di questo capitolo` e dedicataalla dimostrazionedella correttezzadel me-todo dellesperto (potete comunque tralasciare questa dimostrazione senza alcunproblema).Il Capitolo 5 introduce lanalisi probabilistica e gli algoritmi randomizzati. Ti-picamente, lanalisi probabilistica viene utilizzata per determinare il tempo di ese-cuzione di un algoritmo nel caso in cui, per la presenza di una particolare distri-buzione di probabilit` a, il tempo di esecuzione vari con input diversi della stessadimensione. In alcuni casi, supponiamo che gli input siano conformi a una distri-buzione di probabilit` a nota, in modo da mediare il tempo di esecuzione su tuttii possibiliinput.In altri casi, la distribuzionedi probabilit` anon provienedagliinput, ma da scelte casuali effettuate durante lo svolgimento dellalgoritmo.Unalgoritmoilcuicomportamento` edeterminatononsoltantodaisuoiinput, maanchedaivaloriprodotti daungeneratoredinumericasuali ` e dettoalgoritmorandomizzato.`E possibileutilizzare gli algoritmi randomizzati per imporre unadistribuzionedi probabilit` aagli input garantendo cos` che nessun input possasistematicamente provocare una riduzione delle prestazioni o anche per limitareil tasso di errore di algoritmi cui ` e consentito produrre risultati affetti da un errorecontrollato.Le Appendici A-C trattano altri concetti matematici che vi saranno particolar-mente utili durante la lettura di questo libro.`E probabile che conosciate gi` a moltidegli argomenti descritti nelle appendici (sebbene le particolari notazioni da noiadottatepossanodifferireinalcuni casidaquellecheconoscete), quindi pote-te considerare le appendici come materiale di riferimento. Daltra parte, potrestenon avere mai visto molti argomenti della Parte I. Tutti i capitoli della Parte I edelle appendici sono scritti con la tipica forma dei tutorial.Ruolo degli algoritminellelaborazione dei dati 1Che cosa sono gli algoritmi? Perch e ` e utile studiare gli algoritmi? Qual ` e il ruolodegli algoritmi rispettoadaltretecnologieutilizzatenei calcolatori?Inquestocapitolo risponderemo a queste domande.1.1 AlgoritmiInformalmente, un algoritmo ` e una procedura di calcolo ben denita che prendeuncertovalore, ouninsiemedi valori, comeinput egeneraunvalore, ouninsiemedi valori, comeoutput. Unalgoritmo` equindi unasequenzadi passicomputazionali che trasforma linput in output.Possiamo anche considerare un algoritmo come uno strumento per risolvere unproblema computazionale ben denito. La denizione del problema specica intermini generali la relazione di input/output desiderata. Lalgoritmo descrive unaspecica procedura computazionale per ottenere tale relazione di input/output.Per esempio, supponiamo di dovere ordinare una sequenza di numeri in ordinenon decrescente. Questo problema si presenta spesso nella pratica e rappresentaun terreno fertile per introdurre vari strumenti di analisi e tecniche di progettazio-ne standard. Il problema dellordinamento pu` o essere formalmente denito nelseguente modo:Input: una sequenza di n numeri a1, a2, . . . , an.Output: una permutazione(riordinamento) a

1,a

2,. . . , a

n dellasequenzadiinput tale che a

1 a

2 a

n.Per esempio, data la sequenza di input 31, 41, 59, 26, 41, 58, un algoritmo di ordi-namento restituisce come output la sequenza 26, 31, 41, 41, 58, 59. Tale sequen-za di input ` e detta istanza del problema dellordinamento. In generale, listanzadi un problema` eformatadallinput (chesoddisfatuttiivincoli impostinelladenizione del problema) richiesto per calcolare una soluzione del problema.Lordinamento ` e unoperazione fondamentale in informatica (molti programmila usano come passo intermedio), per questo sono stati sviluppati vari algoritmidi ordinamento. La scelta dellalgoritmo pi ` u appropriato a una data applicazionedipende fra laltro dal numero di elementi da ordinare, dal livello di ordina-mento iniziale degli elementi, da eventuali vincoli sui valori degli elementi e daltipo di unit` a di memorizzazione da utilizzare: memoria principale, dischi o nastri.Un algoritmo si dice corretto se, per ogni istanza di input, termina con loutputcorretto. Diciamo che un algoritmo corretto risolve il problema computazionaledato. Un algoritmo errato potrebbe non terminare affatto con qualche istanza diinput o potrebbe terminare fornendo una soluzione diversa da quella desiderata.Contrariamentea quelloche unopotrebbeaspettarsi, gli algoritmierratia vol-6 Capitolo 1 - Ruolo degli algoritmi nellelaborazione dei datite possono essere utili, se il loro tasso di errore pu` o essere controllato. Vedremoun esempio di questo nel Capitolo 31 quando studieremo gli algoritmi per trova-re i numeri primi grandi. Di solito, tuttavia, ci occuperemo soltanto di algoritmicorretti.Unalgoritmopu` oesserespecicatoinlinguaitaliana, comeunprogrammaper computer, o perno come un progettohardware. Lunico requisito` e che laspecica deve fornire una descrizione esatta della procedura computazionale daseguire.Quali problemi risolvono gli algoritmi?Lordinamento non` e affatto lunico problema computazionale per cui sono sta-tisviluppati glialgoritmi(moltiloavrannointuitoosservandola moledi que-sto libro). Le applicazioni pratiche degli algoritmi sono innumerevoli; ne citiamoalcune:Il Progetto Genoma Umano ha lobiettivo di identicare tutti i 100.000 genidel DNA umano, determinando le sequenze di 3 miliardi di paia di basi chimi-che che formano il DNA umano, registrando queste informazioni nei databasee sviluppando gli strumenti per analizzare i dati. Ciascuno di questi passaggirichiede sosticati algoritmi. Sebbene le soluzioni di questi problemi esulinodagli obiettivi di questo libro, i concetti esposti in molti capitoli vengono uti-lizzatiperrisolveretaliproblemibiologici, consentendocos`agliscienziatidi svolgere i loro compiti utilizzando in modo efciente le risorse. Si rispar-mia tempo (di persone e macchine) e denaro, in quanto ` e possibile estrarre pi ` uinformazioni dalle tecniche di laboratorio.Internet consente agli utenti di tutto il mondo di accedere rapidamente a grandiquantit` a di informazioni. Per fare ci ` o vengono impiegati algoritmi intelligentiche gestiscono e manipolano enormi volumi di dati. Fra gli esempi di proble-mi che devono essere risolti citiamo la ricerca dei percorsi ottimali che i datidevonoseguire(letecnicheperrisolverequestiproblemisonodescrittenelCapitolo 24) e luso di un motore di ricerca per trovare velocemente le pagineche contengono una particolare informazione (le relative tecniche sono trattatenei Capitoli 11 e 32).Il commercio elettronico consente di negoziare e scambiare elettronicamentebeni e servizi. La capacit` a di mantenere riservate informazioni quali i codicidelle carte di credito, le password e gli estratti conto ` e essenziale alla diffusionesu vasta scala del commercio elettronico. La crittograa a chiave pubblica e lerme digitali (descritte nel Capitolo 31) sono le principali tecnologie utilizzatee si basano su algoritmi numerici e sulla teoria dei numeri.Nelle attivit` a industriali e commerciali spesso ` e importante allocare poche ri-sorse nel modo pi ` u vantaggioso. Una compagnia petroliferapotrebbe essereinteressataa sapere dove disporrei propri pozzi per massimizzarei protti.Un candidato alla presidenza degli Stati Uniti dAmerica potrebbe essere in-teressato a determinare in quale campagna pubblicitaria investire i suoi soldiper massimizzare le probabilit` a di vincere le elezioni. Una compagnia aereapotrebbe essere interessata ad assegnare il personale ai voli nel modo pi ` u eco-nomico possibile, vericando che ogni volo sia coperto e che siano soddisfattele disposizioni governativesulla programmazionedel personaledi volo.Un1.1 Algoritmi 7provider di servizi Internet potrebbe essere interessato a determinare dove al-locare delle risorse addizionali per servire i suoi clienti in modo pi ` u efciente.Tutti questi sono esempi di problemi che possono essere risolti utilizzando laprogrammazione lineare, che sar` a trattata nel Capitolo 29.Sebbenealcuni dettaglidiquestiesempiesulinodagliscopidi questolibro,tuttavia` e opportuno descrivere le tecniche di base che si applicano a questi tipidi problemi. Spiegheremo inoltre come risolvere molti problemi concreti, inclusii seguenti:Supponiamo di avere una carta stradale dove sono segnate le distanze fra ognicoppiadi incrociadiacenti;il nostroobiettivo` e determinareil percorsopi ` ubreve da un incrocio allaltro. Il numero di percorsi possibili pu` o essere enor-me, anche se escludiamo i percorsi che passano su s e stessi. Come scegliereil pi ` u breve di tutti i percorsi? In questo caso, creiamo un modello della cartastradale (che a sua volta` e un modello delle strade reali) come un grafo (chedescriveremo nel Capitolo 10 e nellAppendice B) e cerchiamo di determina-re il cammino pi ` u breve da un vertice allaltro del grafo. Spiegheremo comerisolvere efcientemente questo problema nel Capitolo 24.Data una sequenza A1, A2, . . . , An di n matrici, vogliamodeterminareilloro prodottoA1A2 An. Poich e la moltiplicazione di matrici ` e associativa,ci sonovari modi di moltiplicare. Peresempio, sen=4, potremmoese-guireilprodottodellematriciinunodeiseguenti 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 mododi moltiplicare le matrici non avr` a effetto sul tempo richiesto per eseguire ilprodotto. Se, invece, queste matrici hanno dimensioni differenti (ma compa-tibili con la moltiplicazione delle matrici), allora il modo di moltiplicare pu` odeterminare una differenza signicativa. Il numero dei possibili modi di mol-tiplicare le matrici ` e esponenziale inn, pertanto provare tutti i possibili modipotrebbe richiedere un tempo molto lungo. Vedremo nel Capitolo 15 come uti-lizzare una tecnica generale, la programmazione dinamica, per risolvere questoproblema in una maniera molto pi ` u efciente.Data lequazioneax b (modn), dovea,b en sono interi, vogliamo de-terminare tutti gli interix, modulon, che soddisfano lequazione. Ci posso-no esserezero, una o pi ` u soluzioni. Potremmo semplicementeprovarex=0, 1, . . . , n1 nellordine, ma il Capitolo 31 descrive un metodo pi ` u efciente.Dati n punti nel piano, vogliamo determinare il guscio convesso di questi pun-ti. Il guscio convesso` e il pi ` u piccolo poligono convesso che contiene i punti.Intuitivamente, possiamo immaginare ogni punto come se fosse rappresentatoda un chiodo che fuoriesce da una tavola. Il guscio convesso potrebbe essererappresentato da un elastico teso che circonda tutti i chiodi. Ogni chiodo attor-no al quale lelastico fa un giro ` e un vertice del guscio convesso (un esempio` e illustrato nella Figura 33.6 a pagina 805). Uno dei 2nsottoinsiemi dei puntipotrebbe essere formato dai vertici del guscio convesso. Conoscere i punti cheformano i vertici del guscio convesso non ` e sufciente, in quanto occorre sa-pere anche lordine in cui essi si presentano. Ci sono dunque molte possibilit` adi scelta per i vertici del guscio convesso. Il Capitolo 33 descrive due buonimetodi per trovare il guscio convesso.8 Capitolo 1 - Ruolo degli algoritmi nellelaborazione dei datiQuesto elenco non ` e affatto esaustivo (come probabilmente avrete immaginatodalle dimensioni di questo libro), ma presenta due caratteristiche che sono comunia molti algoritmi.1. Esistononumerosesoluzioni possibili, moltedellequali nonsonoci ` ochevogliamo. Trovare quella desiderata pu` o essere unimpresa ardua.2. Esistono varie applicazioni pratiche. Fra i problemi precedentemente elencati,determinare il percorso pi ` u breve rappresenta lesempio pi ` u semplice. Una-zienda di trasporti su strada o rotaie` e interessata a trovare i percorsi miniminelle reti stradali o ferroviarie, perch e tali percorsi consentono di risparmiarecosti di manodopera e carburante. Come altro esempio, potrebbe essere neces-sario un nodo di routing su Internet per trovare il percorso pi ` u breve nella reteche permette di instradare rapidamente un messaggio.Strutture datiQuesto libro contieneanche diverse strutturedati. Una struttura dati ` e un mo-do per memorizzare e organizzare i dati e semplicarne laccesso e la modica.Nonesisteununicastrutturadati chevabeneperqualsiasi compito, quindi ` eimportante conoscere vantaggi e svantaggi di queste strutture.TecnicaSebbene possiate utilizzare questo libro come un libro di ricette per algoritmi,tuttavia un giorno potreste incontrare un problema per il quale non riuscite a tro-vare un algoritmo pubblicato (come molti esercizi e problemi di questo libro!). Illibro vi insegna le tecniche per progettare e analizzare gli algoritmi, in modo chepossiate sviluppare i vostri algoritmi, dimostrare che forniscono la risposta esattae valutare la loro efcienza.Problemi difciliGran parte di questo libro` e dedicata agli algoritmi efcienti. La tipica unit` a dimisura dellefcienza ` e la velocit` a, ovvero quanto tempo impiega un algoritmo perprodurre il suo risultato. Ci sono problemi, tuttavia, per i quali non si conosce unasoluzione efciente. Il Capitolo 34 studia un interessante sottoinsieme di questiproblemi, noti come problemi NP-completi.Perch e sono interessanti i problemi NP-completi? In primo luogo, sebbene nonsiastatoancoratrovatounalgoritmoefcienteperunproblemaNP-completo,tuttavia nessuno ha dimostrato che non possa esistere un algoritmo efciente peruno di questi problemi. In altre parole, non sappiamo se esistano algoritmi ef-cienti per i problemi NP-completi. In secondo luogo, linsieme dei problemi NP-completi gode dellimportante propriet` a che, se esiste un algoritmo efciente peruno di essi, allora esistonoalgoritmi efcienti per tutti questi problemi. Questarelazionefra i problemiNP-completi rende molto pi ` u attraentela mancanzadisoluzioni efcienti. In terzo luogo, molti problemi NP-completi sono simili, nonidentici, ai problemi per i quali conosciamogli algoritmi efcienti.Una picco-la variazione della denizione del problema pu` o causare una grande variazionedellefcienza del migliore algoritmo conosciuto.`E importante conoscere i problemi NP-completi perch e spesso alcuni di essi sipresentano in modo inaspettato nelle applicazioni reali. Se vi chiedessero di creare1.2 Algoritmi come tecnologia 9unalgoritmoefcienteperunproblemaNP-completo, rischierestedi sprecaremolto 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 algoritmoefciente che fornisce una buona soluzione, non la migliore possibile.Come esempio concreto, considerate unimpresa di trasporti che abbia un ma-gazzino centrale. Tutte le mattine un autocarro viene caricato presso il magazzinoe poi indirizzatoalle varie destinazioniper consegnare le merci. Alla ne dellagiornata lautocarro deve ritornare al magazzino per essere pronto per il giornosuccessivo. Perridurrei costi, laziendaintendescegliereunordinedi ferma-te per le consegneche consentaallautocarrodi percorrerela distanzaminima.Sitrattadel cosiddettoproblemadel commessoviaggiatoreed` eunproble-ma NP-completo. Non esiste un algoritmo efciente. Sotto opportune ipotesi, tut-tavia, cisonoalgoritmi efcienti chefornisconounadistanzacomplessivachenon` e molto diversa da quella minima. Il Capitolo 35 tratta questi algoritmi diapprossimazione.Esercizi1.1-1Indicate un esempio nel mondo reale in cui si presenta uno dei seguenti proble-mi computazionali: ordinamento, determinare il modo ottimale di moltiplicare lematrici o trovare il guscio convesso.1.1-2Oltre alla velocit` a, quali altri indici di efcienza potrebbero essere utilizzati in unoscenario del mondo reale?1.1-3Scegliete una struttura dati che avete visto in precedenza e analizzatene vantaggie svantaggi.1.1-4In che modo sono simili i problemi del percorso minimo e del commesso viaggia-tore? In che modo differiscono?1.1-5Descrivete un problema del mondo reale in cui ` e ammissibile soltanto la soluzioneideale. Poi indicateneunoin cui ` e accettabileuna soluzioneche approssimaquella ideale.1.2 Algoritmi come tecnologiaSe i computer fossero innitamente veloci e la memoria dei computer fosse gra-tuita,avremmo ancoraqualchemotivo per studiaregli algoritmi?La risposta` es`, se non altro perch e vorremmo ugualmente dimostrare che il nostro metodo dirisoluzione termina e fornisce la soluzione esatta.Se i computer fossero innitamente veloci, qualsiasi metodo corretto per risol-vere un problema andrebbe bene. Probabilmente, vorremmo che la nostra imple-mentazione rispettasse le buone norme dellingegneria del software (ovvero fosseben progettata e documentata), ma il pi ` u delle volte adotteremmo il metodo pi ` usemplicedaimplementare. Ovviamente, icomputerpossonoessereveloci, manon innitamente veloci. La memoria pu` o costare poco, ma non pu` o essere gra-10 Capitolo 1 - Ruolo degli algoritmi nellelaborazione dei datituita. Il tempo di elaborazione e lo spazio nella memoria sono risorse limitate, chedevono essere saggiamente utilizzate; gli algoritmi che sono efcienti in terminidi tempo o spazio ci aiuteranno a farlo.EfcienzaAlgoritmi progettatiper risolvere lo stesso problema spesso sono notevolmentediversi nella loro efcienza. Queste differenze possono essere molto pi ` u signica-tive di quelle dovute allhardware e al software.Per esempio, nel Capitolo 2 esamineremo due algoritmi di ordinamento. Il pri-mo, detto insertion sort, impiega un tempo pari a circac1n2per ordinaren ele-menti, dovec1` e una costanteche non dipende dan; ovvero occorre un tempoallincirca proporzionale a n2. Il secondo algoritmo, merge sort, richiede un tem-po pari a circac2nlg n, dove lg n sta per log2 n ec2` e unaltra costante che nondipende da n. Insertion sort, di solito, ha un fattore costante pi ` u piccolo di mergesort (c1 0 and A[i] > chiave6 do A[i + 1] A[i]7 i i 18 A[i + 1] chiaveInvarianti di ciclo e correttezza di insertion sortLa Figura 2.2 mostra come opera questo algoritmo conA= 5, 2, 4, 6, 1, 3).Lindice j identica la carta corrente che viene inserita nelle altre. Allinizio diogni iterazione del ciclo for esterno, il cui indice ` e j, il sottoarray che ` e formatodagli elementi A[1 . . j 1] costituisce la mano di carte correntemente ordinate egli elementi A[j + 1 . . n] corrispondono alla pila delle carte che si trovano ancorasul tavolo. In effetti, gli elementi A[1 . . j 1] sono quelli cheoriginariamenteoccupavano le posizioni da 1 aj 1, ma che adesso sono ordinati. Deniamoformalmente queste propriet` a di A[1 . . j 1] come invariante di ciclo:2.1 Insertion sort 151 2 3 4 5 65 2 4 6 1 3 (a)1 2 3 4 5 62 5 4 6 1 3 (b)1 2 3 4 5 62 4 5 6 1 3 (c)1 2 3 4 5 62 4 5 6 1 3 (d)1 2 3 4 5 62 4 5 6 1 3 (e)1 2 3 4 5 62 4 5 6 1 3 (f)Figura 2.2 Il funzionamento di INSERTION-SORT con larrayA= 5, 2, 4, 6, 1, 3). Gli indicidellarray sono indicati sopra i rettangoli; i valori memorizzati nelle posizioni dellarray sono in-dicati allinterno dei rettangoli. (a)(e) Le iterazioni del ciclo for (righe 18). In ogni iterazione, ilrettangolo nero contiene la chiave estratta da A[j], che viene confrontata con i valori nei rettangoligrigi alla sua sinistra nel test della riga 5. Le frecce grige mostrano i valori dellarray che vengonospostati di una posizione verso destra nella riga 6; le frecce nere indicano dove viene spostata lachiave nella riga 8. (f) Larray nale ordinato.Allinizio di ogni iterazione del ciclo for (righe 18), il sottoarray A[1 . . j1]` e formato dagli elementi ordinati che originariamente erano in A[1 . . j1].Utilizziamo le invarianti di ciclo per aiutarci a capire perch e un algoritmo ` e cor-retto. Dobbiamo dimostrare tre cose su uninvariante di ciclo:Inizializzazione: ` e vera prima della prima iterazione del ciclo.Conservazione: se` e vera prima di uniterazionedel ciclo, rimane vera primadella successiva iterazione.Conclusione: quando il ciclo termina, linvariante fornisce unutile propriet` a checi aiuta a dimostrare che lalgoritmo ` e corretto.Quando le prime due propriet` a sono valide, linvariante di ciclo ` e vera prima diogni iterazione del ciclo. Notate lanalogia con linduzione matematica, dove perprovare che una propriet` a ` e valida, si prova un caso base e un passaggio induttivo.Qui, dimostrare che linvariante ` e vera prima della prima iterazione equivale al ca-so base e dimostrare che linvariante resta vera da uniterazione allaltra equivaleal passaggio induttivo.La terza propriet` a ` e forse la pi ` u importante, perch e utilizziamo linvariante di ci-clo per dimostrare la correttezza. C` e anche una differenza con luso consueto del-linduzione matematica, dove il passaggio induttivo viene utilizzato allinnito;qui invece interrompiamo il processo induttivo quando il ciclo termina.Vediamo se queste propriet` a sono valide per insertion sort.Inizializzazione: iniziamo dimostrando che linvariante di ciclo ` e vera prima del-la prima iterazione del ciclo, quando j= 2.1Il sottoarray A[1 . . j 1], quindi,` e formato dal solo elementoA[1], che infatti` e lelemento originale inA[1].Inoltre, questo sottoarray` e ordinato (banale, ovviamente) e ci ` o dimostra chelinvariante di ciclo ` e vera prima della prima iterazione del ciclo.1Quando il ciclo ` e un ciclo for, il punto in cui verichiamo linvariante di ciclo appena prima dellaprima iterazione ` e immediatamente dopo lassegnazione iniziale del contatore del ciclo e appenaprima del primo test del ciclo. Nel caso di INSERTION-SORT, questo punto ` e dopo lassegnazionedi 2 alla variabile j, ma prima del primo test j lunghezza[A].16 Capitolo 2 - IntroduzioneConservazione: passiamo alla seconda propriet` a: dimostrare che ogni iterazio-ne conserva linvariante di ciclo. Informalmente, il corpo del ciclo for esternoopera spostando A[j 1], A[j 2], A[j 3] e cos` via di una posizione versodestra, nch e non trover` a la posizione appropriata per A[j] (righe 47), doveinserir` a il valore diA[j] (riga 8). Un trattamento pi ` u formale della secondapropriet` a richiederebbedi denire e dimostrare uninvariantedi ciclo per ilciclo while interno. A questo punto, tuttavia, preferiamo non impantanar-ci in simili formalismi; quindi, condiamo nella nostra analisi informale perdimostrare che la seconda propriet` a ` e vera per il ciclo esterno.Conclusione: inne, esaminiamo che cosa accade quando il ciclo termina. Perinsertion sort, il ciclo for esterno termina quandoj superan, ovvero quandoj=n + 1. Sostituendoj con n + 1 nella formulazione dellinvariante di ci-clo, otteniamo che il sottoarray A[1 . . n] ` e formato dagli elementi ordinati chesi trovavano originariamente in A[1 . . n]. Ma il sottoarrayA[1 . . n] ` e linteroarray! Dunque, tutto larray ` e ordinato; ci ` o signica che lalgoritmo ` e corretto.Applicheremo questo metodo delle invarianti di ciclo per dimostrare la correttezzapi ` u avanti in questo capitolo e in altri capitoli.Convenzioni di pseudocodicaAdotteremo le seguenti convenzioni nelle nostre pseudocodiche.1. Lindentazione (rientro verso destra delle righe) serve a indicare la struttura ablocchi dello pseudocodice. Per esempio, il corpo del ciclo for, che inizia nellariga 1, ` e formato dalla righe 28 e il corpo del ciclo while, che inizia nellariga 5, contiene le righe 67, ma non la riga 8. Il nostro stile di indentazione siapplica anche alle istruzioni if-then-else. Utilizzando lindentazione, anzich egli indicatori convenzionali della struttura a blocchi, come le istruzioni begine end, si riducemolto la confusione, preservandoo perno migliorandolachiarezza.22. I costrutti iterativi while, for e repeat e i costrutti condizionali if, then ed elsehanno interpretazioni simili a quelle del Pascal.3C` e tuttavia una piccola diffe-renza nei cicli for: nel Pascal il valore del contatore del ciclo ` e indenito dopola conclusione del ciclo, mentre in questo libro il contatore del ciclo mantieneil suo valore dopo la ne del ciclo. Quindi, immediatamente dopo un ciclo for,il valore del contatore del ciclo ` e quello che ha appena superato il limite delciclo for. Abbiamo utilizzato questa propriet` a nella nostra analisi della corret-tezza di insertion sort. La prima istruzione del ciclo for (riga 1) ` e for j 2to lunghezza[A]; quindi, alla ne di questo ciclo, j= lunghezza[A] + 1 (cheequivale a j= n + 1, in quanto n = lunghezza[A]).3. Il simbolo indica che il resto della riga ` e un commento.2Nei linguaggi di programmazione reali, in generale, non` e consigliabile utilizzare soltanto lin-dentazione per indicare la struttura a blocchi, in quanto i livelli di indentazione sono difcili dadeterminare quando il codice ` e distribuito su pi` u pagine.3Molti linguaggi con strutture a blocchi hanno costrutti equivalenti, anche se la sintassi esatta pu` odifferire da quella del Pascal.2.1 Insertion sort 174. Unassegnazionemultipladellaformai j e assegnaa entrambelevariabili i e j il valore dellespressionee; deve essere considerata equivalenteallassegnazione j e seguita dallassegnazionei j.5. Le variabili (come i, j e chiave) sono locali a una determinata procedura. Nondovremmo utilizzare variabili globali senza unesplicita indicazione.6. Per identicare un elemento di un array, specichiamo il nome dellarray se-guito dallindice dellelemento fra parentesi quadre. Per esempio, A[i] indicalelemento i-esimo dellarray A. La notazione . . ` e utilizzata per indicare unintervallo di valori allinterno di un array. Quindi, A[1 . . j] indica il sottoarraydi A che ` e composto da j elementi: A[1], A[2], . . . , A[j].7. I dati composti sono tipicamente organizzati in oggetti, che sono formati daattributi o campi. Un particolare campo ` e identicato utilizzando il nome delcampo seguito dal nome del suo oggetto fra parentesi quadre. Per esempio, noitrattiamo un array come un oggetto con lattributo lunghezza che indica il nu-mero di elementi contenuti nellarray. Per specicare il numero di elementi diun array A, scriviamo lunghezza[A]. Anche se utilizziamo le parentesi quadresia per gli indici degli array sia per gli attributi degli oggetti, di solito, ` e chiarodal contesto a cosa intendiamo riferirci.Una variabile che rappresenta un array o un oggetto` e trattata come un pun-tatore ai dati che costituiscono larray o loggetto. Per tutti i campifdi unoggetto x, lassegnazioney x implica che f[y]=f[x]. Inoltre, se poi im-postiamo f[x] 3, allora non soltanto sar` a f[x] = 3, ma anche f[y] = 3. Inaltre parole, x e y puntano allo stesso oggetto dopo lassegnazione y x.Un puntatore pu` o non fare riferimento ad alcun oggetto; in questo caso daremoad esso il valore speciale NIL.8. I parametri vengono passati a una procedura per valore: la procedura chiamatariceve la sua copia dei parametri e, se viene assegnato un valore a un para-metro, la modica non viene vista dalla procedura chiamante. Quando vienepassato un oggetto, viene copiato il puntatore ai dati che costituiscono log-getto, ma non vengono copiati i campi delloggetto. Per esempio, sex ` e unparametro di una procedura chiamata, lassegnazionex y allinterno dellaprocedura chiamata non` e visibile alla procedura chiamante. Lassegnazionef[x] 3, invece, ` e visibile.9. Gli operatori booleani and e or sonooperatoridicortocircuito. Questosignica che, quando valutiamo lespressione x and y, prima dobbiamo va-lutare x. Se x ` e FALSE, allora lintera espressione non pu` o essere TRUE, quindinon occorre valutare y. Se, invece, x ` e TRUE, dobbiamo valutare y per determi-nare il valore dellintera espressione. Analogamente, se abbiamo lespressionex or y, valutiamoy soltanto se x ` eFALSE. Gli operatori di cortocircuito ciconsentono di scrivere espressioni booleane come x ,=NIL and f[x] =ysenza preoccuparci di ci ` o che accade quando tentiamo di valutare f[x] quandox ` e NIL.Esercizi2.1-1Utilizzando la Figura 2.2 come modello, illustrate loperazione di INSERTION-SORT sullarray A = 31, 41, 59, 26, 41, 58).18 Capitolo 2 - Introduzione2.1-2Modicate la procedura INSERTION-SORT per disporre gli elementi in ordine noncrescente, anzich e non decrescente.2.1-3Considerate il seguente problema di ricerca:Input: una sequenza di n numeri A = a1, a2, . . . , an) e un valore v.Output: un indice i tale che v =A[i] o il valore speciale NIL se v non gura in A.Scrivere uno pseudocodice di ricerca lineare che esamina gli elementi della se-quenza alla ricerca di v. Utilizzando uninvariante di ciclo, dimostrate che il vo-stro algoritmo ` e corretto. Vericate che la vostra invariante di ciclo soddisfa le trepropriet` a richieste.2.1-4Considerate il problema di sommare due numeri interi binari di n-bit, memorizzatiin due array A e B di n elementi. La somma dei due interi deve essere memoriz-zata in forma binaria nellarrayCdi(n + 1) elementi. Denite formalmente ilproblema e scrivete lo pseudocodice per sommare i due interi.2.2 Analisi degli algoritmiAnalizzare un algoritmo signica prevedere le risorse che lalgoritmo richiede.Raramente sono di primaria importanza risorse come la memoria, la larghezza dibanda nelle comunicazioni o lhardware nei computer, mentre pi ` u frequentemente` e importante misurare il tempo di elaborazione. In generale, analizzando pi ` u algo-ritmi candidati a risolvere un problema, ` e facile identicare quello pi ` u efciente.Tale analisi potrebbe indicare pi ` u di un candidato, ma di solito in questo processovengono scartati diversi algoritmi inefcienti.Prima di analizzare un algoritmo, dobbiamo avere un modello della tecnologiadi implementazione che sar` a utilizzata, incluso un modello per le risorse di taletecnologia e dei loro costi. Nella maggior parte dei casi di questo libro, consi-dereremo come tecnologia di implementazione un generico modello di calcolo aun processore, che chiameremo modello random-access machine (RAM); inol-tre, i nostri algoritmi saranno implementati come programmi per computer. Nelmodello RAM, le istruzioni sono eseguite una dopo laltra, senza operazioni con-temporanee. Nei capitoli successivi, tuttavia, avremo modo di esaminare modelliper hardware digitale.A rigor di termini, dovremmo denire con precisione le istruzioni del modelloRAM e i loro costi. Purtroppo, tutto questo risulterebbe noioso e non giovereb-be molto a illustrare il processo di analisi e progettazione degli algoritmi. Eppuredobbiamo stare attenti a non abusare del modello RAM. Per esempio, che cosaaccadrebbe se un modello RAM avesse unistruzione di ordinamento? Potremmoordinare gli elementi con una sola istruzione. Tale modello non sarebbe realistico,in quanto i computer reali non hanno simili istruzioni. La nostra guida, dunque, ` ecome i computer reali sono progettati. Il modello RAM contiene istruzioni che sitrovano comunemente nei computer reali: istruzioni aritmetiche (addizione, sot-trazione, moltiplicazione, divisione, resto, oor, ceiling), istruzioni per spostare i2.2 Analisi degli algoritmi 19dati (load, store, copy) e istruzioni di controllo (salto condizionato e incondizio-nato, chiamata di subroutine e return). Ciascuna di queste istruzioni richiede unaquantit` a costante di tempo.I tipi di dati nel modello RAM sono integer (numeri interi) e oating point (nu-meri in virgola mobile). Sebbene di solito la precisione non sia problema in questolibro, tuttavia, in alcune applicazioni potrebbe essere un fattore cruciale. Inoltre,supporremo che ci sia un limite alla dimensione di ogni parola (word) di dati. Peresempio, quando operiamo con input di dimensionen, tipicamente, supponiamoche i numeri interi siano rappresentati dac lg n bit per una costantec 1. Noirichiediamoc 1 in modo che ogni parola possa contenere il valore din, con-sentendoci di indicizzare i singoli elementi di input, e imponiamo chec sia unacostante in modo che la dimensione della parola non cresca in modo arbitrario(se questadimensionepotessecrescerearbitrariamente, potremmomemorizza-re enormi quantit` a di dati in una parola e operare con essa sempre in un tempocostante chiaramente uno scenario irreale).I computer reali contengono istruzioni non elencate in precedenza; tali istruzio-ni rappresentano unarea grigia nel modello RAM. Per esempio, lelevamento apotenza ` e unistruzione a tempo costante? Nel caso generale, no; occorrono varieistruzioni per calcolare xyquando x e y sono numeri reali. In casi limitati, invece,lelevamento a potenza` e unoperazione a tempo costante. Molti computer han-no unistruzione shift left (scorrimento a sinistra), che fa scorrere in un tempocostante i bit di un numero intero di k posizioni a sinistra. In molti computer, loscorrimento dei bit di un intero di una posizione a sinistra equivale a moltiplicareper 2. Lo scorrimento dei bit di k posizioni a sinistra equivale a moltiplicare per2k. Di conseguenza, tali computer possono calcolare 2kin unistruzione a tempocostante facendo scorrere lintero 1 di k posizioni a sinistra, purch e k non superiil numero di bit di una parola del computer. Cercheremo di evitare tali aree grigenel modello RAM, tuttavia considereremo il calcolo di 2kcome unoperazione atempo costante quando k ` e un intero positivo sufcientemente piccolo.Nel modello RAM non tenteremo di modellare la struttura gerarchica della me-moria che ` e comune nei computer attuali, ovvero non modelleremo la memoriacacheovirtuale, chemoltospessovieneimplementataconlapaginazionesurichiesta (demand paging). Vari modelli computazionali tentano di tenere contodegli effetti della gerarchia della memoria, che a volte sono signicativi nei pro-grammi o nelle macchine reali. In pochi problemi di questo libro esamineremogli effetti della gerarchia della memoria, ma nella maggior parte dei casi lanalisiignorer` a tali effetti. I modelli che includono la struttura gerarchica della memo-ria sono un po pi ` u complessi del modello RAM, quindi` e difcile operare conessi. Inoltre, lanalisi del modello RAM di solito` e un eccellente strumento perprevedere le prestazioni delle macchine reali.Lanalisi di un algoritmo nel modello RAM pu` o risultare complessa anche selalgoritmo` e semplice. Gli strumenti matematici richiesti possono includerelateoria delle probabilit` a, la topologia combinatoria, destrezza algebrica e capacit` adi identicare i termini pi ` u signicativi in una formula. Poich e il comportamentodi un algoritmo pu` o essere diverso per ogni possibile input, occorrono strumentiper sintetizzare tale comportamento in formule semplici e facili da capire.Anche se di solito selezioniamo soltanto un modello di macchina per analizzareun determinato algoritmo, avremo a disposizione varie scelte per decidere comeesprimere la nostra analisi. Preferiremmo un metodo che sia semplice da scrive-20 Capitolo 2 - Introduzionere e manipolare, mostri le caratteristiche importanti delle risorse richieste da unalgoritmo ed elimini i dettagli pi ` u noiosi.Analisi di insertion sortIl tempo richiesto dalla procedura INSERTION-SORT dipende dallinput: occorrepi ` u tempo per ordinare un migliaio di numeri che tre numeri. Inoltre, INSERTION-SORT pu` o richiedere quantit` a di tempo differenti per ordinare due sequenze diinput della stessa dimensione a seconda di come gli elementi siano gi` a ordinati.In generale, il tempo richiesto da un algoritmo cresce con la dimensione dellin-put, quindi ` e tradizione descrivere il tempo di esecuzione di un programma comeunafunzionedelladimensionedel suoinput. Per farlo, dobbiamodenirepi ` ucorrettamente i termini tempo di esecuzione e dimensione dellinput.La denizione migliore della dimensione dellinput dipende dal problema chesi sta studiando. Per la maggior parte dei problemi, come lordinamento o il cal-colo delle trasformate discrete di Fourier, la misura pi ` u naturale` e ilnumerodielementi dellinput per esempio, la dimensione n dellarray per lordinamento.Per molti altri problemi, come la moltiplicazione di due interi, la misura miglio-re della dimensione dellinput ` e il numero totale di bit richiesti per rappresentarelinput nella normale notazione binaria. A volte, ` e pi ` u appropriato descrivere ladimensione dellinput con due numeri, anzich e con un uno. Per esempio, se lin-put di un algoritmo ` e un grafo, la dimensione dellinput pu` o essere descritta dalnumero di vertici e dal numero di lati del grafo. Per ogni problema analizzatodovremo indicare quale misura della dimensione di input sar` a adottata.Il tempo di esecuzione di un algoritmo per un particolare input ` e il numero dioperazioni primitive che vengono eseguite o passi. Conviene denire il concet-to di passo nel modo pi ` u indipendente possibile dal tipo di macchina. Per il mo-mento, adottiamo il seguente quadro di ipotesi. Per eseguire una riga del nostropseudocodice occorre una quantit` a costante di tempo. Una riga pu` o richiedere unaquantit` a di tempo diversa da unaltra riga, tuttavia supporremo che ogni esecuzio-ne delli-esima riga richieda un tempo ci, dove ci ` e una costante. Questa ipotesi ` econforme al modello RAM e rispecchia anche il modo in cui lo pseudocodice pu` oessere implementato in molti computer reali.4Nella discussione che segue, la nostra espressione del tempo di esecuzione perINSERTION-SORT si evolver` a da una formula grezza che usa tutti i costi ci delleistruzionia una notazionemolto pi ` u semplice, concisae facilmentemanipola-bile. Questa notazionesemplicatarender` aanchepi ` u faciledeterminarese unalgoritmo ` e pi ` u efciente di un altro.Presentiamo, innanzi tutto, la procedura INSERTION-SORT con il tempo impie-gato da ogni istruzione (costo) e il numero di volte che vengono eseguite le singoleistruzioni. Per ogni j= 2, 3, . . . , n, dove n = lunghezza[A], indichiamo con tj il4Ci sono alcuni particolari da chiarire. I passi computazionali che specichiamo in italiano spessosono varianti di una procedura che richiede pi` u di una quantit` a di tempo costante. Per esempio,pi` u avanti in questo libro potremmo dire di ordinare i punti in funzione della coordinata x; comevedremo, questa operazione richiede pi` u di una quantit` a di tempo costante. Notiamo inoltre cheunistruzione che chiama una subroutine impiega un tempo costante, sebbene la subroutine, unavolta chiamata, possa impiegare di pi` u. In altre parole, separiamo il processo della chiamata dellasubroutine passare i parametri alla subroutine, ecc. dal processo di esecuzione della subroutine.2.2 Analisi degli algoritmi 21numero di volte che il test del ciclo while nella riga 5 viene eseguito per quel va-lore di j. Quando un ciclo for o while termina nel modo consueto (come stabilitodal test allinizio del ciclo), il test viene eseguito una volta di pi ` u del corpo delciclo. Noi supponiamo che i commenti non siano istruzioni eseguibili e, quindi, illoro costo ` e nullo.INSERTION-SORT(A) costo numero di volte1 for j 2 to lunghezza[A] c1n2 do chiave A[j] c2n 13 Inserisce A[j] nella sequenzaordinata A[1 . . j 1]. 0 n 14 i j 1 c4n 15 while i > 0 and A[i] > chiave c5

nj=2tj6 do A[i + 1] A[i] c6

nj=2(tj 1)7 i i 1 c7

nj=2(tj 1)8 A[i + 1] chiave c8n 1Il tempo di esecuzione dellalgoritmo ` e la somma dei tempi di esecuzione per ogniistruzione eseguita; unistruzioneche richiedecipassi e viene eseguitan voltecontribuir` a concin al tempo di esecuzione totale.5Pe calcolareT(n), il tempodi esecuzione di INSERTION-SORT, sommiamo i prodotti delle colonnecosto enumero di volte, ottenendoT(n) = c1n +c2(n 1) +c4(n 1) +c5n

j=2tj +c6n

j=2(tj 1)+c7n

j=2(tj 1) +c8(n 1)Anche per pi ` u input della stessa dimensione, il tempo di esecuzione di un algori-tmo pu` o dipendere da quale input di quella dimensione viene scelto. Per esempio,in INSERTION-SORT il caso migliore si verica se larray ` e gi` a ordinato. Per ognij= 2, 3, . . . , n, troviamo che A[i] chiave nella riga 5, quando i ha il suo valoreiniziale j 1. Quindi tj= 1 per j= 2, 3, . . . , n e il tempo di esecuzione nel casomigliore ` eT(n) = c1n +c2(n 1) +c4(n 1) +c5(n 1) +c8(n 1)= (c1 +c2 +c4 +c5 +c8)n (c2 +c4 +c5 +c8)Questo tempo di esecuzione pu` o essere espresso come an +b, con le costanti a eb che dipendono dai costi delle istruzioni ci; quindi ` e una funzione lineare di n.Selarray` eordinatoinsensoinversocio` einordinedecrescenteallo-rasivericailcasopeggiore. Dobbiamoconfrontareogni elementoA[j] conogni elemento dellintero sottoarray ordinatoA[1 . . j 1], e quinditj=j perj= 2, 3, . . . , n.5Questa caratteristica non ` e necessariamente valida per una risorsa come la memoria. Unistruzioneche fa riferimento am parole di memoria e viene eseguitan volte non necessariamente consumamn parole di memoria in totale.22 Capitolo 2 - IntroduzionePoich en

j=2j=n(n + 1)21en

j=2(j 1) =n(n 1)2(consultate lAppendice A per sapere come risolvere queste sommatorie), il tempodi esecuzione di INSERTION-SORT nel caso peggiore ` eT(n) = c1n +c2(n 1) +c4(n 1) +c5_n(n + 1)21_+c6_n(n 1)2_+c7_n(n 1)2_+c8(n 1)=_c52+c62+c72_n2+_c1 +c2 +c4 +c52 c62 c72+c8_n(c2 +c4 +c5 +c8)Questo tempo di esecuzione pu` o essere espresso come an2+bn+c, con le costantia, b e c che, anche in questo caso, dipendono dei costi delle istruzionici; quindi` e una funzione quadratica di n. Tipicamente, come per insertion sort, il tempo diesecuzione di un algoritmo ` e sso per un dato input, sebbene nei successivi ca-pitoli vedremo alcuni interessanti algoritmi randomizzati il cui comportamentopu` o variare anche con un input sso.Analisi del caso peggiore e del caso medioNellanalisi di insertion sort, abbiamo esaminato sia il caso migliore, in cui larraydi input era gi` a ordinato, sia il caso peggiore, in cui larray di input era ordinatoalla rovescia. Nel seguito del libro, di solito, sono descritte le tecniche per de-terminare soltanto il tempo di esecuzione nel caso peggiore, ovvero il tempo diesecuzione pi ` u lungo per qualsiasi input di dimensione n. Ci sono tre ragioni allabase di questo orientamento.Il tempo di esecuzionenel caso peggiore di un algoritmo` e un limite supe-riore al tempo di esecuzione per qualsiasi input. Conoscendo questo tempo,abbiamo la garanzia che lalgoritmo non potr` a impiegare di pi ` u. Non abbia-mo bisogno di fare altre ipotesi sul tempo di esecuzione e sperare che questotempo non venga mai superato.Per alcuni algoritmi, il caso peggiore si verica molto spesso. Per esempio,nella ricerca di una particolare informazione in un database, il caso peggioredellalgoritmo di ricerca si verica ogni volta che linformazione non ` e pre-sente nel database. In alcune applicazioni di ricerca potrebbe essere frequentericercare informazioni assenti.Il caso medio spesso` e brutto quasi quanto quello peggiore. Supponete diavere scelto a caso n numeri e di applicare lalgoritmo insertion sort. Quantotempo impiegher` a lalgoritmo per determinare dove inserire lelementoA[j]nel sottoarray A[1 . . j 1]? In media, met` a degli elementi di A[1 . . j 1] sonopi ` u piccoli di A[j], mentre gli altri elementi sono pi ` u grandi. In media, quin-di, verichiamo met` a del sottoarrayA[1 . . j 1], pertantotjvale circaj/2.2.2 Analisi degli algoritmi 23Il tempo di esecuzione nel caso medio risulta dunque una funzione quadrati-ca della dimensione dellinput, proprio come il tempo di esecuzione nel casopeggiore.In alcuni casi particolari saremo interessati a determinare il tempo di esecuzionenelcaso medio di un algoritmo, detto anche tempo di esecuzioneprevisto. NelCapitolo 5 vedremo la tecnica dellanalisiprobabilistica che permette di deter-minare il tempo di esecuzione previsto. Una difcolt` a dellanalisi del caso medio,tuttavia, ` e che non` e sempre evidente ci ` o che costituisce un input medio perun particolareproblema. Spesso supporremoche tutti gli input di una data di-mensione abbiano la stessa probabilit` a. In pratica questa ipotesi potrebbe essereinvalidata, tuttavia in alcuni casi possiamo utilizzare un algoritmo randomizzato,che effettua delle scelte casuali, per consentirci di svolgere lanalisi probabilistica.Tasso di crescitaIn precedenza abbiamo fatto alcune ipotesi per semplicare lanalisi della proce-dura INSERTION-SORT. Innanzi tutto, abbiamo ignorato il costo effettivo di ogniistruzione, utilizzando le costantici per rappresentare questi costi. Poi, abbiamoosservato che anche queste costanti ci danno pi ` u dettagli del necessario: il tem-po di esecuzione nel caso peggiore ` ean2+ bn + c, con le costantia, b ec chedipendono dai costi delle istruzionici. Quindi, abbiamo ignorato non soltanto icosti effettivi delle istruzioni, ma anche i costi astratti ci. Adesso faremo unaltraastrazione esemplicativa.`E il tasso o livello di crescita del tempo di esecuzioneche effettivamente ci interessa. Di conseguenza, consideriamo soltanto il termineiniziale di una formula (per esempio an2), in quanto i termini di ordine inferioresono relativamente insignicanti per grandi valori di n. Ignoriamo anche il coef-ciente costante del termine iniziale, in quanto i fattori costanti sono meno signi-cativi del tasso di crescita nel determinare lefcienza computazionale per grandiinput. Quindi, scriviamo che insertion sort, per esempio, ha un tempo di esecu-zione nel caso peggiore pari a(n2) (che si pronuncia teta din al quadrato).In questo capitolo adotteremo informalmente la notazione , che sar` a denita pi ` uprecisamente nel Capitolo 3. Di solito, un algoritmo ` e considerato pi ` u efcientedi un altro se il suo tempo di esecuzione nel caso peggiore ha un tasso di cresci-ta inferiore. A causa dei fattori costanti e dei termini di ordine inferiore, questavalutazione potrebbe essere errata per piccoli input. Tuttavia, per input sufcien-temente grandi, un algoritmo (n2), per esempio, sar` a eseguito pi ` u velocementenel caso peggiore di un algoritmo (n3).Esercizi2.2-1Esprimete la funzione n3/1000 100n2100n + 3 nella notazione .2.2-2Supponete di ordinaren numeri memorizzati nellarrayA trovando prima il pi ` upiccolo elemento di A e scambiandolo con lelemento in A[1]; poi, trovate il se-condo elemento pi ` u piccolo diA e scambiatelo conA[2]. Continuate in questomodo per i primi n1 elementi di A. Scrivete lo pseudocodice per questo algori-tmo, che ` e noto come selection sort (ordinamento per selezione). Quale invariantedi ciclo conserva questo algoritmo? Perch e basta eseguirlo soltanto per i primin 1 elementi, anzich e per tutti glin elementi? Esprimete nella notazione itempi di esecuzione nei casi migliore e peggiore dellalgoritmo selection sort.24 Capitolo 2 - Introduzione2.2-3Considerate di nuovo la ricerca lineare (Esercizio 2.1-3). Quanti elementi dellasequenza di input devono essere esaminati in media, supponendo che lelementocercato ha la stessa probabilit` a di essere un elemento qualsiasi dellarray? Quantielementi nel caso peggiore? Quali sono i tempi di esecuzione nei casi migliore epeggiore della ricerca lineare nella notazione . Spiegate le vostre risposte.2.2-4Come possiamomodicare quasi tutti gli algoritmi in modo da avere un buontempo di esecuzione nel caso migliore?2.3 Progettare gli algoritmiCi sono varie tecniche per progettare gli algoritmi. Insertion sort usa un approccioincrementale: dopo avere ordinatoil sottoarrayA[1 . . j 1], inseriamo il sin-golo elementoA[j] nella posizione appropriata, ottenendo il sottoarray ordinatoA[1 . . j]. Nel prossimo paragrafo esamineremo un metodo di progettazione alter-nativo, noto come divide et impera. Utilizzeremo questo metodo per progettareun algoritmo di ordinamento il cui tempo di esecuzione nel caso peggiore ` e moltopi ` u piccolo di quello di insertion sort. Un vantaggio degli algoritmi divide et impe-ra ` e che i loro tempi di esecuzione, spesso, possono essere facilmente determinatiapplicando le tecniche che saranno presentate nel Capitolo 4.2.3.1 Il metodo divide et imperaMolti utili algoritmi sonoricorsivi nella struttura: per risolvere un determinatoproblema, questi algoritmi chiamano s e stessi in modo ricorsivo, una o pi ` u volte,per trattare sottoproblemi strettamente correlati. Tipicamente, gli algoritmi ricor-sivi adottano un approccio divide et impera: suddividono il problema in vari sot-toproblemi, che sono simili al problema originale, ma di dimensioni pi ` u piccole,risolvonoi sottoproblemiin modo ricorsivo e, poi, combinano le soluzionipercreare una soluzione del problema originale.Il paradigma divide et impera prevede tre passi a ogni livello di ricorsione:Divide: il problema viene diviso in un certo numero di sottoproblemi.Impera: i sottoproblemi vengonorisoltiinmodoricorsivo. Tuttavia, se i sot-toproblemi hannounadimensionesufcientementepiccola, possonoessererisolti in maniera semplice.Combina: lesoluzioni dei sottoproblemi vengonocombinatepergenerarelasoluzione del problema originale.Lalgoritmo merge sort ` e conforme al paradigma divide et impera; intuitivamente,opera nel modo seguente.Divide: divide la sequenza degli n elementi da ordinare in due sottosequenze din/2 elementi ciascuna.Impera: ordina le due sottosequenze in modo ricorsivo utilizzando lalgoritmomerge sort.Combina: fonde le due sottosequenze ordinate per generare la sequenza ordinata.2.3 Progettare gli algoritmi 25La ricorsione tocca il fondo quando la sequenza da ordinare ha lunghezza 1, nelqual caso non c` e pi ` u nulla da fare, in quanto ogni sequenza di lunghezza 1 ` e gi` aordinata.Loperazione chiave dellalgoritmo merge sort ` e la fusione di due sottosequenzeordinate nel passo combina. Per effettuare la fusione, utilizziamo una proceduraausiliaria MERGE(A, p, q, r), doveA ` e un array ep, q er sono indici di nume-razione degli elementi dellarray tali chep qR[j], allora le righe 1617 svolgono lazione appropriata perconservare linvariante di ciclo.Conclusione: alla ne del ciclo, k= r +1. Per linvariante di ciclo, il sottoarrayA[p . . k 1], che ` e A[p . . r], contiene k p = r p +1 elementi ordinati chesono i pi ` u piccoli di L[1 . . n1+1] e R[1 . . n2+1]. Gli array L e R contengonon1 +n2 + 2 = r p + 3 elementi. Tutti gli elementi, tranne i due pi ` u grandi,sono stati copiati in A; questi due elementi sono le sentinelle.Per vericare che la proceduraMERGEviene eseguita nel tempo(n), conn = r p + 1, notate che ciascuna delle righe 13 e 811 impiega un tempo co-stante, i cicli for (righe 47) impiegano un tempo (n1 +n2) = (n),6e ci sonon iterazioni del ciclo for (righe 1217), ciascuna delle quali impiega un tempocostante. Adesso possiamo utilizzare la procedura MERGE come subroutine nel-lalgoritmo merge sort. La procedura MERGE-SORT(A, p, r) ordina gli elementinel sottoarray A[p . . r]. Se p r, il sottoarray ha al massimo un elemento e, quin-di, ` e gi` a ordinato; altrimenti, il passo divide calcola semplicemente un indice q6Il Capitolo 3 spiega come interpretare formalmente le equazioni che contengono la notazione .28 Capitolo 2 - Introduzione5 2 4 7 1 3 2 62 5 4 7 1 3 2 62 4 5 7 1 2 3 61 2 2 3 4 5 6 7fusionefusionefusionesequenza ordinatasequenza inizialefusione fusione fusione fusioneche separaA[p . . r] in due sottoarray: A[p . . q], che contiene n/2| elementi, eA[q + 1 . . r], che contiene n/2| elementi.7MERGE-SORT(A, p, r)1 if p < r2 then q (p +r)/2|3 MERGE-SORT(A, p, q)4 MERGE-SORT(A, q + 1, r)5 MERGE(A, p, q, r)Per ordinare lintera sequenza A = A[1], A[2], . . . , A[n]), effettuiamo la chiama-ta iniziale MERGE-SORT(A, 1, length[A]), dove ancora una volta length[A] = n.La Figura2.4 illustrail funzionamentodellaproceduradalbassoversolalto,quando n ` e una potenza di 2. Lalgoritmo consiste nel fondere coppie di sequen-ze di un elemento per formare sequenze ordinate di lunghezza 2, fondere coppiedi sequenze di lunghezza 2 per formare sequenze ordinate di lunghezza 4 e cos`via, nch e non si fonderanno due sequenze di lunghezza n/2 per formare lultimasequenza ordinata di lunghezza n.Figura 2.4Funzionamento di mergesort con larrayA = 5, 2, 4, 7, 1, 3, 2, 6).Le lunghezze dellesequenze ordinate dafondere aumentano via viache lalgoritmo procededal basso verso lalto.2.3.2 Analisi degli algoritmi divide et imperaQuando un algoritmo contiene una chiamata ricorsiva a s e stesso, il suo tempo diesecuzione spesso pu` o essere descritto con una equazione di ricorrenza o ricor-renza, che esprime il tempo di esecuzione totale di un problema di dimensione nin funzione del tempo di esecuzione per input pi ` u piccoli. Poi ` e possibile utilizzaregli strumenti matematici per risolvere lequazione di ricorrenza e stabilire i limitidelle prestazioni dellalgoritmo.7Lespressione x indica il pi` u piccolo numero intero che ` e maggiore o uguale a x; ]x_ indica ilpi` u grande numero intero che ` e minore o uguale a x. Queste notazioni sono denite nel Capitolo 3.Il sistema pi` u semplice per vericare che impostandoqa ](p +r)/2_ si ottengono i sottoarrayA[p . . q] e A[q + 1 . . r], rispettivamente, di dimensione n/2 e ]n/2_, consiste nellesaminare iquattro casi che si presentano a seconda se p e r siano pari o dispari.2.3 Progettare gli algoritmi 29Una ricorrenza per il tempo di esecuzione di un algoritmo divide et impera sibasa sui tre passi del paradigma di base. Come in precedenza, supponiamo cheT(n) sia il tempo di esecuzione di un problema di dimensionen. Se la dimen-sione del problema` e sufcientemente piccola, per esempion c per qualchecostante c, la soluzione semplice richiede un tempo costante, che indichiamo con(1). Supponiamo che la nostra suddivisione del problema generi a sottoproblemie che la dimensione di ciascun sottoproblema sia 1/b la dimensione del problemaoriginale (per merge sort, i valori dia eb sono entrambi pari a2, ma vedremovari algoritmi divide et impera in cui a ,= b). Se impieghiamo un tempo D(n) perdividere il problema in sottoproblemi e un tempo C(n) per combinare le soluzionidei sottoproblemi nella soluzione del problema originale, otteniamo la ricorrenzaT(n) =_(1) se n caT(n/b) +D(n) +C(n) negli altri casiNel Capitolo 4 vedremo come risolvere le ricorrenze comuni di questa forma.Analisi di merge sortSebbene lo pseudocodice di MERGE-SORT funzioni correttamente quando il nu-mero di elementi non ` e pari, la nostra analisi basata sulla ricorrenza si semplicase supponiamo che la dimensione del problema originale sia una potenza di2.Ognipassodividegeneraduesottosequenzedidimensioneesattamenteparian/2. Nel Capitolo 4, vedremo che questa ipotesi non inuisce sul tasso di crescitadella soluzione della ricorrenza.Per stabilire la ricorrenza perT(n), il tempo di esecuzione nel caso peggioredi merge sort con n numeri, possiamo fare il seguente ragionamento. Lalgoritmomerge sort applicato a un solo elemento impiega un tempo costante. Se abbiamon > 1 elementi, suddividiamo il tempo di esecuzione nel modo seguente.Divide: questo passo calcola semplicemente il centro del sottoarray. Ci ` o richiedeun tempo costante, quindi D(n) = (1).Impera: risolviamo in modo ricorsivo i due sottoproblemi, ciascuno di dimen-sione n/2; ci ` o contribuisce con 2T(n/2) al tempo di esecuzione.Combina: abbiamo gi` a notato che la procedura MERGE con un sottoarray dinelementi richiede un tempo (n), quindi C(n) = (n).Quando sommiamo le funzioniD(n) eC(n) per lanalisi di merge sort, stiamosommando una funzione che ` e (1) e una funzione che ` e (n). Questa somma` eunafunzionelinearedi n, cio` e(n). Sommandolaaltermine2T(n/2)delpasso impera, si ottiene la ricorrenza per il tempo di esecuzione T(n) nel casopeggiore di merge sort:T(n) =_(1) se n = 12T(n/2) + (n) se n > 1(2.1)Nel Capitolo4 vedremoil teorema dellesperto, che possiamoutilizzareperdimostrare che T(n) ` e (nlg n), dove lg n sta per log2n. Poich e la funzione lo-garitmica cresce pi ` u lentamente di qualsiasi funzione lineare, per input sufcien-temente grandi, lalgoritmo merge sort, con il suo tempo di esecuzione (nlg n),supera le prestazioni di insertion sort, il cui tempo di esecuzione ` e (n2), nel casopeggiore. Non occorre il teorema dellesperto per capire perch e la soluzione dellaricorrenza (2.1) ` e T(n) = (nlg n).30 Capitolo 2 - IntroduzioneRiscriviamo la ricorrenza (2.1) cos`T(n) =_c se n = 12T(n/2) +cn se n > 1(2.2)La costante c rappresenta sia il tempo richiesto per risolvere i problemi di dimen-sione 1 sia il tempo per elemento dellarray dei passi divide e combina.8La Figura 2.5 mostra come possiamo risolvere la ricorrenza (2.2). Per comodit` a,supponiamo chen sia una potenza esatta di2. La parte (a) della gura mostraT(n), che nella parte (b) ` e stato espanso in un albero equivalente che rappresentala ricorrenza. Il terminecn` e la radice(il costoal primo livellodi ricorsione)e i due sottoalberi dellaradicesonole duericorrenzepi ` u piccoleT(n/2). Laparte (c) mostra questo processo un passo pi ` u avanti con lespansione di T(n/2).Il costo per ciascuno dei due sottonodi al secondo livello di ricorsione` ecn/2.Continuiamo a espandere i nodi nellalbero suddividendolo nelle sue componenticome stabilisce la ricorrenza, nch e le dimensioni dei problemi si riducono a1,ciascuno con un costo c. La parte (d) mostra lalbero risultante.Sommiamo i costi per ogni livello dellalbero. Il primo livello ha un costo totalecn, il secondo livello ha un costo totale c(n/2) +c(n/2) = cn, il terzo livello haun costo totale c(n/4) +c(n/4) +c(n/4) +c(n/4) = cn e cos` via. In generale,il livello i sotto il primo ha 2inodi, ciascuno dei quali ha un costo c(n/2i), quindili-esimo livello sotto il primo ha un costo totale2ic(n/2i)=cn. A livello pi ` ubasso ci sono n nodi, ciascuno con un costo c, per un costo totale cn.Il numero totale di livelli dellalbero di ricorsione nella Figura 2.5 ` e lg n + 1.Questo pu` o essere facilmente dimostrato con un ragionamento induttivo informa-le. Il caso base si verica quando n = 1, nel qual caso c` e un solo livello. Poich elg 1 = 0, abbiamo che lg n + 1 fornisce il numero corretto di livelli. Adesso sup-poniamo, come ipotesi induttiva, che il numero di livelli di un albero di ricorsioneper 2inodi sia lg 2i+ 1 = i + 1 (poich e per qualsiasi valore di i, si ha lg 2i= i).Poich e stiamo supponendo che la dimensione dellinput originale sia una potenzadi2, la successiva dimensione da considerare` e2i+1. Un albero con2i+1nodiha un livello in pi ` u di un albero con2inodi; quindi il numero totale di livelli ` e(i + 1) + 1 = lg 2i+1+ 1.Per calcolare il costo totale rappresentato dalla ricorrenza (2.2), basta sommarei costi di tutti i livelli. Ci sono lg n + 1 livelli, ciascuno di costo cn, per un costototale di cn(lg n+1) = cnlg n+cn. Ignorando il termine di ordine inferiore e lacostante c, si ottiene il risultato desiderato (nlg n).Esercizi2.3-1UtilizzandolaFigura2.4comemodello, illustrateloperazionedi mergesortsullarray A = 3, 41, 52, 26, 38, 57, 9, 49).8`E improbabile che la stessa costante rappresenti esattamente sia il tempo richiesto per risolvere iproblemi di dimensione 1 sia il tempo per elemento dellarray dei passi divide e combina. Possiamoaggirare questo problema, assegnando a c il valore pi` u grande di questi tempi e accettando che lanostra ricorrenza impone un limite superiore al tempo di esecuzione oppure assegnando a c il valorepi` u piccolo di questi tempi e accettando che la nostra ricorrenza impone un limite inferiore al tempodi esecuzione. Entrambi i limiti saranno nellordine dinlg n e, presi insieme, danno un tempo diesecuzione (nlg n).2.3 Progettare gli algoritmi 312.3-2Modicate la proceduraMERGEin modo da non utilizzarele sentinelle;inter-rompete il processo quando tutti gli elementi di uno dei due array L e R sono staticopiati in A; poi copiate il resto dellaltro array in A.Figura 2.5La costruzione di unalbero di ricorsioneper la ricorrenzaT(n) = 2T(n/2) +cn.La parte (a) mostra T(n),che viene progressivamenteespanso in (b)(d) performare lalbero diricorsione. Lalberocompletamente espansonella parte (d) ha lg n + 1livelli (cio` e ha unaltezzalg n, come indicato) e ognilivello ha un costo cn. Diconseguenza, il costo totale` e cnlg n +cn, che ` e(nlg n).2.3-3Applicate linduzione matematica per dimostrare che, se n ` e una potenza esatta di2, allora T(n) = nlg n ` e la soluzione della ricorrenzaT(n) =_2 se n = 22T(n/2) +n se n = 2k, per k > 12.3-4Insertion sort pu` o essere espresso come una procedura ricorsiva nel modo seguen-te: per ordinare A[1 . . n], si ordina in modo ricorsivo A[1 . . n 1] e poi si inseri-sce A[n] nellarray ordinato A[1 . . n 1]. Scrivete una ricorrenza per il tempo diesecuzione di questa versione ricorsiva di insertion sort.32 Capitolo 2 - Introduzione2.3-5Riprendendo il problema della ricerca (Esercizio 2.1-3), notiamo che, se la se-quenzaA ` e ordinata, possiamo confrontare il punto centrale della sequenza conv ed escludere met` a sequenza da ulteriori considerazioni. La ricerca binaria ` e unalgoritmo che ripete questa procedura, dimezzando ogni volta la dimensione dellaporzione restante della sequenza. Scrivete uno pseudocodice, iterativo o ricorsivo,per la ricerca binaria. Dimostrate che il tempo di esecuzione nel caso peggioredella ricerca binaria ` e (lg n).2.3-6Il ciclowhile, righe57, dellaproceduraINSERTION-SORTnel Paragrafo2.1usa la ricerca lineare per esplorare (a ritroso) il sottoarray ordinato A[1 . . j 1].`E possibile usare la ricerca binaria (Esercizio 2.3-5) per migliorare il tempo diesecuzione complessivo nel caso peggiore di insertion sort no a (nlg n)?2.3-7 Descrivete un algoritmo con tempo (nlg n) che, dato un insieme S di n numeriinteri e un altro intero x, determini se esistono due elementi in S la cui somma ` eesattamente x.2.4 Problemi2-1 Insertion sort su piccoli arrays in merge sortSebbene merge sort venga eseguito nel tempo(nlg n) nel caso peggiore e in-sertion sort venga eseguito nel tempo(n2) nel caso peggiore, i fattori costantidi insertion sort lo rendono pi ` u veloce per piccoli valori din. Quindi, ha sensousare insertionsort allinternodi merge sort quandoi sottoproblemidiventanosufcientemente piccoli. Considerate una versione modicata di merge sort in cuin/k sottoliste di lunghezzak siano ordinate utilizzando insertion sort e poi fusemediante il meccanismo standard di merge sort; k ` e un valore da determinare.a. Dimostrarechelen/ksottoliste, ciascunadi lunghezzak, possonoessereordinate da insertion sort nel tempo (nk) nel caso peggiore.b. Dimostrare che le sottoliste possono essere fuse nel tempo (nlg(n/k)) nelcaso peggiore.c. Dato che lalgoritmo modicato viene eseguito nel tempo (nk +nlg(n/k))nel caso peggiore, qual ` e il massimo valore asintotico di k (notazione ) comefunzione di n per cui lalgoritmo modicato ha lo stesso tempo di esecuzioneasintotico del meccanismo standard di merge sort?d. In pratica, come dovrebbe essere scelto il valore di k?2-2 Correttezza di bubblesortBubblesort ` e un noto algoritmo di ordinamento; opera scambiando ripetutamentegli elementi adiacenti che non sono ordinati.BUBBLESORT(A)1 for i 1 to lunghezza[A]2 do for j lunghezza[A] downto i + 13 do if A[j] < A[j 1]4 then scambia A[j] A[j 1]2.4 Problemi 33a. Indichiamo con A

loutput di BUBBLESORT(A). Per dimostrare che laprocedura BUBBLESORT ` e corretta, bisogna vericare che termina e cheA

[1] A

[2] A

[n] (2.3)doven =lunghezza[A]. ChealtrobisognavericareperdimostrarecheBUBBLESORT ordina effettivamente gli elementi?I prossimi due punti dimostrano la disuguaglianza (2.3).b. Denite con precisione uninvariante di ciclo per il ciclo for, righe 24, e di-mostrate che tale invariante ` e vera. La vostra dimostrazione dovrebbe usare lastruttura della verica delle invarianti di ciclo presentata in questo capitolo.c. Utilizzandola condizionedi conclusionedellinvariantedi ciclo dimostratanel punto (b), denite uninvariantedi ciclo per il ciclo for, righe 14, chevi consentir` a di dimostrare la disuguaglianza(2.3). La vostra dimostrazionedovrebbe usare la struttura della verica delle invarianti di ciclo presentata inquesto capitolo.d. Qual ` e il tempo di esecuzione nel caso peggiore di bubblesort? Confrontatelocon il tempo di esecuzione di insertion sort.2-3 Correttezza della regola di HornerIl seguente frammento di codice implementa la regola di Horner per il calcolo diun polinomioP(x) =n

k=0akxk= a0 +x(a1 +x(a2 + +x(an1 +xan) ))dati i coefcienti a0, a1, . . . , an e un valore di x:1 y 02 i n3 while i 04 do y ai +xy5 i i 1a. Qual ` e il tempo di esecuzione asintotico di questo frammento di codice per laregola di Horner?b. Scrivete uno pseudocodice per implementare un semplice algoritmo che cal-cola i termini del polinomio da zero. Qual ` e il tempo di esecuzione di questoalgoritmo? Confrontatelo con la regola di Horner?c. Dimostratechelaseguentedenizione` euninvariantedicicloperilciclowhile, righe 3 5:Allinizio di ogni iterazione del ciclo while, righe 35,y=n(i+1)

k=0ak+i+1xk.34 Capitolo 2 - IntroduzioneLa vostra dimostrazione dovrebbe usare la struttura della verica delle inva-rianti di ciclo presentata in questo capitolo e dovrebbe vericare che, alla ne,y= nk=0akxk.d. Concludete dimostrando che il frammento di codice dato calcola correttamenteun polinomio caratterizzato dai coefcienti a0, a1, . . . , an.2-4 InversioniSia A[1 . . n] un array di n numeri distinti. Se i < j e A[i] > A[j], allora la coppia(i, j) ` e detta inversione di A.a. Elencate le cinque inversioni dellarray 2, 3, 8, 6, 1).b. Quale array con elementi estratti dallinsieme 1, 2, . . . , n ha pi ` u inversioni?Quante inversioni ha?c. Qual ` e la relazione fra il tempo di esecuzione di insertion sort e il numero diinversioni nellarray di input? Spiegate la vostra risposta.d. Create un algoritmo che determina il numero di inversioni in una permutazionedi n elementi nel tempo (nlg n) nel caso peggiore (suggerimento: modicatemerge sort).NoteNel 1968 Knuth pubblic` o il primo di tre volumi con il titolo generale The Art ofComputer Programming [182, 183, 185]. Il primo volume diede lavvio allo stu-dio moderno degli algoritmi per calcolatori, con particolare enfasi sullanalisi deitempi di esecuzione; lopera completa resta un importante riferimento per moltiargomenti trattati nel nostro libro. Secondo Knuth, la parola algoritmo deriva daal-Khow arizm, un matematico persiano del nono secolo.Aho, Hopcroft e Ullman [5] sostennero lanalisi asintotica degli algoritmi co-meunostrumentoperconfrontareprestazioni relative. Diffuseroinoltrelusodelle relazioni di ricorrenza per descrivere i tempi di esecuzione degli algoritmiricorsivi.Knuth [185] ` e autore di un trattato enciclopedico su molti algoritmi di ordina-mento. Il confronto di questi algoritmi (pagina 381) include lanalisi del conteggioesatto dei passi, come quella che abbiamo fatto in questo capitolo per insertionsort. La discussione di Knuth sullalgoritmo insertion sort include numerose va-rianti dellalgoritmo. La pi ` u importante di queste ` e Shells sort, introdotta da D. L.Shell, che applica insertion sort a sottosequenze periodiche dellinput per produrreun algoritmo di ordinamento pi ` u veloce.Knuth ha descrittoanche merge sort. Egli ricorda che nel 1938 fu inventatoun collazionatore meccanico in grado di fondere due pacchi di schede perforatein un solo passo. Nel 1945 J. von Neumann, uno dei pionieri dellinformatica,apparentemente scrisse un programma di merge sort nel calcolatore EDVAC.Gries [133] ha scritto la storia recente delle dimostrazioni della correttezza deiprogrammi; attribuisce a P. Naur il primo articolo in questo campo e a R. W. Floydle invarianti di ciclo. Il libro di Mitchell [222] descrive i pi ` u recenti progressi nelladimostrazione della correttezza dei programmi.Crescita delle funzioni 3Il tasso di crescita del tempo di esecuzione di un algoritmo, denito nel Capitolo 2,fornisce una semplice caratterizzazione dellefcienza dellalgoritmo; inoltre, ciconsente di confrontare le prestazioni relative di algoritmi alternativi. Se la dimen-sione dellinput n diventa sufcientemente grande, lalgoritmo merge sort, con ilsuo tempo di esecuzione(nlg n) nel caso peggiore, batte insertion sort, il cuitempo di esecuzione nel caso peggiore ` e (n2). Sebbene a volte sia possibile de-terminare il tempo esatto di esecuzione di un algoritmo, come abbiamo fatto coninsertion sort nel Capitolo 2, tuttavia lestrema precisione, di solito, non compensalo sforzo per ottenerla. Per input sufcientemente grandi, le costanti moltiplicati-ve e i termini di ordine inferiore di un tempo esatto di esecuzione sono dominatidagli effetti della dimensione stessa dellinput.Quando operiamo con dimensioni dellinput abbastanza grandi da rendere rile-vante soltanto il tasso di crescita del tempo di esecuzione, stiamo studiando lef-cienza asintotica degli algoritmi. In altre parole, ci interessa sapere come aumentail tempo di esecuzione di un algoritmo al crescere della dimensione dellinput allimite, quando la dimensione dellinput cresce senza limitazioni. Di solito, un al-goritmo che` e asintoticamentepi ` u efciente sar` a il migliore con tutti gli input,tranne con quelli molto piccoli.Questo capitolo descrive diversi metodi standard per semplicare lanalisi asin-totica degli algoritmi. Il prossimo paragrafo inizia denendo vari tipi di notazioniasintotiche, di cui abbiamo gi` a visto un esempio nella notazione . Poi sarannopresentate alcune convenzioni sulle notazioni che saranno adottate in tutto il libro.Inne, esamineremo il comportamento delle funzioni che comunemente si usanonellanalisi degli algoritmi.3.1 Notazione asintoticaLe notazioni che usiamo per descrivere il tempo di esecuzione asintotico di un al-goritmo sono denite in termini di funzioni il cui dominio ` e linsieme dei numerinaturali N = 0, 1, 2, . . .. Tali notazioni sono comode per descrivere la funzionedel tempo di esecuzione nel caso peggioreT(n), che di solito ` e denita soltantocon dimensioni intere dellinput. A volte, per` o, ` e lecito abusare della notazioneasintotica in vari modi. Per esempio, la notazione viene facilmente estesa al domi-nio dei numeri reali o limitata a un sottoinsieme dei numeri naturali. `E importantecapire il signicato esatto della notazione in modo che, quando se ne abusa, nonvenga utilizzata male. Questo paragrafo denisce le notazioni asintotiche di basee presenta anche alcuni tipici abusi.36 Capitolo 3 - Crescita delle funzioni(b) (c) (a)n n nn0n0n0f(n) = (g(n)) f(n) = O(g(n)) f(n) = (g(n))f(n)f(n)f(n)cg(n)cg(n)c1g(n)c2g(n)Figura 3.1 Esempi graci delle notazioni , O, e . Nei tre casi il valore di n0 mostrato ` e il pi` upiccolo possibile; ` e accettabile anche un valore pi` u grande. (a) La notazione limita una funzionea meno di fattori costanti. Si scrive f(n)= (g(n)) se esistono delle costanti positive n0, c1 e c2tali che, a destra di n0, il valore di f(n) ` e sempre compreso fra c1g(n) e c2g(n), estremi inclusi.(b) La notazioneO fornisce un limite superiore a una funzione a meno di un fattore costante. Siscrive f(n)=O(g(n)) se esistono delle costanti positive n0 e c tali che, a destra di n0, il valoredi f(n) ` e sempre uguale o minore di cg(n). (c) La notazione fornisce un limite inferiore a unafunzione a meno di un fattore costante. Si scrive f(n) = (g(n)) se esistono delle costanti positiven0 e c tali che, a destra di n0, il valore di f(n) ` e sempre uguale o maggiore di cg(n).Notazione Nel Capitolo2 abbiamo determinato che il tempo di esecuzione nel caso peggio-re di insertionsort ` eT(n) = (n2). Deniamo adessoil signicatodi questanotazione. Per una data funzioneg(n), indichiamo con(g(n)) linsiemedellefunzioni(g(n)) = f(n) : esistono delle costanti positive c1, c2 e n0 tali che0 c1g(n) f(n) c2g(n) per ogni n n0 .1Una funzione f(n) appartiene allinsieme (g(n)) se esistono delle costanti posi-tive c1 e c2 tali che essa possa essere compresa fra c1g(n) e c2g(n), per un valoresufcientemente grande din. Poich e(g(n))` e un insieme, potremmo scriveref(n) (g(n)) per indicare chef(n) ` e un membro di(g(n)). Invece, disolito, scriveremo f(n) =(g(n)) per esprimere lo stesso concetto. Questoabuso del simbolo di uguaglianza per denotare lappartenenza a un insieme, ini-zialmente, potrebbe sembrare poco chiaro, ma vedremo pi ` u avanti che ha i suoivantaggi.La Figura 3.1(a) presenta un quadro intuitivo delle funzioni f(n) e g(n), dovef(n)=(g(n)). Per tutti i valori di n a destra di n0, il valore di f(n) coincideo sta sopra c1g(n) e coincide o sta sotto c2g(n). In altre parole, per ogni n n0,la funzione f(n) ` e uguale a g(n) a meno di un fattore costante. Si dice che g(n) ` eun limite asintoticamente stretto per f(n).La denizione di(g(n)) richiede che ogni membro dif(n) (g(n)) siaasintoticamente non negativo, ovvero che f(n) sia non negativa quando n ` e suf-cientemente grande (una funzione asintoticamente positiva ` e positiva per qualsia-si valore sufcientemente grande di n). Di conseguenza, la funzioneg(n) stessa1Allinterno della notazione dellinsieme, i due punti (:) vanno letti tale che.3.1 Notazione asintotica 37deve essere asintoticamente non negativa, altrimenti linsieme(g(n)) ` e vuoto.Pertanto, supporremo che ogni funzione utilizzata nella notazione sia asintoti-camente non negativa. Questa ipotesi vale anche per le altre notazioni asintotichedenite in questo capitolo.Nel Capitolo2 abbiamointrodottoun concettoinformaledella notazioneche equivaleva a escludere i termini di ordine inferiore e a ignorare il coefcientedel termine di ordinepi ` u elevato. Giustichiamobrevemente questaintuizioneutilizzando la denizione formale per dimostrare che12n2 3n=(n2). Perfarlo, dobbiamo determinare le costanti positive c1, c2 e n0 in modo chec1n212n23n c2n2per qualsiasi n n0. Dividendo per n2, si hac1 12 3n c2La disuguaglianzadestra pu` o essere resa valida per qualsiasivaloredi n 1scegliendoc2 1/2. Analogamente, la disuguaglianza sinistra pu` o essere resavalida per qualsiasi valore din 7 scegliendoc1 1/14. Quindi, scegliendoc1=1/14, c2=1/2 en0=7, possiamo vericare che12n2 3n=(n2).Certamente ` e possibile scegliere altri valori delle costanti, ma la cosa importante` e che esiste qualche scelta. Notate che queste costanti dipendono dalla funzione12n2 3n; unaltra funzione che appartiene a(n2), di solito, richiede costan-ti differenti. Possiamo applicare anche la denizione formale per vericare che6n3,=(n2). Supponiamo per assurdo che esistano le costantic2 en0 tali che6n3c2n2per ogni n n0; ma alloran c2/6 e questo non pu` o essereassolutamente vero per n arbitrariamente grande, in quanto c2 ` e costante.Intuitivamente, i terminidi ordineinferioredi unafunzioneasintoticamentepositiva possono essere ignorati nel determinare i limiti asintoticamentestretti,perch e sono insignicanti per grandi valori di n. Una piccola frazione del terminedi ordine pi ` u elevato ` e sufciente a dominare i termini di ordine inferiore. Quin-di, assegnando a c1 un valore che ` e leggermente pi ` u piccolo del coefciente deltermine di ordine pi ` u elevato e a c2 un valore che ` e leggermente pi ` u grande, ` e pos-sibile soddisfare le disuguaglianze nella denizione della notazione. In modoanalogo, pu` o essere ignorato il coefciente del termine di ordine pi ` u elevato, inquanto esso cambia soltanto c1 e c2 di un fattore costante pari al coefciente.Come esempio consideriamo una funzione quadratica f(n) = an2+bn+c, do-ve a, b e c sono costanti e a >0. Escludendo i termini di ordine inferiore e ignoran-do la costante, si ha f(n)=(n2). Formalmente, per dimostrare la stessa cosa,prendiamo le costanti c1=a/4, c2=7a/4 e n0=2max(([b[ /a),_([c[ /a)).Il lettore pu` o vericare che 0 c1n2 an2+bn+c c2n2per ogni n n0. Ingenerale, per qualsiasi polinomiop(n)= di=0aini, dove i coefcientiai sonocostanti e ad> 0, si ha p(n) = (nd) (vedere Problema 3-1).Poich e qualsiasi costante ` e un polinomio di grado 0, possiamo esprimere qual-siasi funzione costante come(n0) o(1). Questultima notazione, tuttavia, ` e38 Capitolo 3 - Crescita delle funzioniun abuso di secondordine, perch e non ` e chiaro quale variabile tende allinnito.2Adotteremo spesso la notazione(1) per indicare una costante o una funzionecostante rispetto a qualche variabile.Notazione OLa notazione limita asintoticamente una funzione da sopra e da sotto. Quandoabbiamo soltanto un limite asintotico superiore, utilizziamo la notazioneO. Peruna data funzione g(n), denotiamo con O(g(n)) (si legge O grande di g di n osemplicemente O di g di n) linsieme delle funzioniO(g(n)) = f(n) : esistono delle costanti positive c e n0 tali che0 f(n) cg(n) per ogni n n0La notazioneO si usa per assegnare un limite superiore a una funzione, a menodi un fattore costante. La Figura 3.1(b) illustra il concetto intuitivo che sta dietroquesta notazione. Per qualsiasi valoren a destra din0, il valore della funzionef(n) coincide o sta sotto cg(n).Si scrivef(n)=O(g(n)) per indicare che una funzionef(n) ` e un membrodellinsiemeO(g(n)). Notate chef(n) =(g(n)) implicaf(n) =O(g(n)),in quantola notazione` e una nozionepi ` ufortedellanotazioneO. Secondola notazione della teoria degli insiemi possiamo scrivere(g(n)) O(g(n)).Quindi, la nostra dimostrazione che qualsiasi funzione quadraticaan2+ bn + c,con a > 0, ` e in (n2) implica anche che tali funzioni quadratiche sono in O(n2).Ci ` o che pu` o sembrare pi ` u sorprendente ` e che qualsiasi funzione lineare an +b ` ein O(n2); questo ` e facilmente vericabile ponendo c = a +[b[ e n0= 1.I lettori che hanno gi` a visto la notazioneO potrebbero trovare strano che noiscriviamo, per esempio, n = O(n2). Nella letteratura, la notazione O viene a vol-te utilizzata informalmente per descrivere i limiti asintoticamente stretti, ovveroci ` o che noi abbiamo denito con la notazione . In questo libro, tuttavia, quandoscriviamof(n)=O(g(n)), stiamo semplicemente affermando che qualche co-stante multipla di g(n) ` e un limite asintotico superiore di f(n), senza specicarequanto sia stretto il limite superiore. La distinzione fra limiti superiori asintotici elimiti asintoticamente stretti ` e diventata standard nella letteratura degli algoritmi.Utilizzando la notazione O, spesso, ` e possibile descrivere il tempo di esecuzio-ne di un algoritmo, esaminando semplicemente la struttura complessiva dellal-goritmo. Per esempio, la struttura con i cicli doppiamente annidati dellalgoritmoinsertion sort del Capitolo 2 genera immediatamente un limite superioreO(n2)sul tempo di esecuzione nel caso peggiore: il costo di ogni iterazione del ciclo in-terno ` e limitato superiormente da O(1) (costante), gli indici i e j sono entrambi almassimo n; il ciclo interno viene eseguito al massimo una volta per ognuna dellen2coppie di valori i e j.Poich e la notazioneO descrive un limite superiore, quando la utilizziamo perlimitare il tempo di esecuzione nel caso peggiore di un algoritmo, abbiamo unlimitesultempodi esecuzionedellalgoritmoperogniinput. Quindi, illimite2Il problema reale ` e che la nostra notazione ordinaria per le funzioni non distingue le funzioni daivalori. Nel lambda-calcolo, i parametri di una funzione sono specicati in modo chiaro: la funzionen2pu` o essere scrittan.n2o ancher.r2. Tuttavia, se adottassimo una notazione pi` u rigorosa,complicheremmo le manipolazioni algebriche; per questo abbiamo scelto di tollerare labuso.3.1 Notazione asintotica 39O(n2) sul tempo di esecuzione nel caso peggiore di insertion sort si applica ancheal suo tempo di esecuzione per qualsiasi input. Il limite (n2) sul tempo di ese-cuzione nel caso peggiore di insertion sort, tuttavia, non implica un limite (n2)sul tempo di esecuzione di insertion sort per qualsiasi input. Per esempio, abbia-mo visto nel Capitolo 2 che, quando linput ` e gi` a ordinato, insertion sort vieneeseguito nel tempo (n).Tecnicamente, ` e un abuso dire che il tempo di esecuzione di insertion sort` eO(n2), in quanto, per un dato n, il tempo effettivo di esecuzione varia a secondadel particolare input di dimensione n. Quando scriviamo il tempo di esecuzione` eO(n2), intendiamo dire che c` e una funzionef(n) che ` e O(n2) tale che, perqualsiasi valore din, indipendentementeda quale input di dimensionen vengascelto, il tempo di esecuzione con quellinput` e limitato superiormente dal valo-ref(n). In modo equivalente, intendiamoche il tempo di esecuzionenel casopeggiore ` e O(n2).Notazione Cos` come la notazione O fornisce un limite asintotico superiore a una funzione,la notazione fornisce un limite asintotico inferiore. Per una data funzione g(n),denotiamocon(g(n)) (si leggeOmega grandedi gdi n o semplicementeOmega di g di n) linsieme delle funzioni(g(n)) = f(n) : esistono delle costanti positive c e n0 tali che0 cg(n) f(n) per ogni n n0Il concetto intuitivo che sta dietro la notazione ` e illustrato nella Figura 3.1(c).Per tutti i valori di n a destra di n0, il valore di f(n) coincide o sta sopra cg(n).Dalle denizioni delle notazioni asintotiche che abbiamo visto nora, ` e faciledimostrare il seguente importante teorema (vedere Esercizio 3.1-5).Teorema 3.1Per ogni coppia di funzionif(n) e g(n), si ha f(n)=(g(n)), se e soltanto sef(n) = O(g(n)) e f(n) = (g(n)).Come esempio applicativo di questo teorema, la nostra dimostrazione che an2+bn + c=(n2) per qualsiasi costantea, b e c, cona>0, implica immediata-mente che an2+ bn + c=(n2) e an2+ bn + c=O(n2). In pratica, anzich eusare il Teorema 3.1 per ottenere i limiti asintotici superiore e inferiore dai limitiasintoticamente stretti, come abbiamo fatto per questo esempio, di solito lo usia-mo per dimostrare i limiti asintoticamente stretti dai limiti asintotici superiore einferiore.Poich e la notazione descrive un limite inferiore, quando la usiamo per li-mitare il tempo di esecuzione nel caso migliore di un algoritmo, implicitamen-te limitiamo anche il tempo di esecuzione dellalgoritmo con input arbitrari. Peresempio, il tempo di esecuzione nel caso migliore di insertion sort` e(n), cheimplica che il tempo di esecuzione di insertion sort ` e (n).Il tempo di esecuzione di insertion sort quindi ` e compreso fra (n) e O(n2), inquanto si trova in una zona compresa tra una funzione lineare di n e una funzionequadratica din. Inoltre, questi limiti sono asintoticamente i pi ` u stretti possibili:per esempio, il tempo di esecuzione di insertion sort non ` e (n2), in quanto esisteun input per il quale insertion sort viene eseguito nel tempo (n) (per esempio,40 Capitolo 3 - Crescita delle funzioniquando linput ` e gi` a ordinato). Tuttavia, non` e contraddittorioaffermare che iltempo di esecuzione nel caso peggiore di insertion sort ` e (n2), in quanto esisteun input con il quale lalgoritmo impiega un tempo (n2). Quando diciamo che iltempo di esecuzione di un algoritmo ` e (g(n)), intendiamo che indipendentemen-te da quale particolare input di dimensione n sia scelto per qualsiasi valore di n,il tempo di esecuzione con quellinput ` e pari ad almeno una costante moltiplicataper g(n), con n sufcientemente grande.Notazione asintotica nelle equazioni e nelle disuguaglianzeAbbiamo gi` a visto come la notazione asintotica possa essere utilizzata allinternodi formule matematiche. Per esempio, presentando la notazione O, abbiamo scrit-to n=O(n2). Avremmo potuto scrivere anche 2n2+ 3n + 1=2n2+ (n).Come vanno interpretate queste formule?Quando la notazione asintotica sta da sola sul lato destro di unequazione (odisuguaglianza), come inn=O(n2), abbiamo gi` a denito il segno uguale perindicare lappartenenza allinsieme: n O(n2). In generale, per` o, quando la no-tazione asintotica appare in una formula, va interpretata come se indicasse qualchefunzione anonima, di cui non ` e importante fare il nome. Per esempio, la formula2n2+ 3n + 1=2n2+ (n) signica che2n2+ 3n + 1=2n2+ f(n), dovef(n) ` e qualche funzione dellinsieme(n). In questo caso, f(n)=3n + 1, cheappartiene effettivamente a (n).Utilizzando la notazione asintotica in questo modo, ` e possibile eliminare detta-gli superui e poco chiari da unequazione. Per esempio, nel Capitolo 2 abbiamoespresso il tempo di esecuzione nel caso peggiore di merge sort come la ricorrenzaT(n) = 2T(n/2) + (n)Se siamo interessati soltanto al comportamento asintotico di T(n), non ` e impor-tante specicare con esattezza tutti i termini di ordine inferiore; ` e sottointeso cheessi siano tutti inclusi nella funzione anonima indicata dal termine (n).Il numero di funzioni anonime in unespressione ` e sottointeso che sia uguale alnumero di volte che appare la notazione asintotica; per esempio, nellespressionen

i=1O(i)c` e una sola funzione anonima (una funzione di i). Questa espressione non ` e quin-di la stessa cosa di O(1) + O(2) ++ O(n) che, in effetti, non ha una chiarainterpretazione.In alcuni casi, la notazione asintotica si trova sul lato sinistro di unequazione,come in2n2+ (n) = (n2)Per interpretare simili equazioni, applichiamo la seguente regola:Indipendente-mentedalmodoincuivenganosceltelefunzionianonimeasinistradelsegnouguale,c` e un modo di sceglierele funzionianonime a destra del segno ugualeper rendere valida lequazione. Quindi, il signicato del nostro esempio ` e che perqualsiasi funzionef(n) (n), c` equalche funzioneg(n) (n2) tale che2n2+ f(n) = g(n) per ogni n. In altre parole, il lato destro di unequazione for-nisce un livello di dettaglio pi ` u grossolano del lato sinistro.3.1 Notazione asintotica 41Simili relazioni potrebbero essere concatenate in questo modo2n2+ 3n + 1 = 2n2+ (n)= (n2)Applicando la precedente regola, possiamo interpretare separatamente le singoleequazioni. La prima equazione indica che esiste qualche funzionef(n) (n)tale che 2n2+3n+1 = 2n2+f(n) per ogni n. La seconda equazione indica cheper qualsiasi funzioneg(n) (n) (come la funzionef(n) appena citata), c` equalche funzione h(n) (n2) tale che 2n2+ g(n)=h(n) per ogni n. Notateche questa interpretazioneimplica che2n2+ 3n+1 =(n2), che` e quantointuitivamente indicano le equazioni concatenate.Notazione oIl limite asintotico superiore fornito dalla notazione O pu` o essere asintoticamentestretto oppure no. Il limite 2n2= O(n2) ` e asintoticamente stretto, mentre il limite2n = O(n2) non lo ` e. Utilizziamo la notazione o per denotare un limite superioreche non` e asintoticamentestretto. Deniamo formalmenteo(g(n)) (si legge opiccolo di g di n) come linsiemeo(g(n)) = f(n) : per qualsiasi costante c > 0, esiste una costanten0> 0 tale che 0 f(n) < cg(n) per ogni n n0Per esempio, 2n = o(n2), ma 2n2,= o(n2).Le denizioni delle notazioni O e o sono simili. La differenza principale ` e chein f(n)=O(g(n)) il limite 0 f(n) cg(n) vale per qualche costante c > 0,mentre in f(n)=o(g(n)) il limite0 f(n) 0. Intuitivamente, nella notazioneo la funzionef(n) diventa insignicanterispetto a g(n) quando n tende allinnito; ovverolimnf(n)g(n)= 0 (3.1)Alcuni autori usano questo limite come denizione della notazioneo; la deni-zione in questo libro vincola anche le funzioni anonime a essere asintoticamentenon negative.Notazione Per analogia, la notazionesta alla notazione come la notazioneo sta allanotazioneO. Utilizziamo la notazione per indicare un limite inferiore che non` e asintoticamente stretto. Un modo per denirla ` e il seguentef(n) (g(n)) se e soltanto se g(n) o(f(n))Formalmente, tuttavia, deniamo(g(n))(omegapiccolodi gdi n)comelinsieme(g(n)) = f(n) : per qualsiasi costante c > 0, esiste una costanten0> 0 tale che 0 cg(n) < f(n) per ogni n n0Per esempio, n2/2=(n), man2/2 ,=(n2). La relazionef(n)=(g(n))implica che42 Capitolo 3 - Crescita delle funzionilimnf(n)g(n)= se il limite esiste; cio` e f(n) diventa arbitrariamente grande rispetto a g(n) quandon tende allinnito.Confronto di funzioniMolte delle propriet` a delle relazioni dei numeri reali si applicano anche ai con-fronti asintotici. Supponiamo che f(n) e g(n) siano asintoticamente positive.Propriet` a transitiva:f(n) =(g(n)) e g(n) =(h(n)) implicano f(n) =(h(n))f(n) =O(g(n)) e g(n) =O(h(n)) implicano f(n) =O(h(n))f(n) =(g(n)) e g(n) =(h(n)) implicano f(n) =(h(n))f(n) =o(g(n)) e g(n) =o(h(n)) implicano f(n) =o(h(n))f(n) =(g(n)) e g(n) =(h