PROGRAMMAZIONE: linguaggi

1

Linguaggi ad alto livello : Java, Basic, C++, HTMLLinguaggi a basso livello: assemblyLinguaggio macchina

PROGRAMMAZIONE: traduttori

2

COMPILATORI: da linguaggio evoluto a linguaggio macchina (eventualmente attraverso assembly)INTERPRETI: da linguaggio evoluto a linguaggio macchina, una istruzione alla voltaASSEMBLATORI: da linguaggio assembly a linguaggio macchina

ELEMENTI DEI LINGUAGGI

3

Ogni linguaggio ha un alfabeto costituito da differenti caratteri.

Un insieme di caratteri costituisce una parola.

Istruzione è un elemento del linguaggio di programmazione con cui si richiede l’esecuzione di una operazione.

• Ingresso• Uscita• Assegnazione• Confronto• Operazione logica o matematica• Salto

ELEMENTI DEI LINGUAGGI

4

Funzione: insieme di espressioni il cui risultato dipende dal valore assunto da una o più variabili.

Struttura: insieme razionale e ordinato di varie istruzioni• Sequenza• Selezione• Ripetizione

ALGORITMI

5

Un algoritmo (detto anche procedura, prescrizione, processo, routine, metodo) è un insieme di regole (dette anche direttive o istruzioni) che, eseguite secondo un ordine prestabilito, consentono di trovare il risultato di un problema a partire dai dati in ingresso.

ALGORITMI

6

Le caratteristiche fondamentali degli algoritmi sono:

1.non ambiguità: le operazioni indicate devono essere sufficientemente semplici e ben definite da poter essere comprese da un esecutore non particolarmente esperto (uomo o macchina);

2.eseguibilità: l’esecutore deve essere in grado di eseguire ogni singola regola con le risorse a sua disposizione;

3.finitezza: ogni algoritmo deve terminare dopo un numero finito di passi, cioè in un intervallo finito di tempo.

DIAGRAMMI DI FLUSSO

7

Il diagramma di flusso è una rappresentazione grafica di un algoritmo costituita da un insieme di simboli (figure geometriche standard) collegate da frecce.

DIAGRAMMI DI FLUSSO

8

RAPPRESENTAZIONE A BLOCCHI DI SELEZIONI

9

RAPPRESENTAZIONE A BLOCCHI DI SELEZIONI

10

RAPPRESENTAZIONE A BLOCCHI DI RIPETIZIONI

11

Esempio: Massimo Comun Divisore. Un esempio di algoritmo contenente due selezioni binarie con una sola azione è fornito da quello che calcola il Massimo Comun Divisore (MCD) di due interi positivi secondo il seguente metodo di Euclide

Per calcolare il MCD di due interi positivi:

• si divide il maggiore per il minore

• se il resto è 0 il minore rappresenta il MCD cercato

• altrimenti il minore sostituisce il maggiore, il resto sostituisce il minore e il procedimento ricomincia da capo.

Il relativo diagramma di flusso è indicato in figura.

La corrispondente espressione in pseudo istruzioni è la seguente:

1. leggi x, y;2. if (x < y)

scambiali;3. dividi x per y e

chiama r il resto;4. poni x = y;5. poni y = r;6. if (r == 0) stampa

x ; fine 7. vai a 3);

Come si può osservare, nella forma strutturata sono scomparse le istruzioni di salto e i riferimenti numerici delle singole istruzioni.

Esempio: lati di un triangolo. Come esempio di selezioni binarie in cascata si può considerare il seguente

PROBLEMA: “scrivere un algoritmo che consenta di stabilire se tre numeri, a, b, c possono essere i lati di un triangolo”.

ALGORITMO: come è noto, in un triangolo la somma di due lati qualsiasi è maggiore del terzo.

Perciò dovranno essere contemporaneamente soddisfatte le tre condizioni:

a + b > c a + c > b b + c > a

1) leggi a, b, c;2) se (a + b <= c) vai a 7);3) se (a + c <= b) vai a 7);4) se (b + c <= a) vai a 7);5) stampa “Lati validi”;6) fine;7) stampa “Lati non validi”;8) fine;

Esse si traducono nelle seguenti pseudo istruzioni:

e quindi nel diagramma di flusso indicato a lato:

Per dividere tra loro due numeri naturali:

• si sottrae il divisore dal dividendo;

• si continua a sottrarlo dal risultato dell’ultima sottrazione fino a che tale risultato sia maggiore o uguale al divisore

• il numero di sottrazioni effettuate fornisce il quoziente

• il risultato dell’ultima fornisce il resto della divisione

Esempio: divisione con sottrazioni ripetute. Un esempio di ciclo con guardia all’inizio è costituito dall’algoritmo che esegue la divisione intera fra due numeri naturali con il seguente metodo delle sottrazioni ripetute:

Questo algoritmo si traduce facilmente nel diagramma di flusso seguente, dove la variabile res contiene inizialmente il dividendo, la variabile den il divisore. res contiene poi i risultati delle successive sottrazioni, l’ultimo dei quali fornisce appunto il resto.

Il quoziente è fornito dal contatore quoz, che inizialmente vale 0 e viene incrementato di 1 a ogni sottrazione eseguita.

Esempio: moltiplicazione con addizioni ripetute. Un esempio di ciclo con guardia alla fine è costituito dall’algoritmo che esegue la moltiplicazione di due numeri naturali con il metodo delle addizioni ripetute:

Questo algoritmo si traduce facilmente nel seguente diagramma di flusso dove indichiamo con

•A, B i due numeri da moltiplicare

•prod il prodotto

•K una variabile contatore, posta inizialmente uguale a uno dei due numeri. K viene diminuita di 1 ogni volta che si esegue un’addizione, e quando raggiunge il valore 0 determina la fine del ciclo.

per moltiplicare tra loro due numeri naturali si somma uno di essi a se stesso un numero di volte uguale all’altro.