Fondamenti di Algoritmi - Intranet DEIBhome.deib.polimi.it/.../4_Fondamenti_di_Algoritmi.pdf ·...

Politecnicodi Milano

Fondamenti di AlgoritmiFondamenti di Algoritmi

Corsi di Informatica Grafica

Prof. Manuel Roveri

Dipartimento di Elettronica e [email protected]


IndiceIndice

Algoritmi:◦ Definizione

◦ Diagrammi di Flusso

◦ Esempi ed esercizi

Programmazione◦ Paradigmi di programmazione

◦ Costrutti elementari di un linguaggio di programmazione

◦ Linguaggi di programmazione

◦ Fasi della programmazione


Algoritmi ed Informatica GraficaAlgoritmi ed Informatica Grafica

Perchè affrontare gli algoritmi in un corso di

informatica grafica?

◦ Il mondo della grafica è fatto ad algortmi

◦ Programmare Autocad

Perchè il linguaggio C?

◦ Più utilizzato e facile da imparare

◦ Orientato agli algoritmi

◦ Permette di avere le basi per poter studiare uno specifico linguaggio

per Autocad (ad es , Visual Basic, .Net, C#)


Elaboratore come risolutore di problemiElaboratore come risolutore di problemi

La risoluzione di un problema è il processo

che dato un problema ed individuato un

opportuno metodo risolutivo trasforma i dati

iniziali nei corrispondenti risultati finali.

Affinchè la risoluzione di un problema possa

essere realizzata attraverso l’uso del calcolatore,

tale processo deve poter essere definito come

sequenza di azioni elementari.


Algoritmo ed EsecutoreAlgoritmo ed Esecutore

Un algoritmo è una sequenza finita di azioni

che risolve in un tempo finito una classe di

problemi.

Esecutore: macchina astratta capace di

eseguire le azioni specificate dall’algoritmo

Dati in

IngressoEsecutore Risultati

Algoritmo


Proprietà degli algoritmiProprietà degli algoritmi

Eseguibilità: ogni azione deve essere

eseguibile dall’esecutore in un tempo finito.

Non-ambiguità: ogni azione deve essere

univocamente interpretabile dall’esecutore

Finitezza: il numero totale di azioni da

eseguire, per ogni insieme di dati di

ingresso, deve essere finito


Esempi (1/3)Esempi (1/3)

Soluzione dell’equazione ax+b=0

1. leggi i valori di a e b

2. calcola calcola -b

3. dividi quello che hai ottenuto per a e chiamalo x

4. stampa x



Calcolo del massimo di un insieme

1. Scegli un elemento come massimo provvisorio

2. Per ogni elemento i dell’insieme: se i>max eleggi i

come nuovo massimo provvisorio max

3. Il risultato è max



Stabilire se una parola P viene alfabeticamente prima di

una parola Q

1. leggi P,Q

2. ripeti quanto segue:

3. se prima lettera di P < prima lettera Q allora scrivi vero

4. altrimenti se prima lettera P > prima lettera Q

allora scrivi falso

5. altrimenti (le lettere sono =)

6. togli da P e Q la prima lettera

7. fino a quando hai trovato le prime lettere diverse


Descrizione di algoritmiDescrizione di algoritmi

Un algoritmo viene descritto mediante:

◦ azioni elementari: descrivono operazioni “semplici”

◦ strutture di controllo: descrivono quali azioni devono

essere eseguite, e/o in quale ordine

ESEMPI DI STRUTTURE DI CONTROLLO:

◦ Se .... allora .... altrimenti ....

◦ Finché .... esegui ....

◦ Torna al passo ....


DIAGRAMMA A BLOCCHI: Grafi di FlussoDIAGRAMMA A BLOCCHI: Grafi di Flusso

Ambiguita' del linguaggio naturale

Per definire algoritmi si usano i grafi di flusso (flowchart)

E’ un linguaggio formale di tipo grafico per rappresentare gli

algoritmi

◦ Attraverso il diagramma a blocchi si può indicare l’ordine di

esecuzione delle istruzioni.

◦ Un particolare simbolo grafico detto blocco elementare è associato ad

ogni tipo di istruzione elementare.

◦ I blocchi sono collegati tra loro tramite frecce che indicano il

susseguirsi delle istruzioni


Blocchi Elementari Blocchi Elementari


Strutture di controlloStrutture di controllo

La programmazione in un linguaggio di alto livello è basata su tre strutture di controllo:

◦ Sequenza

◦ Selezione

◦ Ripetizione

Sequenza: serie di istruzioni che vengono eseguite una dopo l’altra

Selezione: viene posta una condizione, se la condizione è verificata viene eseguito un blocco di istruzioni, altrimenti ne viene eseguito un altro

Ripetizione: uno stesso blocco di istruzioni viene eseguito a ripetizione fino a quando non viene verificata la condizione di uscita dal ciclo


Istruzione 1

Istruzione 2

Istruzione N

Esempio:

• Leggi un numero da tastiera

• Moltiplicalo per 2

• Stampalo a video

SequenzaSequenza


Istruzione 1

Istruzione 2

Esempio:


• Condizione: è un numero

positivo?

• Se la condizione è verificata

si incrementa il numero,

altrimenti lo si decrementa

• Si stampa a video il numero

Condizione

Istruzione 3

Istruzione 4

SelezioneSelezione


Istruzione 1

Istruzione 2

Esempio:


• Decrementalo di 1

• Condizione uscita: il numero

è uguale a 0?

• se la condizione è verificata il

programma esce dal ciclo,

altrimenti lo ripete

Condizione uscita

RipetizioneRipetizione

Un ciclo è detto enumerativo quando è noto a priori il numero di volte che deve essere eseguito

◦ si usa una variabile detta contatore del ciclo che viene incrementata (o decrementata) fino a raggiungere un

valore prefessato

Un ciclo è indefinito quando non è noto a priori il numero di volte che deve essere eseguito

◦ questo accade quando la condizione di fine ciclo dipende dal valore di una o più variabili che dipendono

dall’interazione con l’esterno o vengono modificate all’interno dell’iterazione in modo complesso


I tre costrutti fondamentali sono sufficienti aI tre costrutti fondamentali sono sufficienti aI tre costrutti fondamentali sono sufficienti aI tre costrutti fondamentali sono sufficienti a

descrivere qualunque algoritmodescrivere qualunque algoritmo

Detto in altre parole:

dato un problema di complessità finita, è sempre possibile scrivere l’algoritmo

che lo risolve utilizzando opportunamente i tre costrutti fondamentali

presentati nei paragrafi precedenti

Per semplificare possiamo dire che un problema ha complessità finita quando

esiste una soluzione calcolabile in un tempo finito

E’ ad esempio impossibile scrivere un programma in grado di indovinare con

esattezza la schedina del totocalcio, o i numeri del lotto (queste funzioni non

sono calcolabili)

Teorema di BöhmTeorema di Böhm--JacopiniJacopini


Considerazioni su diagramma a blocchiConsiderazioni su diagramma a blocchi

Un diagramma a blocchi `e un insieme di blocchi

costituito da:

◦ un blocco iniziale

◦ un numero finito n >= 1 di blocchi azione e/o blocchi di

lettura/scrittura

◦ un numero finito m >= 0 di blocchi di controllo

◦ un blocco finale

Condizioni di validità:ciascun blocco è raggiungibile dal blocco iniziale

il blocco finale è raggiungibile da qualsiasi altro blocco


ProgrammazioneProgrammazione

Linguaggi di programmazione

Fasi della programmazione

Paradigmi di programmazione

Costrutti elementari di un linguaggio di programmazione


Il linguaggio del calcolatoreIl linguaggio del calcolatore

Il calcolatore esegue programmi scritti in un

opportuno linguaggio: il linguaggio macchina

Tale linguaggio differisce nei suoi dettagli da

calcolatore a calcolatore

◦ Da processore a processore


Le istruzioni macchinaLe istruzioni macchina

Un programma scritto in linguaggio macchina è formato da

una sequenza di istruzioni appartenenti al set di istruzioni del

particolare processore

Ogni istruzione è formata da:

◦ Un codice operativo

◦ Zero o più operandi

Tanto il codice operativo quanto gli operandi sono

rappresentati nella memoria del calcolatore sotto forma di

numeri binari

Data la difficoltà per l’uomo di interpretare numeri binari si

usa l’assembler al posto del linguaggio macchina

codice operativo operando(i)


I programmiI programmi

Un programma consiste di

due parti

◦ La parte istruzioni

contenente il codice del

programma

◦ La parte dati costituita dalle

celle di memoria destinate a

contenere i dati sui quali il

programma opera

◦ Il processore esegue un

programma dalla prima

istruzione fino all’istruzione halt

LOAD 4, R1

LOAD 5, R2

SUB R1, R2

STORE R1, 7

50

40

0

1

2

3

5

6

istruzioni

dati

halt4


Programmi vs. processiProgrammi vs. processi

Un programma è un entità statica

◦ Descrive semplicemente un algoritmo

Con il termine processo si indica un

programma in esecuzione

◦ Caratterizzato dal codice in esecuzione e da uno

stato

Lo stato di un processo è descritto dal valore assunto

dalla sezione dati del programma e dai valori assunti dai

registri del processore

programma : processo = ricetta : attività del cucinare


Un esempio di programmaUn esempio di programma

Esempio: calcolare espressione (a + b) * (c + d)

◦ Poni in memoria centrale, nelle celle 16, 17, 18 e 19 i valori di a, b, c, e d;

◦ Esegui l’addizione di a e b:

Copia cella 16 in registro A

Copia cella 17 in registro B

Somma i due registri (l’operazione è eseguita dalla ALU)

◦ Immagazzina risultato (ora in registro A) nella cella 20

◦ Esegui l’addizione di c e d:

Copia cella 18 in registro A

Copia cella 19 in registro B

Somma i registri (l’operazione è eseguita dalla ALU)

◦ Esegui la moltiplicazione di (a + b) e (c + d):

Copia in registro B cella 20

Moltiplica il contenuto dei due registri

◦ Scrivi il risultato sul dispositivo di uscita:

Memorizza registro A, nella cella 20

Scrivi cella 20 nel registro dati della periferica

◦ Arresta l’esecuzione del programma


Contenuto della memoriaContenuto della memoria


Le istruzioni del programmaLe istruzioni del programma


Il linguaggio AssemblyIl linguaggio Assembly

La programmazione in linguaggio macchina è troppo

complessa e noiosa per i programmatori

Al posto delle sequenze di numeri, è più comodo usare delle

abbreviazioni simili all’inglese per rappresentare le operazioni

elementari: Nasce il linguaggio Assembly

È necessario un programma (assembler) che traduca in

linguaggio macchina i programmi scritti in linguaggio assembly


L’esempio in linguaggio assemblyL’esempio in linguaggio assemblyREAD A

READ B

READ C

READ D

LOADA A

LOADB B

ADD

STOREA RIS

LOADA C

LOADB D

ADD

LOADB RIS

MUL

STOREA RIS

WRITE RIS

HALT

INT A

INT B

INT C

INT D

INT RIS


I linguaggi di alto livelloI linguaggi di alto livello

La programmazione in linguaggio macchina è improponibile

per programmi di una certa complessità...

... e l’assembly oltre un certo limite non aiuta

I linguaggi di alto livello facilitano la programmazione dei

calcolatori

“Alto livello” = “Vicino al programmatore”

Ovviamente è necessario un programma

(compilatore) che converta il programma scritto

nel linguaggio di alto livello

in linguaggio macchina


Linguaggi di alto livello: QualiLinguaggi di alto livello: Quali

COBOL (COmmon Business Oriented Language)

LISP, PROLOG

Fortran (FORmula TRANslator)

Pascal

Basic

C / C++

JAVA

C#

…


Fasi della programmazioneFasi della programmazione

La preparazione di un programma scritto in un linguaggio ad alto livello, passa tra diverse fasi:

◦ editazione

◦ compilazione

◦ linking (collegamento)

◦ caricamento

◦ esecuzione


Fase di editazioneFase di editazione

Consiste nella scrittura del codice (testo del

programma) in un file

Si esegue tramite un programma chiamato

editor o Ambiente di sviluppo

Genera il programma sorgente


Fase di compilazioneFase di compilazione

Il codice sorgente viene passato al compilatore

che si occuperà di tradurre il programma nel

codice in linguaggio macchina

Genera il programma oggetto


Fase di linking (collegamento)Fase di linking (collegamento)

I programmi scritti in linguaggio ad alto livello, contengono

dei riferimenti a funzioni definite altrove

◦ Nelle librerie del linguaggio e/o del sistema operativo

Il codice oggetto prodotto dal compilatore conterrà dei

“buchi” (riferimenti alle funzioni di libreria)

Il linker si occupa di collegare il codice oggetto con quello

delle funzioni mancanti

Genera il programma eseguibile


Fase di Caricamento / EsecuzioneFase di Caricamento / Esecuzione

Fase di caricamento

◦ Prima che possa essere eseguito, un programma

dovrà essere caricato in memoria

◦ Il programma loader (parte del sistema operativo)

si occupa di questa operazione

Fase di esecuzione

◦ Il computer esegue il programma, una istruzione

per volta


Linguaggi compilati e interpretatiLinguaggi compilati e interpretati

Il calcolatore “capisce” solo il linguaggio macchina

I programmi scritti in linguaggi di alto livello devono

essere tradotti in linguaggio macchina prima di

essere eseguiti

◦ Di ciò si occupa il compilatore

In alternativa alcuni linguaggi di alto livello hanno

associato un interprete

◦ Si tratta di un programma capace di “capire” quel

particolare linguaggio e di eseguirne i programmi

◦ Un’istruzione per volta

Fondamenti di Algoritmi - Intranet DEIBhome.deib.polimi.it/.../4_Fondamenti_di_Algoritmi.pdf ·...

Documents

Transcript of Fondamenti di Algoritmi - Intranet DEIBhome.deib.polimi.it/.../4_Fondamenti_di_Algoritmi.pdf ·...