Gli Algoritmi
L’algoritmo è un insieme ordinato di
operazioni non ambigue ed effettivamente
computabili che, quando eseguito, produce
un risultato e si arresta in un tempo finito.
Analizziamo ora le diverse
componenti della frase
Un insieme ordinato
Un algoritmo è un insieme di operazioni, per le
quali deve esistere un ordinamento chiaro e non
ambiguo. Ciò significa che sappiamo quale
operazione eseguire per prima e quale eseguire
dopo averne completata una. Dobbiamo essere
estremamente precisi nello specificare l’ordine
in cui le operazioni devono essere eseguite.
Non ambigue
Le operazioni utilizzate in un algoritmo devono soddisfare due
criteri: essere non ambigue ed essere effettivamente
computabili. Un’operazione è non ambigua quando può essere
compresa ed eseguita direttamente dall’agente di calcolo senza
necessità i ulteriori semplificazioni o spiegazioni(detta primitiva).
Effettivamente computabili
Tuttavia, non è sufficiente che un’operazione sia comprensibile.
Deve anche essere eseguibile dall’agente di calcolo. Eseguibile
significa che deve esistere un processo computazionale che
consente all’agente di calcolo di completare l’operazione con
successo.
Che produce un risultato
gli algoritmi risolvono problemi. Perché sia possibile determinare
se una soluzione è corretta, l’algoritmo deve produrre un
risultato osservabile da un utente, come un valore numerico, un
nuovo oggetto o una modifica dell’ambiente. Utilizziamo la
parola risultato invece che la parola risposta. Talvolta un
algoritmo non può fornire la risposta corretta, perché per un
dato input, tale risposta non esiste. In questi casi l’algoritmo può
produrre qualcos’altro, come un messaggio di errore, una luce
rossa d’avvertimento, o un’approssimazione della risposta
corretta (risultati osservabili).
E termina in un tempo finito
un’altra importante caratteristica degli algoritmi è che devono
produrre il risultato dopo l’esecuzione di un numero finito di
operazioni; dobbiamo garantire che l’algoritmo alla fine
raggiungerà un’istruzione del tipo: «stop, ho finito». Quindi alla
fine l’algoritmo si dovrà arrestare
Risoluzione algoritmica dei
problemi
Il dispositivo dovrebbe eseguire meccanicamente le
istruzioni e completare con successo il compito
senza la necessità di comprendere i processi che
hanno portato a scoprire la soluzione. Il robot si
limita a eseguire i passi nell’ordine specificato ,
completando con successo ciascuna operazione e
alla fine producendo il risultato desiderato in un
tempo finito. Tutto questo grazie a una rivoluzione
informatica è eseguito dai computer, che è molto
più efficiente di quel particolarissimo agente di
calcolo che è il cervello umano.
Top-down e Bottom-up
• La programmazione top-down è
uno stile di programmazione in
cui la progettazione inizia
specificando parti complesse e
suddividendole successivamente
in parti più piccole (divide et
impera).
• Il bottom up prende corpo dal
punto di partenza (bottom)
ovvero dalla situazione iniziale;
considera l'obiettivo finale,
induce a costruire un percorso
sequenziale organizzato in
passaggi successivi in cui
l'ancoraggio tra traguardi
intermedi e obiettivo finale è
generalmente ricercato in modo
intuitivo.
Esempi di algoritmo
Gli algoritmi vengono raggruppati e catalogati a seconda della loro funzione o delle
tecniche utilizzate per realizzarli, tuttavia una catalogazione rigorosa e completa è
ormai diventata impossibile.
Alcuni tipi di algoritmo
•
Algoritmi di ordinamento
•
Algoritmi di ricerca
•
Genetici evolutivi
•
Swarm Intelligence
•
Ricorsivi
•
Algoritmo combinatorio
•
Codice automodificante
•
Conversione e codifica
•
Algoritmi di compressione: senza perdita di informazioni e con perdita di informazioni
Molte categorie di algoritmi sono strettamente legate all'organizzazione dei dati in memoria (strutture dati).
Altri algoritmi
•
Algoritmi quantistici
•
Algoritmo apriori
•
Algoritmo di Berger
•
Algoritmo di Sturm
•
Algoritmo online
•
Algoritmo di pitch detection
Risoluzione degli algoritmi
Gli algoritmi possono essere espressi in diverse forme
• linguaggio naturale
• in forma grafica
• utilizzando i costrutti di un linguaggio di programmazione.
I Programmi descrivono gli algoritmi in termini di sequenze di istruzioni scritte
in un opportuno linguaggio di programmazione, comprensibile al calcolatore.
Compito del programmatore:
• Individuare la sequenza di passi che portano alla soluzione del problema e
produrre il relativo algoritmo
• Codificare l'algoritmo in un programma
Per costruire un programma
Per costruire un programma sono necessari tre tipi di meccanismi di
strutturazione:
• struttura di sequenza
che permette di comporre istruzioni ed eseguirle
una di seguito all'altra; ha un solo ingresso ed una sola uscita.
• struttura condizionale che permette di eseguire una sola istruzione tra
due o più istruzioni, in base al valore di un'espressione booleana.
• struttura di iterazione
che permette di eseguire ripetutamente
un'istruzione sotto il controllo di un'espressione booleana.
Bubble sort (algoritmo di
ordinamento)
Il suo funzionamento è semplice: ogni coppia di
elementi adiacenti della lista viene comparata e
se essi sono nell'ordine sbagliato vengono
invertiti. L'algoritmo scorre poi tutta la lista
finché non vengono più eseguiti scambi,
situazione che indica che la lista è ordinata.
Quicksort
Quicksort è un algoritmo di ordinamento
ricorsivo che si basa sul paradigma divide et
impera.
esempio di Quicksort
es
esempio di Bubble sort