Riassunto esame Algoritmica, prof. Romani, libro consigliato Elementi di Algoritmica di Francesco Romani

Sunti di algoritmica

Università di Pisa - Professore esame: Francesco Romani

Libro: Elementi di Algoritmica, Francesco Romani

Prima parte: Algoritmi e modelli di calcolo

Comunicazione, linguaggio e linguaggi

Il linguaggio è uno strumento essenziale per esprimere concetti in modo non ambiguo; si distinguono linguaggi naturali (esseri umani) e linguaggi artificiali (linguaggi di programmazione). Per ciascun linguaggio si distingue l’aspetto lessicale, sintattico e semantico: la correttezza di tutti questi aspetti determina la correttezza della comunicazione.

È necessario quindi fornire in modo non ambiguo le specifiche lessicali, semantiche e sintattiche di un linguaggio: quelle lessicali riguardano le regole di formazione delle parole e la corretta ortografia dei termini convenzionali del linguaggio (detti parole chiave), quelle sintattiche riguardano le regole di formazione di frasi corrette a partire dai termini del linguaggio, quelle semantiche, per i linguaggi di programmazione, permettono di stabilire i risultati dell’esecuzione di un programma e possono essere fornite in modo intuitivo o in forma matematica.

La definizione lessicale e sintattica dei linguaggi può essere data mediante un apparato formale, secondo il metodo delle grammatiche formali introdotto dal linguista Chomsky.

Per alfabeto si intende un insieme finito di simboli, che non sono necessariamente caratteri tipografici, ma possono essere anche espressioni più complesse. È necessario stabilire con chiarezza l’alfabeto su cui si opera per evitare ambiguità. Es. W={a, b}

Per stringa di un alfabeto W si intende una sequenza finita di simboli dell’alfabeto, ottenuta attraverso un’operazione di giustapposizione o concatenazione; viene considerata anche la stringa vuota indicata con la lettera greca λ (lambda). L’insieme di tutte le stringhe di un alfabeto W si indica con W*. Es. W={a, b}; Stringhe=”a”,”ab”,”abba”,”bab”, ecc.

Per linguaggio di un alfabeto W si intende un qualsiasi sottoinsieme L dell’insieme delle stringhe di W. Un linguaggio finito può essere descritto mediante l’elenco delle stringhe che lo compongono. I linguaggi di programmazione appartengono a una classe di linguaggi facilmente definibile e maneggiabile.

Esistono vari meccanismi per la definizione dei linguaggi:

• Metodo di riconoscimento: procedimento che riceve come dato di ingresso una stringa e restituisce “sì” o “no” a seconda che la stringa appartenga o meno al linguaggio; questo metodo non è consigliabile per studiare la struttura di un intero linguaggio in quanto permette solo un approccio per tentativi.
• Metodo di generazione: procedimento che permette di generare una a una tutte le stringhe del linguaggio (per i linguaggi finiti), fornendo via via indicazioni sulla sua struttura.
• Apparato algebrico: procedimento che permette di dare espressioni esplicite per gli elementi del linguaggio, per esempio {x {a, b}* | x=aⁿbⁿ, n ∈ N}.

Algoritmi e calcolabilità

Per algoritmo si intende la descrizione precisa delle azioni da compiere per risolvere un problema di qualsiasi genere; possiamo sempre distinguere tre elementi essenziali: il problema da risolvere (es. trovare la torre di Pisa), il procedimento per risolvere il problema (es. la strada più breve per la torre di Pisa), e l’agente di calcolo che esegue le istruzioni (es. il turista). L’algoritmo è sempre espresso in forma rigorosa, in modo da essere comprensibile ed eseguibile senza possibilità di errore.

Ogni istruzione è detta passo dell’algoritmo, ovvero un’unità comprensibile ed eseguibile. La precisione dell’algoritmo è inversamente proporzionale alle capacità dell’agente di calcolo, ma quando l’esecutore è un calcolatore, non si può lasciar niente di implicito. È sempre necessario quindi stabilire il livello di dettaglio, il linguaggio e l’ambiente in cui si opera. Quest’ultimo è detto ambiente di calcolo: in ogni ambiente esistono oggetti su cui si opera e strumenti per operare (operazioni aritmetiche: i numeri, le quattro operazioni).

Un algoritmo deve soddisfare determinati requisiti:

• Lunghezza finita: deve essere esprimibile con una sequenza finita di passi.
• Passi discreti: ogni passo deve essere elementare e distinto dagli altri.
• Non ambiguità: i singoli passi devono essere comprensibili per l’agente di calcolo.
• Non casualità: niente deve essere lasciato al caso, il risultato prodotto è certo e ripetibile.
• Determinismo: ogni volta si deve effettuare una sola fra le scelte possibili.

I computer sono particolari macchine in grado di eseguire algoritmi in particolari ambienti di calcolo, purché questi siano descritti tramite linguaggi di programmazione. Il programmatore deve chiarire l’algoritmo in ogni dettaglio definendo il flusso logico, permettendo di verificare velocemente la correttezza del procedimento e di localizzare eventuali errori. Viene così evidenziata la potenziale utilità formativa di un approccio algoritmico ai problemi.

La macchina di Turing

La macchina di Turing si ottiene dotando un controllo a stati finiti di un nastro illimitato su cui possono essere scritti e letti caratteri di un apposito alfabeto. Le azioni del controllo dipendono dal suo stato interno e dal simbolo letto, e consistono nella scrittura di un nuovo simbolo con spostamento del punto di lettura verso destra o sinistra. All’inizio il nastro contiene tutti blank tranne una stringa di input, e il punto di lettura è posizionato all’inizio della stringa. Se l’elaborazione termina in un numero finito di passi, il risultato è formato dalla parte di nastro che contiene simboli diversi da blank. Non si può sapere quando e se l’elaborazione terminerà.

Una MdT è definita come una quintupla M=(K, V, s, F) dove:

• K è un insieme finito di stati
• V è l’alfabeto d’ingresso
• s è lo stato iniziale
• δ è una funzione di transizione che associa a una coppia (x, q), con x: simbolo dell’alfabeto e q: stato, una tripla (y, a, m) con y: stato, a: simbolo che sostituisce e m: spostamento a destra o a sinistra.
• F è un insieme di stati finali

Si dice configurazione la tripla (q, α, i) dove q è lo stato attuale, α è la stringa ottenuta togliendo gli infiniti blank iniziali e finali, e i è la distanza del punto di lettura dall’inizio di α. Si definisce mossa il passaggio da una configurazione all’altra.

Tutte le possibili definizioni del formalismo delle MdT sono equivalenti: per ogni macchina definita nel modo A è possibile costruire una particolare macchina definita in un modo B che produce lo stesso risultato della prima. Con le macchine di Turing e un po’ di esperienza è possibile realizzare ogni tipo di algoritmo. È stato rigorosamente dimostrato che tutte le definizioni conosciute di modelli di calcolo sufficientemente potenti sono equivalenti al modello delle macchine di Turing e inoltre ogni definizione che possa mai venire pensata di un modello di calcolo è equivalente alle macchine di Turing (tesi di Church, ritenuta vera ma non dimostrabile).

Una caratteristica fondamentale delle MdT è l’universalità: si possono costruire macchine universali capaci di simulare il funzionamento di ogni altra macchina di Turing, ricevendone la descrizione nella stringa d’ingresso. Qui si possono introdurre i concetti di programma memorizzato e dato di ingresso: la descrizione dell’algoritmo non è più una proprietà intrinseca della macchina, ma un dato di ingresso detto programma.

La Random Access Machine

Le macchine di Turing sono molto lontane dalla struttura dei calcolatori reali. Una Random Access Machine è composta da un nastro di input su cui è permessa la sola lettura di numeri interi relativi, un nastro di output su cui è permessa la sola scrittura di numeri interi relativi, una sequenza di istruzioni detta programma e una memoria composta da illimitati registri identificati da un numero naturale detto indirizzo.

Le istruzioni permettono di leggere numeri e memorizzarli, effettuare operazioni aritmetiche e di confronto, scrivere il contenuto dei registri sul nastro di output e infine passare a un’altra istruzione con un salto incondizionato o condizionato (in base al valore del registro).

Si indichi con op un operando del tipo “=i”, “i”, “(i)”:

• “=i” rappresenta la costante intera i: val(“=i”) = i
• “i” rappresenta il contenuto del registro di indirizzo i: val(“i”) = c(i)
• “(i)” rappresenta il contenuto del registro il cui indirizzo è contenuto nel registro i: val(“(i)”) = c(c(i))

E si indichi con et una etichetta, ovvero un numero o un nome che identifica univocamente un’istruzione del programma; un possibile insieme di istruzioni per una Ram è il seguente:

Data una MdT M esiste una RAM R che la simula: con lo stesso dato di ingresso entrambe le macchine non terminano o restituiscono lo stesso output. Data una RAM R esiste una MdT M che la simula: il nastro di M simula la memoria illimitata di R e le quintuple producono nel nastro le stesse azioni che in memoria produce il programma. Un qualunque calcolatore, ammettendo una quantità illimitata di memoria, costituisce un modello di calcolo equivalente alla RAM.

Seconda parte: Analisi e sintesi di algoritmi

Introduzione alla complessità computazionale concreta

Dato un qualunque problema esistono infiniti algoritmi per risolverlo. Il problema sta nell’individuare il migliore fra essi: la complessità computazionale concreta studia appunto la questione dell’efficienza degli algoritmi e del costo della risoluzione dei problemi. La difficoltà nel risolvere un problema dipende dalla sua natura e dalla sua dimensione, la quale è comunemente legata al numero dei dati in input.

Un problema di riconoscimento di una stringa ha come dimensione la lunghezza della stringa, operazioni su alberi e grafi hanno come dimensione il numero dei nodi e degli archi, i calcoli di una RAM hanno come dimensione la lunghezza della stringa di input, e così via.

Dato un modello di calcolo si possono scegliere varie misure di costo che tengono conto della qualità della risorsa utilizzata per risolvere un problema. Un computer reale può avere come misure di costo il tempo di elaborazione in secondi (misura di tempo) o il numero massimo di byte di memoria utilizzati (misura di spazio).

Si definisce complessità o costo di un algoritmo una funzione non negativa, non decrescente e a valori interi, che associa alla dimensione del problema il costo della sua risoluzione in base alla misura scelta. Uno stesso algoritmo, con dati diversi della stessa dimensione, può presentare diversa complessità. In questo caso si parla di complessità nel caso peggiore se si prende in considerazione il caso più sfavorevole e di complessità media se si prende in considerazione la media dei casi.

Si definisce complessità del problema una funzione che associa alla dimensione del problema il minimo costo della risoluzione in base alla misura scelta. Anche in questo caso, se la funzione dipende anche dal dato di ingresso e non solo dalla sua dimensione, si parla di complessità nel caso peggiore o di complessità media. Per determinare la complessità di un problema bisognerebbe individuare e valutare tutti gli algoritmi che lo risolvono, ma questo studio è chiaramente impossibile.

Si ricorre quindi a funzioni che limitino la complessità dal basso all’alto: se per il problema P si trova un algoritmo A di complessità f(n) che lo risolve, si dice che f(n) è una limitazione superiore alla complessità di P; se si dimostra che non esiste alcun algoritmo di complessità minore o uguale a g(n) che risolve il problema, allora si dice che g(n) è una limitazione inferiore alla complessità di P. Se per uno stesso problema P vale che f(n)=g(n), allora si afferma che la complessità di P è f(n).

In generale una funzione di complessità risulta essere complicata e poco intuitiva, poiché deve tener conto di molti dettagli (fasi della risoluzione, misura di complessità, ecc.) Per ovviare a questo inconveniente comunemente si introduce il concetto di ordine di grandezza di una funzione, ovvero ci si concentra sulla velocità di crescita della funzione di complessità al tendere di n all’infinito.

Con la notazione O(f(n)) si indica l’insieme delle funzioni g(n) per cui esistono due costanti c e n₀ tali che g(n) ≤ c f(n) per ogni n > n₀. Si dice quindi che g(n)=O(f(n)), ovvero che g(n) è di ordine f(n).

Con la notazione Ω(f(n)) si indica l’insieme delle funzioni g(n) per cui esistono due costanti c e n₀ tali che g(n) ≥ c f(n) per ogni n > n₀. Si dice quindi che g(n)=Ω(f(n)), ovvero che g(n) è di ordine omega f(n).

In base alla loro complessità gli algoritmi sono suddivisi in classi di funzioni:

• Complessità costante: tutte le costanti reali sono dell’ordine di 1, a=O(1)
• Crescita lineare: tutte le funzioni del tipo an + b (2n, 3n + 2, ecc.) sono dell’ordine di n, an + b=O(n)
• Crescita quadratica: tutte le funzioni del tipo an² + bn + p(log n) + c sono dell’ordine di n²
• Crescita cubica: tutte le funzioni del tipo an³ + bn² + cn + p(log n) + d sono dell’ordine di n³
• Crescita logaritmica: tutte le funzioni del tipo a log n + (termini di ordine inferiore) sono dell’ordine di log n
• Crescita esponenziale: tutte le funzioni del tipo aⁿ + bⁿ + p(n) + q(log n), con n>m, p e q polinomi di qualsiasi grado e a>b>1, sono dell’ordine di aⁿ

Si parla di limitazioni inferiori e superiori anche in termini di ordine di grandezza; quando la limitazione inferiore è dello stesso ordine di quella superiore, si è determinato l’ordine di grandezza della complessità del problema. È possibile limitare superiormente l’ordine di grandezza di funzioni limitate da relazioni ricorrenti del tipo: β f(n) ≤ u f ([n/v]) + c n⁰, per ogni n>n₀. Poiché una simile relazione compare spesso nell’analisi di algoritmi definiti per ricorrenza, vediamo in dettaglio il seguente lemma:

Tecniche di programmazione ricorsiva

La ricorsione è un potente strumento per la descrizione degli algoritmi e agevola la determinazione di limitazioni superiori alla loro complessità.

La funzione fattoriale n! è definita ricorsivamente come 0!=1, n!=n(n-1)!, con n>0:

>>>def fattoriale(n):
    if n==0:
        return 1
    return n* fattoriale(n-1)
>>>print ("12!", fattoriale(12))
>>>print ("13!", fattoriale(13))
>>>print ("14!", fattoriale(14))

Un programma che stampi la rappresentazione binaria di un numero intero positivo si basa sull’osservazione che, dato un numero n, se la sua rappresentazione…