INFORMATICA
MATTEO CRISTANI
INDICE

CICLO DELLE LEZIONI
LEZ. 1
LEZ. 2
LEZ. 3
LEZ. 4
LEZ. 5
INTRODUZIONE AL
CORSO
I CALCOLATORI
ELETTRONICI
ELEMENTI DI
TEORIA DELL’
INFORMAZIONE
MISURE DELLA
INFORMAZIONE
CALCOLO BINARIO:
CONVERSIONI DI
BASE
LEZ. 6
LEZ. 7
LEZ. 8
LEZ. 9
LEZ. 10
CALCOLO BINARIO:
OPERAZIONI IN
BASE 2
ESERCITAZIONE DI
CALCOLO BINARIO
ESERCITAZIONE DI
CALCOLO BINARIO
PORTE LOGICHE
PROGETTO DI
CIRCUITI DIGITALI
LEZ. 11
LEZ. 12
LEZ. 13
LEZ. 14
LEZ. 15
INTRODUZIONE
AGLI ALGORITMI
PRODUTTIVITA’
INDIVIDUALE
IL WEB
RICERCA DI
DOCUMENTI
USO DEI MOTORI
DI RICERCA
LEZ. 16
LEZ. 17
LEZ. 18
LEZ. 19
LEZ. 20
SICUREZZA
INFORMATICA
ELEMENTI DI
CRITTOGRAFIA
ESERCITAZIONE DI
CRITTOGRAFIA
ESERCITAZIONE
GENERALE
SOMMARIO DEL
CORSO
AGENDA



DEFINIZIONE DI ALGORITMO
APPROCCIO AL PROGETTO DI ALGORITMI
MISURE SUGLI ALGORITMI
DEFINIZIONE DI ALGORITMO

Algoritmo: un insieme ordinato di operazioni non
ambigue ed effettivamente computabili che, quando
eseguito, produce un risultato e si arresta in un tempo
finito.

In termini informali, un algoritmo è una sequenza ordinata
di operazioni che risolve un problema specifico.

Se questa idea aveva una certa importanza per il calcolo
matematico, l'avvento dell'informatica l'ha arricchita di
nuovi significati..
DEFINIZIONE DI ALGORITMO

.. tanto che, con molta enfasi, è stata data
anche la seguente definizione di informatica:

L’informatica è lo studio degli algoritmi, che
comprende:
1.
2.
3.
4.
le
le
le
le
loro
loro
loro
loro
proprietà formali e matematiche;
implementazioni hardware;
implementazioni linguistiche;
applicazioni.
CIO’ CHE NON E’ ALGORITMO

L’opposto di algoritmo: euristica.

Si definisce infatti procedimento euristico
un metodo di approccio alla soluzione dei
problemi che non segue un chiaro
percorso, ma si affida all'intuito e allo
stato temporaneo delle circostanze, al
fine di generare nuova conoscenza.
CONCETTI BASE DI PROGRAMMAZIONE

Tutte le operazioni utilizzate per realizzare algoritmi rientrano in una delle
seguenti tre categorie:

Operazioni sequenziali

Un’istruzione sequenziale esegue una singola attività ben definita. Terminata
l’attività, l’algoritmo passa all’operazione successiva. Solitamente le operazioni
sequenziali sono espresse come semplici frasi dichiarative.

Operazioni condizionali

Si tratta delle istruzioni di un algoritmo che “pongono una domanda”. L’operazione
successiva è selezionata sulla base della risposta fornita alla domanda.

Operazioni iterative

Si tratta delle istruzioni “di ciclo” di un algoritmo. Indicano di non proseguire con
l’istruzione successiva, ma di tornare indietro e ripetere l’esecuzione di un
precedente blocco di istruzioni.
PROPRIETA’ DEGLI ALGORITMI

Un algoritmo deve essere:

non ambiguo (i risultati non devono variare in funzione della macchina o
persona che esegue l'algoritmo)

corretto (deve risolvere un dato problema)

realizzabile (deve essere eseguibile con le risorse a disposizione)

finito (deve essere composto da un numero finito di passi elementari; le
operazioni sono eseguite un numero finito di volte)

efficiente (deve avere un costo accettabile, se non ottimo, in termini di
risorse consumate: tempo di CPU richiesto per completare, quantità di
memoria utilizzata, quantità di bit trasferiti)
ATTRIBUTI DI UN ALGORITMO

Correttezza

Facilità di comprensione

Eleganza

Efficienza

Talvolta eleganza e facilità di comprensione vanno
in direzioni contrarie: più elegante è la soluzione,
più difficile risulta da capire.
EFFICIENZA

Efficienza è il termine usato per descrivere l’uso attento delle
risorse da parte di un algoritmo.

Come si misurano il tempo e lo spazio consumati da un algoritmo,
in modo da determinare se è efficiente?

L’efficienza rispetto allo spazio si può giudicare in base alla
quantità di informazioni che l’algoritmo deve registrare nella
memoria del computer per svolgere il proprio compito, oltre ai dati
iniziali sui quali opera.

L’efficienza rispetto al tempo di un algoritmo è un’indicazione della
quantità di “lavoro” richiesto dall’algoritmo stesso. È una misura
dell’efficienza implicita del metodo, indipendente dalla velocità
della macchina su cui è eseguito, dai valori dei dati di ingresso
elaborati ma non dalla loro quantità.
MISURE DELLA COMPLESSITA’
Tempo di
esecuzione
Tipologia di algoritmo
logN
Risolvono grossi problemi riducendone la
dimensione di un fattore costante.
N
Eseguono poche operazioni su ciascun elemento
dell’input.
NlogN
Suddividono il problema in sottoproblemi più
piccolo che vengono risolti indipendentemente.
N2
Elaborano gli elementi dell’input a coppie
(probabilmente all’interno di due cicli nidificati).
2N
Risolvono alcuni problemi di interesse pratico per
i quali non si conoscono ancora algoritmi non
esponenziali.
N3
Elaborano terne di valori (probabilmente
all’interno di tre cicli nidificati).
DESCRIZIONE DI UN ALGORITMO

•


•


Il linguaggio di descrizione di un algoritmo deve essere
adeguato alle caratteristiche del suo esecutore.
esecutore umano:
- linguaggio naturale (eventualmente strutturato)
- linguaggio grafico (es. diagrammi di flusso)
calcolatore (esecutore automatico):
- linguaggio di programmazione
(programma = specifica di una computazione)
PSEUDOCODICE
Utilizzare un insieme di istruzioni per MT per descrivere un algoritmo
non è certamente agevole.
Molti studiosi di informatica utilizzano una notazione denominata
pseudocodice per progettare e rappresentare gli algoritmi. Si tratta
di costrutti in simil-linguaggio naturale studiati per assomigliare alle
istruzioni di un linguaggio di programmazione, ma che in realtà non
si eseguono su un computer.
Lo pseudocodice rappresenta un compromesso tra i due estremi del
linguaggio naturale e di quello formale; è semplice, altamente
leggibile e praticamente privo di regole grammaticali.
ESEMPIO
Esempio
moltiplicazione per somme
Problema: dati due numeri interi a e b maggiori o uguali a 0,
determinarne il prodotto p.
1.
2.
3.
4.
5.
6.
p0
se b=0 vai all’istruzione 6
p  p+a
b  b-1
vai all’istruzione 2
fine
TERMINAZIONE
ATTENZIONE!
Il fatto che il numero di istruzioni presenti nella descrizione di
un
algoritmo sia finito non implica necessariamente che
l’algoritmo
termini in un tempo finito!
1.
2.
3.
4.
r0
r  r+1
vai all’istruzione 2
fine
Manca la condizione di uscita dal ciclo!
DIAGRAMMI DI FLUSSO
Un diagramma di flusso (flow chart) è la rappresentazione
grafica dei
passi che costituiscono un algoritmo.
E’ uno strumento efficace per la descrizione degli algoritmi.
I diagrammi di flusso usano forme geometriche diverse per
rappresentare:
 trasferimento di informazioni (lettura dati, scrittura
risultati, visualizzazione dati intermedi)
 esecuzione di calcoli
 assunzione di decisioni
 esecuzione di iterazioni (ripetizione di sequenze di
operazioni)
Simboli convenzionali:
Elaborazione – I blocchi rettangolari possono rappresentare
istruzioni di assegnamento o più in generale istruzioni che
comportano una qualche modifica dello stato globale della
computazione.
Decisione – I blocchi a forma di rombo vengono utilizzati per
rappresentare istruzioni di salto condizionato.
Inizio/fine – I blocchi ovali vengono utilizzati per
rappresentare l’inizio e la fine dell’algoritmo.
SIMBOLI
vE
B
i1,i2,..,in
o1,o2,..,on
WHILE-DO

Ciclo di esecuzione di una istruzione
I
O
REPEAT-UNTIL

Ciclo con condizione d’uscita
I
O
IF-THEN-ELSE

Selezione tra due istruzioni sulla base di una condizione
I
Then
Else
O
ESEMPIO


CALCOLO DEL FATTORIALE
N!=N*(N-1)*(N-2)*…*2