Fondamenti di Algoritmi -...

Politecnico di Milano

Fondamenti di Algoritmi

Corsi di Informatica Grafica Prof. Manuel Roveri Dipartimento di Elettronica e Informazione [email protected]

Politecnico di Milano Indice

�  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

Politecnico di Milano Algoritmi 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#)

Politecnico di Milano Elaboratore 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.

Politecnico di Milano Algoritmo 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 Ingresso Esecutore Risultati

Algoritmo

Politecnico di Milano Proprietà 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

Politecnico di Milano 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

Politecnico di Milano Descrizione 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 ....

Politecnico di Milano DIAGRAMMA 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

Politecnico di Milano Blocchi Elementari

Politecnico di Milano Strutture 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

Sequenza


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

Selezione


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

Ripetizione

�  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 a descrivere 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öhm-Jacopini

Politecnico di Milano Considerazioni 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

Politecnico di Milano Programmazione

�  Linguaggi di programmazione �  Fasi della programmazione �  Paradigmi di programmazione �  Costrutti elementari di un linguaggio di programmazione

Politecnico di Milano Il 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

Politecnico di Milano Le 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)

Politecnico di Milano I 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

halt 4

Politecnico di Milano Programmi 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

Politecnico di Milano Un 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

Politecnico di Milano Contenuto della memoria

Politecnico di Milano Le istruzioni del programma

Politecnico di Milano Il 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

Politecnico di Milano L’esempio in linguaggio assembly

READ 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

Politecnico di Milano I 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

Politecnico di Milano Linguaggi di alto livello: Quali

�  COBOL (COmmon Business Oriented Language) �  LISP, PROLOG �  Fortran (FORmula TRANslator) �  Pascal �  Basic �  C / C++ �  JAVA �  C# �  …

Politecnico di Milano Fasi della programmazione

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

◦  editazione ◦  compilazione ◦  linking (collegamento) ◦  caricamento ◦  esecuzione

Politecnico di Milano Fase 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

Politecnico di Milano Fase 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

Politecnico di Milano 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

Politecnico di Milano Fase 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

Politecnico di Milano Linguaggi 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 -...

Documents

Transcript of Fondamenti di Algoritmi -...