Informatica umanistica b algoritmi, programmi, e linguaggi di programmazione



Scaricare 471.5 Kb.
26.01.2018
Dimensione del file471.5 Kb.


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

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

  • Tritare l'aglio

  • Unirlo all'olio, alle acciughe tagliate molto finemente

  • Cuocere a fiamma moderata e mescolare fino a far ridurre il contenuto in un composto omogeneo.

  • Dopo circa venti minuti aggiungere qualche fiocco di burro

  • 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):

    • Scomponi M ed N in fattori primi
    • 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):

    • RIPETI finche’ M  N
    • SE M > N, M  M –N;
    • ALTRIMENTI, N  N – M;
    • RITORNA al passo 1;
    • 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: L’ALGORITMO DI EUCLIDE, II

  • MCD(M,N):

    • Dividi M per N; sia R il resto
    • Se R = 0, termina; MCD = N
    • Altrimenti, M = N, N = R, e ritorna da


UN ALGORITMO PIU’ FORMALE (CLASSIFICAZIONE DELLA TEMPERATURA)



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):

    • RIPETI finche’ M  N
    • SE M > N, M  M –N;
    • ALTRIMENTI, N  N – M;
    • RITORNA al passo 1;
    • 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:

    • Leggi da input l’altezza H
    • Leggi da input la base B
    • Calcola l’area A
    • Produci in output il risultato


AREA DEL RETTANGOLO: DIAGRAMMA DI FLUSSO



BLOCCHI: INIZIO E FINE PROGRAMMA



BLOCCHI: ISTRUZIONI ELEMENTARI



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):

    • RIPETI finche’ M  N
    • SE M > N, M  M –N;
    • ALTRIMENTI, N  N – M;
    • RITORNA al passo 1;
    • OUTPUT M


ESEMPIO: SCAMBIO DI VALORI

  • Leggi il valore della prima variabile X

  • Leggi il valore della seconda variabile Y

  • Salva il valore di X in una variable Aux per ricordarlo

  • Assegna ad X il valore di Y

  • Assegna a Y il valore di Aux



DIAGRAMMA DI FLUSSO



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

  • Leggi N

  • Dividi N per 2

  • Se Resto = 0 scrivi: N e’ pari

  • 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



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



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



INTERPRETI

  • Un interprete e’ un programma che interpreta le istruzioni di un programma ad alto livello DIRETTAMENTE, senza tradurle in linguaggio macchina

  • Tipici linguaggi interpretati: Java, Lisp, Perl, Python



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



DIFFERENZE TRA LINGUAGGI AD ALTO LIVELLO



DIFFERENZE TRA LINGUAGGI AD ALTO LIVELLO



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



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




Condividi con i tuoi amici:


©astratto.info 2019
invia messaggio

    Pagina principale