# Informatica 5 Liceo Scientifico Scienze Applicate/Algoritmi

Informatica 5 Liceo Scientifico Scienze Applicate
Copertina Tutti i moduli · Sviluppo
    CopertinaInformatica 5 Liceo Scientifico Scienze Applicate/Copertina
* OctaveInformatica 5 Liceo Scientifico Scienze Applicate/Octave
* MatriciInformatica 5 Liceo Scientifico Scienze Applicate/Matrici
* Sistema di equazioni lineariInformatica 5 Liceo Scientifico Scienze Applicate/Sistema di equazioni lineari
* LatexInformatica 5 Liceo Scientifico Scienze Applicate/Latex
* Istruzioni Programmazione OctaveInformatica 5 Liceo Scientifico Scienze Applicate/Istruzioni Programmazione Octave
** EserciziInformatica 5 Liceo Scientifico Scienze Applicate/Istruzioni Programmazione Octave/Esercizi
* Gauss Risoluzione Sistemi LineariInformatica 5 Liceo Scientifico Scienze Applicate/Gauss Risoluzione Sistemi Lineari
* Jacobi Risoluzione Sistemi LineariInformatica 5 Liceo Scientifico Scienze Applicate/Jacobi Risoluzione Sistemi Lineari
* Calcolare Numericamente un IntegraleInformatica 5 Liceo Scientifico Scienze Applicate/Calcolare Numericamente un Integrale
** AreaInformatica 5 Liceo Scientifico Scienze Applicate/Area
* Risolvere Numericamente una equazione differenzialeInformatica 5 Liceo Scientifico Scienze Applicate/Risolvere Numericamente una equazione differenziale
** Decadimento RadioattivoInformatica 5 Liceo Scientifico Scienze Applicate/Decadimento Radioattivo
* Grafici in OctaveInformatica 5 Liceo Scientifico Scienze Applicate/Grafici in Octave
* Metodo di BisezioneInformatica 5 Liceo Scientifico Scienze Applicate/Metodo di Bisezione
* FrattaliInformatica 5 Liceo Scientifico Scienze Applicate/Frattali
* Problemi legati al Calcolo NumericoInformatica 5 Liceo Scientifico Scienze Applicate/Problemi legati al Calcolo Numerico
* Tecnica di MontecarloInformatica 5 Liceo Scientifico Scienze Applicate/Tecnica di Montecarlo
* AlgoritmiInformatica 5 Liceo Scientifico Scienze Applicate/Algoritmi
* Algoritmi Complessità computazionaleInformatica 5 Liceo Scientifico Scienze Applicate/Algoritmi Complessità computazionale
* Modelli e SimulazioneInformatica 5 Liceo Scientifico Scienze Applicate/Modelli e Simulazione
** Modelli e SistemiInformatica 5 Liceo Scientifico Scienze Applicate/Modelli e Sistemi
** Tipi di Modello
** Diagrammi a blocchiInformatica 5 Liceo Scientifico Scienze Applicate/Diagrammi a blocchi
** Sistemi a microprocessoreInformatica 5 Liceo Scientifico Scienze Applicate/Sistemi a microprocessore
** Blocchi di condizionamento e Teorema di ShannonInformatica 5 Liceo Scientifico Scienze Applicate/Blocchi di condizionamento e Teorema di Shannon
** Un po' di elettronicaInformatica 5 Liceo Scientifico Scienze Applicate/Un po' di elettronica
** Esempi applicativi μP-μCInformatica 5 Liceo Scientifico Scienze Applicate/Esempi applicativi μP-μC
** AutomiInformatica 5 Liceo Scientifico Scienze Applicate/Automi
** Distributore BibiteInformatica 5 Liceo Scientifico Scienze Applicate/Distributore Bibite
** Sistemi Lineari e RetroazionatiInformatica 5 Liceo Scientifico Scienze Applicate/Sistemi Lineari e Retroazionati
** Simulazione Sistema Retroazionato
** Esempio Lancio del PesoInformatica 5 Liceo Scientifico Scienze Applicate/Esempio Lancio del Peso
Modifica il sommario

## Algoritmi

Un algoritmo e' la tecnica/procedimento utilizzato per risolvere una specifica classe di problemi ad esempio :
Un algoritmo nell'ambito informatico e' un codice che risolve con efficienza un particolare problema, per un matematico la definizione di algoritmo e' mirata a garantire l'effettiva computabilita' del metodo
La "bellezza" di un algoritmo spesso e' legata ai soli tempi di elaborazione cioe' a quanto velocemente riesce a risolvere un certo problema , in altri casi alla scelta della struttura dati utilizzata per formalizzare il problema (scelta del modello) e alla eleganza logica della tecnica risolutiva (chiarezza del codice e compattezza dello stesso).
Il termine algoritmo deriva dalla latinizzazione del nome del matematico persiano Al-Khwārizmī che scrisse un libro sulle regole per il calcolo aritmetico usando il sistema di numerazione indiano-arabo nel 12° secolo.
Vediamo un semplice algoritmo che permette di ordinare gli elementi di un vettore :
Per ordinare gli elementi di un vettore dal piu' piccolo al piu' grande si possono usare diversi algoritmi, quello piu' semplice da spiegare e' il BubbleSort e quello piu' veloce e' il QuickSort. Un algoritmo e' un particolare programma che risolve una classe di problemi (nel nostro caso l'ordinamento degli elementi di un vettore) con una certa efficienza ( generalmente espressa in termini di velocita' di calcolo).

## Bubblesort

Per ordinare un vettore di n elementi bisogna fare n-1 passate, ad ogni passata l'elemento piu' piccolo rimasto nella parte di vettore ancora da ordinare viene spostato nella posizione corretta, per ordinare il vettore bastano n-1 passate perché sistemati i primi n-1 elementi anche l'ultimo numero e' per forza di cose al posto giusto. In una singola passata , pensiamo sia la passata i-esima si prendono in considerazione tutti gli elementi partendo dall'ultimo (indice n-1) fino a quello con l'indice con lo stesso numero della passata, ogni elemento considerato ad esempio quello k-esimo viene confrontato con quello che lo precede k-1-esimo e se vett[k] < vett[k-1] i due elementi del vettore si scambiano fra loro , altrimenti si passa a considerare l'elemento successivo. Facciamo un esempio , vettore di 6 elementi , passate da fare 5, nella prima passata si ha
come si vede, alla fine della prima passata il vettore e' composto da due parti una ordinata (colore verde) che contiene il numero piu' piccolo (2) e una che deve essere ancora ordinata, la seconda passata si occupa di ordinare soltanto di quest'ultima, si vede che per fare la prima passata bisogna considerare via via gli elementi in giallo con il corrispondente elemento che lo precede, sono queste coppie di valori che vengono confrontate ed eventualmente scambiate fra loro. Nella seconda passata si ha:
il vettore ordinato e' composto ora da due numeri e il vettore da ordinare e' diventato piu' piccolo, si nota che il numero di confronti che si devono fare si riduce di conseguenza di una unità ad ogni passata.Vediamo la passata 3
Vediamo la passata 4
vediamo la passata 5
si nota che durante la passata 4 non ci sono stati scambi , quando non ci sono scambi durante tutta una passata il vettore risulta ordinato e ele passate successive non sono piu' necessarie, in questa spiegazione e nel programma seguente non utilizzeremo questa particolarita' che consente di velocizzare la fine dell'algoritmo.
Il programma e' caratterizzato da un primo ciclo for che conta le passate ( conta da 1 ) e all'interno della singola passata c'e un secondo for che prende in analisi i diversi elementi J (partendo dal fondo n-1 fino a quello di indice pari al numero della passata) che devono essere confrontati con l'elemento del vettore che lo precede J-1 , si nota poi la necessita' dell'uso della variabile temp per poter scambiare due celle di un vettore senza perdersi uno dei valori delle celle. In questo programma l'ordinamento e' fatto su un vettore di stringhe (parole), in questo caso l'ordinamento e' quello alfabetico (antonella minore di zorro)
BubbleSort
In Octave
L'efficienza di un algoritmo viene espressa con l'ordine di complessita', generalmente esso dipende dal numero n di elementi del vettore, se le operazioni da fare per completare l'algoritmo fossero proporzionali al numero di elementi del vettore l'odine di complessità sarebbe indicato come $O(n)$ e si legge O grande di n. Nel caso del bubblesort le cose vanno peggio di O(n) e i calcoli da farsi sono proporzionalia a $n^{2}$ secondo un fattore di proporzionalita' di 0.5 si ha allora $O({\frac {n^{2}}{2}})$. Per il quicksort l'ordine di complessita' e' del $O(n\log _{2}n)$ , meglio del bubblesort ma peggio di un andamento solamente proporzionale ad n . Vediamo in un grafico l'andamento delle istruzioni da effettuare in 3 casi diversi di complessita'