Corso di Informatica per Giurisprudenza Lezione 2 Agenda Concetto di algoritmo



Scaricare 445 b.
25.11.2017
Dimensione del file445 b.


Corso di Informatica per Giurisprudenza Lezione 2


Agenda

  • Concetto di algoritmo:

    • Algoritmi e programmi
      • Macchina a stati
      • Linguaggi e calcolabilità
      • Linguaggi di Programmazione
        • Semantica operazionale
        • Funzioni e denotazione
      • Equivalenza funzionale e computazionale
    • Codifica dei dati
      • Tipi elementari
      • Strutture di dato


Macchina a stati (1)

  • Formalizzazione del concetto di calcolo

  • Operazioni base di una macchina a stati:

    • Lettura dell’input
    • Scrittura dell’output
    • Transizione di stato
    • Memorizzazione dati


Macchina a stati (2)

  • Calcolo:

    • Stato iniziale
    • Sequenza di caratteri di input
    • Sequenza di stati ed azioni di trasformazione dell’input
    • Sequenza di scritture dell’output
    • Stati finali


Rappresentazione a grafo



Esempio di macchina a stati (1)

  • Un apparecchio telefonico può essere riguardato come una macchina a stati

    • Stato iniziale: segnale assente (s0)
    • Stati intermedi: segn. di linea (s1) segn. di libero (s2) segn. di occupato (s3) segn. di assenza di linea (s4)
    • Stato finale: conversazione conclusa (s5)
  • Linguaggio riconosciuto: Attivazione di una conversazione telefonica



Esempio di macchina a stati (2)

  • Modello di funzionamento

    • Stato iniziale: segnale assente
    • Sequenza:
      • Accesso (a);
      • Se linea Componi (c);
      • Se libero Conversazione (p) altrimenti se occupato Concludi (e)


Esempio di macchina a stati (3)



Il concetto di linguaggio (1)

  • Alfabeto

    • Un insieme finito e non vuoto i cui elementi sono detti SIMBOLI
  • Stringa

  • Stringa vuota

    • La sequenza di lunghezza zero su un qualsiasi alfabeto (è denotata con )


Il concetto di linguaggio (2)

  • Sia  un alfabeto,

    • * denota l’insieme delle stringhe su 
    • + denota l’insieme delle stringhe su  tranne la stringa vuota
    • + = * - {}
  • Linguaggio

    • Sottoinsieme delle stringhe su di un alfabeto
    • L  *


Un esempio

  • = {a,b,c}

  • * = {, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, …}

  • Un linguaggio

    • L = {a, aa, aaa, aaaa, aaaaa, …}


Grammatiche (1)

  • Dato un alfabeto VT detto alfabeto terminale,

  • un alfabeto VN detto alfabeto nonterminale,

  • un elemento s dell’alfabeto nonterminale detto simbolo distinto,

  • un insieme P di regole di produzione che trasformano stringhe di (VT ∪ VN)* in stringhe nonvuote su VT ∪ VN,

  • la quadrupla < VT,VN,s,P> è detta una grammatica



Grammatiche (2)

  • Date due stringhe  e  di (VT ∪ VN)* diremo che  deriva  ( ⇒ )se e solo se scrivesi

    •  = xy;
    •  = xy
    • Con x, y, ,  in (VT ∪ VN)*
    • C’è una regola di produzione  → 


Grammatiche (3)

  • Una stringa è derivata indirettamente da un’altra quando si può compiere una sequenza di passi di derivazione che conduce dalla prima alla seconda stringa

  • Il linguaggio generato da una grammatica è costituito dalle stringhe terminali derivate indirettamente dal simbolo distinto

  • Ogni stringa del linguaggio generato da una grammatica si dice sinttaticamente corretta per la grammatica stessa



Grammatiche (4)

  • Un linguaggio generato da una grammatica si dice grammaticale

  • IMPORTANTISSIMO:

  • Un linguaggio è grammaticale se e solo se è riconoscibile da una macchina a stati



Osservazioni (1)



Osservazioni (2)

  • Le lettere dell’Italiano sono simboli di un alfabeto

  • Possiamo vedere come linguaggio:

    • Il lessico (radici e desinenze delle parole)
    • Il vocabolario (l’insieme delle parole italiane)
    • Le strutture frasali (sintagmi) italiane:
      • “Il giovane biologo veronese”;
      • “L’arguto giurista in erba scaligero”;
      • “L’interessante corso di Informatica”
    • Le frasi ed i periodi Italiani:
      • “La lezione si fece stimolante”;
      • “La pausa per il caffè era peraltro cogente”


Problemi (1)

  • Chiamiamo PROBLEMA DI RICONOSCIMENTO di un linguaggio L su di un alfabeto , il problema di stabilire se una data stringa  in * sia in L o no

  • Ogni stringa  si dice una istanza del problema



Generalità sulle funzioni (1)

  • Siano A e B due insiemi, diciamo Prodotto Cartesiano A╳B l’insieme delle coppie ordinate di elementi di A e B

  • Chiamiamo relazione tra A e B un sottoinsieme del prodotto cartesiano di A e B

  • Per una relazione r definita tra A e B definiamo A il dominio di r, e B il codominio di r



Generalità sulle funzioni (2)

  • Una funzione è una relazione univoca, cioè una relazione che ad ogni elemento del dominio associa al più un elemento del codominio

  • Una funzione che associa sempre ad un elemento del dominio un elemento del codominio si dice totale



Generalità sulle funzioni (3)

  • Dato un elemento x del dominio l’elemento in relazione f con x nel codominio si indica con f(x) e si dice l’immagine di x

  • Dato un elemento y nel codominio, se vale y = f(x), allora si dice che x è la controimmagine di y secondo f



Generalità sulle funzioni (4)

  • Una funzione f si dice iniettiva se ad elementi distinti del dominio associa elementi distinti del codominio: x ≠ y → f(x) ≠ f(y)

  • Una funzione si dice suriettiva se ogni elemento del codominio ha controimmagine ∀y∃x[y = f(x)]

  • Una funzione sia iniettiva che suriettiva si dice biiettiva o biunivoca



Esempi (1)

  • A={0,1}; B={a,b} A╳B = {(0,a);(0,b);(1,a);(1,b)}

  • Relazione determinata da 1 va con b R={(0,a);(0,b);(1,b)}



Esempi (2)

  • Sia A=naturali () e B=naturali

  • Funzione f(n)=n2

    • Proprietà:
      • Iniettiva
      • Non suriettiva
  • Funzione f(n) = maxdiv(n) [che trova il massimo divisore di n strettamente minore di n]

    • Proprietà:
      • Non iniettiva
      • Suriettiva


Problemi (2)

  • Sia f una funzione dai numeri naturali in se stessi (f: ℕ)

  • Dato un numero naturale n chiamiamo PROBLEMA DI CALCOLO

    • Trovare f(n)
  • Dati due numeri naturali m ed n chiamiamo PROBLEMA DI DECISIONE

    • Stabilire se vale f(n) = m


Concetto di calcolabilità

  • Una funzione f si dice calcolabile se e solo se esiste una macchina a stati che è in grado di leggere n in input e scrivere f(n) in output in un tempo finito

  • Una funzione f totale e calcolabile si dice totalmente calcolabile



Equivalenza (1)

  • Ogni problema di decisione può essere risolto se so risolvere il corrispondente problema di calcolo

    • Per decidere se m=f(n) calcolo f(n) e stabilisco se vale l’uguaglianza
  • Meno ovviamente vale anche il contrario

    • Se so stabilire quando m=f(n) per calcolare f(n) enumero da 1 in avanti e risolvo 1=f(n), 2=f(n),… fino a quando il risultato è vero. Il valore stabilito è f(n)


Equivalenza (2)

  • Ogni problema di decisione corrisponde ad un problema di riconoscimento e viceversa

  • Per stabilire che questo è vero è sufficiente ricordare che l’insieme * è ovviamente numerabile (anche detto di cardinalità ℵ0) ovvero corrispondente biunivocamente ad tramite una funzione h

  • Una volta enumerato * il problema di riconoscimento per una stringa corrisponde a stabilire se vale per una funzione f(h())=1 (inteso come codifica per il vero)



Equivalenza (2) - continua

  • Per un problema di decisione ogni istanza del problema può definirsi come una istanza di un problema di riconoscimento

    • Enumeriamo 2. Enumeriamo * per un dato alfabeto  e costruiamo la corrispondenza biunivoca composta da * all’enumerazione di 2.
    • Ogni coppia di corrisponde ora ad una stringa in *. Sia L il linguaggio delle stringhe che corrispondono ad una coppia (m,n) tale che f(n)=m. Riconoscere L corrisponde a risolvere il problema di decisione per f


Problemi paradigmatici

  • Date le equivalenze sopradette, i problemi paradigmatici sono quelli di riconoscimento

  • La calcolabilità è definita mediante macchine a stati

  • Quindi: l’obiettivo dell’informatica teorica è definire tecniche per risolvere problemi di riconoscimento mediante macchine a stati



Linguaggi di programmazione

  • Un linguaggio di programmazione è un linguaggio grammaticale il cui scopo è descrivere tecniche di risoluzione di problemi in modo che attraverso un meccanismo automatico si possa fare applicare tali tecniche su di una macchina a stati

  • I token di un linguaggio di programmazione (simboli dell’alfabeto su cui è costruito) si chiamano istruzioni



Linguaggi di programmazione

  • Una stringa sintatticamente corretta di un linguaggio di programmazione si dice un programma

  • La semantica operazionale di un linguaggio di programmazione corrisponde ad un insieme di regole che trasformano programmi in macchine a stati

  • La semantica denotazionale di un linguaggio di programmazione corrisponde ad un insieme di regole che trasformano un programma nella funzione da esso calcolata



Tipi di linguaggio (1)

  • Se le istruzioni di un linguaggio di programmazione vengono tradotte in comandi eseguibili dalla macchina (istruzioni macchina) una per volta il linguaggio di programmazione si dice interpretato

  • Il programma che effettua la traduzione si dice interprete



Se ogni programma di un linguaggio di programmazione viene tradotto in una sequenza di istruzioni macchina (codice eseguibile) il linguaggio di programmazione si dice compilato

  • Se ogni programma di un linguaggio di programmazione viene tradotto in una sequenza di istruzioni macchina (codice eseguibile) il linguaggio di programmazione si dice compilato

  • Il programma che effettua la traduzione si dice compilatore



Ogni programma eseguibile può essere in realtà strutturato in comandi eseguibili direttamente dalla macchina ma anche in comandi eseguibili da macchine virtuali

  • Ogni programma eseguibile può essere in realtà strutturato in comandi eseguibili direttamente dalla macchina ma anche in comandi eseguibili da macchine virtuali

  • Una macchina virtuale è un programma che conosce un codice intermedio tra quello ad alto livello del linguaggio di programmazione e quello della macchina fisica

  • Tale codice prende il nome di p-code



Architettura dei linguaggi

  • Sintassi del linguaggio e sua analisi

    • PARSER
  • Semantica del linguaggio

    • INTERPRETE
    • COMPILATORE
  • Esecuzione di programmi

    • Run-Time Support


Paradigmi di programmazione (1)

  • Un paradigma di programmazione è un modo di vedere la macchina che esegue i programmi

  • Esecuzione di p-code come semantica operazionale



Paradigmi di programmazione (2)

  • Linguaggi imperativi

    • La computazione è modellata come l’esecuzione di ordini da parte di un “servo”
  • Linguaggi dichiarativi

      • La computazione è modellata come un calcolo strutturato di
        • Funzioni (paradigma funzionale)
        • Condizioni logiche (paradigma logico)


Equivalenza di programmi

  • Due programmi che computano la stessa funzione possono farlo in modo profondamente diverso

  • Se due programmi computano la stessa funzione si dice che sono funzionalmente equivalenti

  • Se due programmi che computano la stessa funzione lo fanno nello stesso modo si dice che sono algoritmicamente equivalenti



Algoritmo

  • Perciò:

    • Algoritmo è la forma astratta di un programma, essendo due programmi implementazioni dello stesso algoritmo se computano la stessa funzione nello stesso modo
  • Necessità:

    • Un modo semplice e generale di descrivere gli algoritmi
  • Pseudolinguaggio

    • Una forma non implementata di linguaggio di programmazione che contenga le strutture base dei linguaggi di programmazione (imperativi)


Strutture fondamentali

  • Funzioni base

    • Controllo di flusso
    • Lettura di dati
    • Scrittura di dati
    • Assegnamento di valori a variabili


Controllo di flusso: sequenza

  • Struttura di controllo per fare eseguire due istruzioni una dopo l’altra

  • La rappresentazione normalmente adottata è di utilizzare un separatore di linea esplicito /il punto e virgola) o implicito (a capo)



Controllo di flusso: selezione

  • Struttura di controllo per fare eseguire una istruzione se vale una condizione ed un’altra altrimenti

  • La struttura generalmente si rappresenta mediante la codifica se condizione allora istr. 1 altrimenti istr. 2



Controllo di flusso: ciclo

  • Struttura di controllo per fare eseguire ripetutamente una istruzione se vale una condizione

  • La struttura generalmente si rappresenta mediante la codifica fintantoché condizione istruzione



Nozione di variabile

  • Variabile

    • Nome
    • Tipo
    • Valore
  • Un nome di variabile è valido, generalmente se è alfanumerico con limiti all’impiego di operatori aritmetici e se inizia con una lettera

  • Occorrono costrutti per

    • Definire tipi
    • Attribuire tipi alle variabili


Altre istruzioni

  • Assegnamento

    • x ← v
    • Sottocaso: incremento
      • x ← x + 1
  • Lettura

    • read(x)
  • Scrittura

    • write(x)


Tipi di dati

  • Tipi elementari/strutturati

  • Tipi predefiniti/utente

  • Costrutti di definizione di tipo

  • Costrutti di binding (assegnamento di tipo alle variabili)

  • Regole di compatibilità tra tipi



Tipi elementari

  • Tipi elementari predefiniti

    • Interi (numeri relativi)
      • Short/long
      • Range
    • Reali (numeri con la virgola)
      • Float/Double
      • Range e precisione
    • Carattere (caratteri alfanumerici)
    • Stringhe (sequenze di caratteri alfanumerici)
    • Logico (vero o falso)


Tipi enumerativi

  • I tipi enumerativi sono tipi utente elementari costituiti da un elenco di tutti e soli i possibili valori del tipo

  • Esempio: colori dell’arcobaleno

        • {rosso, arancione, giallo, verde, blu, indaco, violetto}


Tipi strutturati

  • Strutture statiche

    • Array
    • Record
  • Strutture dinamiche

    • Liste
    • Alberi
    • File


Accesso agli elementi

  • Strutture ad accesso diretto o casuale sono quelle che permettono di leggere e scrivere elementi della struttura senza aver prima scandito altri elementi

  • Strutture ad accesso sequenziale sono quelle che invece richiedono che la lettura di un elemento segua la lettura di altri elementi che precedono l’elemento detto nell’ordine di scansione della struttura



Array

  • Un array è un oggetto formato da un insieme accessibile direttamente di oggetti tutti dello stesso tipo

  • Gli indici di accesso sono un tipo enumerativo ovvero numeri interi

  • Un array è definito dalla sua dimensione strutturale (un array di dimensioni strutturale 1è un vettore, uno di dimensione strutturale 2 è una matrice) e dalle dimensioni relative (un vettore di dieci elementi è di dimensione relative 10)



Array

  • Esempio:

    • Array di dimensione strutturale 1 e dimensione relativa 7 di numeri interi


Record

  • Un record è un oggetto formato da un insieme accessibile direttamente di oggetti di tipi diversi

  • Gli indici di accesso sono nomi validi di variabili



Liste

  • Una lista si costruisce aggiungendo un elemento in coda ad una lista esistente, che può essere vuota

  • Per leggere una lista abbiamo due operatori:



Grafi

  • Un grafo (diretto) è una coppia in cui E è un insieme di coppie di V, gli elementi di V si chiamano vertici, gli elementi di E archi

  • Una sequenza di vertici di un grafo è un percorso se e solo se ogni coppia di vertici in sequenza è un arco

  • Un grafo si dice aciclico se e solo se non contiene percorsi circolari (cioè che iniziano e terminano con lo stesso vertice)



Alberi

  • Un albero è

    • Un grafo diretto aciclico dove
    • Ogni vertice è puntato da al più un altro vertice
    • L’insieme dei vertici non puntati è un singoletto
  • Una lista è un albero i cui elementi puntano al più un altro elemento



File

  • I file sono sequenze accessibili anche mediante indici

  • Si differenziano dalle liste per avere potenzialmente molti punti d’accesso





Condividi con i tuoi amici:


©astratto.info 2017
invia messaggio

    Pagina principale