INFORMATICA

MATTEO CRISTANI

INDICE CICLO DELLE LEZIONI

LEZ. 1INTRODUZIONE AL CORSO

LEZ. 2I CALCOLATORI ELETTRONICI

LEZ. 3ELEMENTI DI TEORIA DELL’INFORMAZIONE

LEZ. 4MISURE DELLA INFORMAZIONE

LEZ. 5CALCOLO BINARIO: CONVERSIONI DI BASE

LEZ. 6CALCOLO BINARIO: OPERAZIONI IN BASE 2

LEZ. 7ESERCITAZIONE DI CALCOLO BINARIO

LEZ. 8ESERCITAZIONE DI CALCOLO BINARIO

LEZ. 9PORTE LOGICHE

LEZ. 10PROGETTO DI CIRCUITI DIGITALI

LEZ. 11INTRODUZIONE AGLI ALGORITMI

LEZ. 12PRODUTTIVITA’ INDIVIDUALE

LEZ. 13IL WEB

LEZ. 14RICERCA DI DOCUMENTI

LEZ. 15USO DEI MOTORI DI RICERCA

LEZ. 16SICUREZZA INFORMATICA

LEZ. 17ELEMENTI DI CRITTOGRAFIA

LEZ. 18ESERCITAZIONE DI CRITTOGRAFIA

LEZ. 19ESERCITAZIONE GENERALE

LEZ. 20SOMMARIO 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. le loro proprietà formali e matematiche;2. le loro implementazioni hardware;3. le loro implementazioni linguistiche;4. le loro 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’

Elaborano terne di valori (probabilmente all’interno di tre cicli nidificati).

N3

Risolvono alcuni problemi di interesse pratico per i quali non si conoscono ancora algoritmi non esponenziali.

2N

Elaborano gli elementi dell’input a coppie (probabilmente all’interno di due cicli nidificati).

N2

Suddividono il problema in sottoproblemi più piccolo che vengono risolti indipendentemente.

NlogN

Eseguono poche operazioni su ciascun elemento dell’input.

N

Risolvono grossi problemi riducendone la dimensione di un fattore costante.

logN

Tipologia di algoritmoTempo di esecuzione

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)

PSEUDOCODICEUtilizzare 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.

ESEMPIOEsempio moltiplicazione per somme

Problema: dati due numeri interi a e b maggiori o uguali a 0,determinarne il prodotto p.

1. p 02. se b=0 vai all’istruzione 63. p p+a4. b b-15. vai all’istruzione 26. fine

TERMINAZIONEATTENZIONE!

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. r 02. r r+13. vai all’istruzione 24. fine

Manca la condizione di uscita dal ciclo!

DIAGRAMMI DI FLUSSOUn 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,..,ino1,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

O

Then Else

ESEMPIO CALCOLO DEL FATTORIALE N!=N*(N-1)*(N-2)*…*2