Informatica

Algoritmo e variabile

Lo pseudocodice è una descrizione informale di una sequenza di passi che portano alla soluzione di un problema.

Algoritmo

Un algoritmo che risolve un problema è una sequenza di passi non ambigua, eseguibile e che termina in un tempo finito.

Creazione di un algoritmo

• Determinare i dati disponibili (ingressi) e i risultati da produrre (uscite).
• Scomporre il problema in compiti più semplici.
• Descrivere ciascun sotto-problema mediante pseudocodice.
• Collaudare lo pseudocodice in casi specifici.

Un algoritmo (o procedura risolutiva) specifica come ottenere il risultato finale mediante una sequenza di istruzioni (Ordini).

Attenzione

• Un algoritmo non è l’esecuzione materiale delle azioni volte a raggiungere il risultato finale che invece è affidata ad un esecutore.
• L’esecuzione delle azioni atte ad eseguire un algoritmo è detto processo.

Gli algoritmi hanno una complessità differente che fa diventare la sua risoluzione più veloce. La complessità in generale viene calcolata come funzione del valore e della lunghezza dall'input C = f(n), dove n è il parametro che misura l'input.

Complessità

Le complessità possono essere di tipo:

• Spaziale: Spazio necessario ad un algoritmo per risolvere un particolare problema.
• Temporale: Tempo necessario ad un algoritmo per risolvere un particolare problema.

La complessità temporale viene calcolata in numero di operazioni (indipendente dalla macchina usata). La complessità viene calcolata sul caso peggiore, ovvero che fa impiegare il maggior tempo ad un algoritmo. La complessità peggiore si indica con O (valore), dove il valore n rappresenta la grandezza dell’input.

Come capire se un algoritmo è migliore di un altro?

• Possiamo guardare come è scritto? [guardiamo le istruzioni dell’algoritmo]
  • Comprensibilità
  • Numero di istruzioni
• Possiamo guardare le sue ipotetiche esecuzioni? [guardiamo i possibili processi]
  • Numero di passi da fare a seconda dei parametri di ingresso

Processo

Il processo è l’applicazione degli algoritmi.

Complessità asintotica

Si dice che f(n) ha complessità asintotica g(n) se valgono le seguenti condizioni:

• f(n) = O(g(n))
• g(n) è la più piccola di tutte le funzioni che soddisfano la prima condizione.

Complessità di alcune operazioni

• Complessità O(n): "La ricerca lineare esamina tutti i valori di una lista una sola volta finché non trova una corrispondenza con quanto cercato oppure raggiunge la fine della lista."
• Complessità O(log(n)): "La ricerca binaria cerca un valore in una lista ordinata determinando se si trova nella prima o nella seconda metà della lista stessa, ripetendo la ricerca in una sola delle due metà."
• Complessità O(n²): "Un ciclo che esegue n iterazioni ciascuna delle quali richiede un tempo O(n)."

Metodo Pallottoliere

Dati i due numeri A e B:

• Si metta in A ciò che si ottiene facendo A + 1.
• Si metta in B ciò che si ottiene facendo B – 1.
• Se B non è uguale a 0 allora si torni al passo 1) altrimenti A contiene la somma tra l’originale A e l’originale B.

Metodo normale

Dati due numeri A e B:

• Scrivere A e scrivere B di modo che le unità stiano una sotto l’altra.
• Si scriva dopo il numero A il simbolo + e dopo il numero B il simbolo =.
• Si tracci una linea sotto il numero B.
• Considerare la colonna delle unità come colonna attiva.
• Se nella colonna attiva non ci sono cifre da sommare ci si fermi, si è ottenuto il risultato.
• Si sommino le cifre della colonna attiva e si scriva l’unità sotto le due cifre considerate e l’eventuale decina sopra le cifre della colonna successiva a quella attiva.
• Si sposti la colonna attiva alla colonna successiva sulla sinistra.
• Si torni al passo 5).

L’algoritmo Pallottoliere occorrono proprio B passi per sommare i due numeri, mentre con il metodo normale, dato N il numero di cifre di B, occorrono N+1 passi per sommare i due numeri.

Complessità asintotica: Si dice che f(n) ha complessità asintotica g(n) se valgono le seguenti condizioni:

• f(n) = O(g(n))
• g(n) è la più piccola di tutte le funzioni che soddisfano la prima condizione.

Rappresentazione

Una rappresentazione si stabilisce tra:

• Significato: Un oggetto da rappresentare.
• Significante: Un simbolo (potenzialmente complesso) che lo rappresenta.

Disponiamo di due tipi di rappresentazione:

• Pittorica
  • Analogica, simboli non separati.
  • Nessun chiaro simbolo di relazione.
  • Nessuna regola canonica.
  • Concreta.
• Linguistica
  • Non-analogica.
  • Simboli discreti.
  • Chiari simboli di connessione.
  • Composizione secondo regole grammaticali.
  • Astratta.

In un algoritmo per produrre una macchina in grado di elaborarlo, ci interessa rappresentare:

• Parametri di ingresso.
• Dati parziali.
• Azioni/Istruzioni.

Variabile

Una variabile è uno spazio di memoria; una posizione, all’interno della memoria del computer, in cui si possono archiviare informazioni durante l’esecuzione di un programma. Ogni variabile ha un proprio nome.

In informatica procedurale la variabile è uno spazio di memoria in cui il valore può cambiare.

Es: X=6 → X=X+1 → N.B. = sta a significare l’azione di assegnamento, ovvero scrivere nella variabile il suo valore.

• Operazioni matematiche:
• + Addizione
• - Sottrazione
• * Moltiplicazione
• / Divisione
• ** Potenza
• % Resto
• // Divisione intera
• Funzioni matematiche:
• abs() Valore assoluto
• round() Valore arrotondato ad un numero intero
• max() Maggiore
• min() Minore
• sqrt() Radice quadrata
• trunc() Tronca il valore del numero restituendo un intero
• cos() Coseno in radianti
• sin() Seno in radianti