INFORMATICA UMANISTICA B

ALGORITMI, PROGRAMMI, E LINGUAGGI DI

PROGRAMMAZIONE

DI NUOVO LA MACCHINA DI TURING

MACCHINA DI TURING COME MODELLO DI PROGRAMMAZIONE

Partendo dalla macchina di Turing, abbiamo seguito un primo percorso attraverso l’Informatica moderna, focalizzato sull’aspetto ‘sistemistico’ dell’Informatica

La macchina di Turing non e’ pero’ soltanto, o soprattutto, un architettura di computer, ma un punto di partenza per teorie della PROGRAMMAZIONE

In questa lezione e la prossima seguiremo invece un secondo percorso focalizzato su questo aspetto

PROGRAMMI

Un computer e’ una macchina per eseguire PROGRAMMI

Un programma e’ un ALGORITMO per risolvere un certo PROBLEMA scritto secondo le regole di un LINGUAGGIO DI PROGRAMMAZIONE

ALGORITMO

Un PROGRAMMA e’ un ALGORITMO posto in forma comprensibile al computer

Definizione informale di ALGORITMO: una sequenza FINITA di passi DISCRETI e NON AMBIGUI che porta alla soluzione di un problema

Questa definizione si puo’ applicare al di fuori dell’Informatica: nella matematica (da cui ha origine) ma anche nella cucina

UN QUASI-ALGORITMO: LA RICETTA PER LA BAGNA CAUDA

1. Cuocere gli spicchi di aglio, coperti con il latte, fino a quando non diventino teneri.

2. Tritare l'aglio3. Unirlo all'olio, alle acciughe tagliate molto

finemente4. Cuocere a fiamma moderata e mescolare

fino a far ridurre il contenuto in un composto omogeneo.

5. Dopo circa venti minuti aggiungere qualche fiocco di burro

6. Servire in tavola con le verdure.

PERCHE’ QUASI-ALGORITMO?

Numero di passi e’ finito Ma molti passi sono ambigui:

‘teneri’? `fiamma moderata’?

IL TERMINE ALGORITMO

Il nome ALGORITMO deriva dal nome del matematico persiano Muhammad ibn Mūsa 'l-Khwārizmī che attorno all’825 scrisse un trattato chiamato Kitāb al-djabr wa 'l-muqābala (Libro sulla ricomposizione e sulla riduzione) AL-KHWARIZMI ALGORISMO

ALGORITMO (ALGEBRA deriva da AL-DJABR)

UN PROBLEMA, DUE ALGORITMI: IL MASSIMO COMUN DIVISORE

MCD: UN ALGORITMO ELEMENTARE

A scuola si impara un algoritmo molto semplice per calcolare MCD: la SCOMPOSIZIONE IN FATTORI PRIMI

42 = 2 x 3 x 7 56 = 2 x 2 x 2 x 7

Algoritmo MCD(M, N):1. Scomponi M ed N in fattori primi2. Estrai i componenti comuni

Questo metodo si’ puo’ solo applicare per numeri piccoli (la scomposizione in fattori primi e’ molto costosa)

MCD: L’ALGORITMO DI EUCLIDE

MCD(M,N):1. RIPETI finche’ M N

2. SE M > N, M M –N;

3. ALTRIMENTI, N N – M;

4. RITORNA al passo 1;

5. OUTPUT M

ESEMPIO

MCD(42,56): M(42) N(56);

N (56) > M (42) N 14

M(42) N(14); M (42) > N (14); M 28

M(28) N(14) M(28) > N (14); M 14

OUTPUT: 14

MCD(M,N):1. RIPETI finche’ M N

2. SE M > N, M M –N;

3. ALTRIMENTI, N N – M;

4. RITORNA al passo 1;

5. OUTPUT M

ALCUNE CONSIDERAZIONI:PROBLEMI ED ALGORITMI

Ci sono sempre molti algoritmi per risolvere un problema

Parte dell’arte della programmazione e’ trovare gli algoritmi piu’ efficienti

ALGORITMI E FUNZIONI

In termini matematici, un algoritmo puo’ essere visto come una FUNZIONE che produce un certo OUTPUT dato un certo INPUT Per esempio, MCD(42,56) = 14

Due algoritmi si dicono EQUIVALENTI se producono lo stesso output dato lo stesso input. Fattori primi e Euclide sono EQUIVALENTI (ma

non egualmente efficienti!!)

ALGORITMI PIU’ COMUNI IN INFORMATICA

Algoritmi MATEMATICI Per fare calcoli anche molto complessi (per esempio,

integrali, la scoperta di numeri primi)

Algoritmi di ORDINAMENTO 45 2 17 28 101 2 17 28 45 101

Algoritmi di RICERCA Algoritmi per il TRATTAMENTO DELLE STRINGHE COMPILATORI Algoritmi di COMPRESSIONE

DA ALGORITMI A PROGRAMMI

LINGUAGGI DI PROGRAMMAZIONE

Un linguaggio di programmazione permette di esprimere certi tipi di istruzioni in modo che possano venire poi convertite in istruzioni macchina

Un linguaggio di programmazione e’ caratterizzato da SINTASSI (come vengono scritte le istruzioni) SEMANTICA (come devono venire interpretate)

CONSIDERAZIONI, II: INGREDIENTI ESSENZIALI DI UN LINGUAGGIO DI PROGRAMMAZIONE

MCD(M,N):1. RIPETI finche’ M N

2. SE M > N, M M –N;

3. ALTRIMENTI, N N – M;

4. RITORNA al passo 1;

5. OUTPUT M

INGREDIENTI ESSENZIALI DI UN LINGUAGGIO DI PROGRAMMAZIONE

Poter mettere istruzioni in SEQUENZA Poter cambiare l’ordine di esecuzione sulla

base di TEST Poter RIPETERE istruzioni Questi ingredienti vengono catturati tramite i

DIAGRAMMI DI FLUSSO

DIAGRAMMI DI FLUSSO

Una rappresentazione grafica usata per descrivere in modo piu’ preciso i passi di un algoritmo senza usare una sintassi specifica

Un diagramma e’ composto da una serie di BLOCCHI uniti da archi

ESEMPIO: AREA DEL RETTANGOLO

Calcolo dell’area di un rettangolo AREA:

1. Leggi da input l’altezza H

2. Leggi da input la base B

3. Calcola l’area A

4. Produci in output il risultato

AREA DEL RETTANGOLO: DIAGRAMMA DI FLUSSO

BLOCCHI: INIZIO E FINE PROGRAMMA

BLOCCHI: ISTRUZIONI ELEMENTARI

COUNT 0

COUNT COUNT + 1

BLOCCHI: INPUT / OUTPUT

LE VARIABILI

Molti algoritmi richiedono un qualche modo per immagazzinare i risultati di certi calcoli. Per esempio, nell’algoritmo per MCD, M e N

Quasi tutti i linguaggi di programmazione permettono di usare delle VARIABILI per questo scopo. Una variabile puo’ essere pensata come un nome per una zona di memoria.

VARIABILI NELL’ALGORITMO DI EUCLIDE

MCD(M,N):

1. RIPETI finche’ M N

2. SE M > N, M M –N;

3. ALTRIMENTI, N N – M;

4. RITORNA al passo 1;

5. OUTPUT M

CONDIZIONALI

Un’altro degli ingredienti fondamentali di un linguaggio di programmazione e’ la possibilita’ di scegliere di eseguire istruzioni diverse a seconda dei risultati di un TEST

CONDIZIONALI

ESEMPIO: PARI O DISPARI

1. Leggi N

2. Dividi N per 2

3. Se Resto = 0 scrivi: N e’ pari

4. Altrimenti scrivi: N e’ dispari

PARI E DISPARI

RIPETIZIONI

L’ultimo componente fondamentale di un linguaggio di programmazione e’ la possibilita’ di ripetere le stesse azioni un gran numero di volte

RIPETIZIONI

ALGORITMO DI EUCLIDE

M N

OUTPUT:M

M > N?

M M - N N N - M

STOP

START

F

T

T

F

REMINDER: LA MACCHINA DI TURING E L’IPOTESI DI CHURCH

Quando avevamo introdotto la macchina di Turing, si era menzionata l’ipotesi di Church: La macchina di Turing’ e’ una macchina

UNIVERSALE Nel senso che ogni programma eseguibile puo’

essere scritto sotto forma di istruzioni per la macchina di Turing

Questa ipotesi si basa sul fatto che la macchina di Turing puo’ esprimere tutti i costrutti fondamentali appena discussi

LINGUAGGI DI PROGRAMMAZIONE

Il calcolatore comprende istruzioni in LINGUAGGIO MACCHINA 0011 001 010

Una prima astrazione dal linguaggio macchina sono i cosiddetti ASSEMBLER che esprimono le istruzioni macchina in formato simbolico ADD R1 R2

Una seconda astrazione sono i linguaggi di programmazione AD ALTO LIVELLO che astraggono dalle istruzioni macchina X X + Y

ALGORITMO DI EUCLIDE IN UN TIPICO LINGUAGGIO AD ALTO LIVELLO

function MCD(M,N) while M ≠ N if M > N then M M - N else N N - M return M

COMPILATORE

E’ un programma che trasforma un programma espresso in linguaggio ad alto livello (PROGRAMMA SORGENTE) in linguaggio macchina (PROGRAMMA OGGETTO) In Windows: crea file .exe

Linguaggi tipicamente compilati: C, C++, Fortran, Pascal

COMPILATORI

UN ESEMPIO DI LINGUAGGIO DI PROGRAMMAZIONE

VISUAL BASIC e’ il linguaggio di programmazione usato per sviluppare applicazioni in ambienti Microsoft Windows

E’ un linguaggio Di alto livello Interpretato Visuale

VISUAL BASIC:ASSEGNAZIONE AD UNA VARIABILE

VISUAL BASIC: INPUT / OUTPUT

VISUAL BASIC:COSTRUTTI CONDIZIONALI

VISUAL BASIC:ITERAZIONI

DIFFERENZE TRA LINGUAGGI AD ALTO LIVELLO

GREP in PERL:

while (<STDIN>) {

if (/Poesio/) { print $_;}

}

DIFFERENZE TRA LINGUAGGI AD ALTO LIVELLO

….import java.util.regex.*;

public class Grep { …. // Pattern used to parse lines private static Pattern linePattern = Pattern.compile(".*\r?\n"); // The input pattern that we're looking for private static Pattern pattern; // Compile the pattern from the command line private static void compile(String pat) { try { pattern = Pattern.compile(pat); } catch (PatternSyntaxException x) { System.err.println(x.getMessage()); System.exit(1); } } // Use the linePattern to break the given CharBuffer into lines, applying // the input pattern to each line to see if we have a match

private static void grep(File f, CharBuffer cb) { Matcher lm = linePattern.matcher(cb); // Line matcher Matcher pm = null; // Pattern matcher int lines = 0; while (lm.find()) { lines++; CharSequence cs = lm.group(); // The current line if (pm == null) pm = pattern.matcher(cs); else pm.reset(cs); if (pm.find()) System.out.print(f + ":" + lines + ":" + cs); if (lm.end() == cb.limit()) break; } }

XSL

XSL (eXtensible Stylesheet Language): un linguaggio che permette di specificare come visualizzare un documento formattato in XML

Uso tipico: convertire XML in HTML

COSTRUTTI CONDIZIONALI IN XSL

<xsl:template match="poem">

<xsl:if test="@author='jm'"> 1. The poem's author is jm. </xsl:if>

<poem author="jm" year="1667"> <verse>Seest thou yon dreary Plain, forlorn and wild,</verse> <verse>The seat of desolation, void of light,</verse> <verse>Save what the glimmering of these livid flames</verse> <verse>Casts pale and dreadful?</verse> </poem>

LINGUAGGI DI MARCATURA E LINGUAGGI DI PROGRAMMAZIONE

Attenzione a non confondere un linguaggio di MARCATURA come XML con un linguaggio di PROGRAMMAZIONE come XSL Un linguaggio di marcatura CLASSIFICA certe

porzioni di testo Un linguaggio di programmazione specifica

ISTRUZIONI

QUALI SONO I LINGUAGGI DI PROGRAMMAZIONE PIU’ USATI?

LETTURE

Tomasi: 1.2, 1.3, 1.4 Da Wikipedia: le voci

Algoritmo Diagramma a blocchi Programma Linguaggio di Programmazione