Post on 15-Feb-2019
Politecnico di Milano
Fondamenti di AlgoritmiFondamenti di Algoritmi
Corsi di Informatica Grafica
Prof. Manuel Roveri
Politecnico di Milano 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
Politecnico di Milano 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#)
Politecnico di Milano 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.
Politecnico di Milano 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 Ingresso Esecutore Risultati
Algoritmo
Politecnico di Milano 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
Politecnico di Milano Esempi (1/3)Esempi (1/3)
Soluzione dell’equazione ax+b=01. leggi i valori di a e b2. calcola calcola -b3. dividi quello che hai ottenuto per a e chiamalo x4. stampa x
Politecnico di Milano Esempi (2/3)Esempi (2/3)
Calcolo del massimo di un insieme1. Scegli un elemento come massimo provvisorio2. Per ogni elemento i dell’insieme: se i>max eleggi i
come nuovo massimo provvisorio max3. Il risultato è max
Politecnico di Milano Esempi (3/3)Esempi (3/3)
Stabilire se una parola P viene alfabeticamente prima di una parola Q1. leggi P,Q 2. ripeti quanto segue:
3. se prima lettera di P < prima lettera Q allora scrivi vero4. altrimenti se prima lettera P > prima lettera Q
allora scrivi falso5. 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 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 ....
Politecnico di Milano 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
Politecnico di Milano Blocchi Elementari Blocchi Elementari
Politecnico di Milano 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
Politecnico di Milano
Istruzione 1
Istruzione 2
Istruzione N
Esempio:
• Leggi un numero da tastiera
• Moltiplicalo per 2
• Stampalo a video
SequenzaSequenza
Politecnico di Milano
Istruzione 1
Istruzione 2
Esempio:
• Leggi un numero da tastiera
• 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
Politecnico di Milano
Istruzione 1
Istruzione 2
Esempio:
• Leggi un numero da tastiera
• 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
Politecnico di Milano
I tre costrutti fondamentali sono sufficienti adescrivere qualunque algoritmo
I tre costrutti fondamentali sono sufficienti adescrivere 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-JacopiniTeorema di Böhm-Jacopini
Politecnico di Milano 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
Politecnico di Milano ProgrammazioneProgrammazione
� Linguaggi di programmazione� Fasi della programmazione� Paradigmi di programmazione� Costrutti elementari di un linguaggio di programmazione
Politecnico di Milano 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
Politecnico di Milano 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)
Politecnico di Milano 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
Politecnico di Milano 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
Politecnico di Milano 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
Politecnico di Milano Contenuto della memoriaContenuto della memoria
Politecnico di Milano Le istruzioni del programmaLe istruzioni del programma
Politecnico di Milano 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
Politecnico di Milano L’esempio in linguaggio assemblyL’esempio in linguaggio assembly
READ AREAD BREAD CREAD DLOADA A LOADB BADDSTOREA RISLOADA CLOADB DADD
LOADB RISMULSTOREA RISWRITE RISHALT
INT AINT BINT CINT DINT RIS
Politecnico di Milano 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 livelloin linguaggio macchina
Politecnico di Milano 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#� …
Politecnico di Milano 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
Politecnico di Milano 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
Politecnico di Milano Fase di compilazioneFase di compilazione
� Il codice sorgente viene passato al compilatoreche si occuperà di tradurre il programma nel codice in linguaggio macchina
� Genera il programma oggetto
Politecnico di Milano 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
Politecnico di Milano 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
Politecnico di Milano 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