Fondamenti Teorici e Programmazione - Modulo B

Modulo B - Metodi formali per l'informatica - Fondamenti teorici

Programma del corso

1. Fondamenti di strutture dati

   • Insiemi
   • Relazioni e funzioni
   • Alberi - Grafi (precedenze: insiemi, plan, e dipendenza, scheduling) - Es: top, insieme di profili, crit. net.

2. Logica

   Strumenti che permettono di rappresentare dati (linguaggio molto preciso)

   Informatica: pone problema per problema

   • Es: SORT(N) = SORT(N) <= N AND SORT(N+1) = SORT(N+1)
   • AND = proprietà che deve valere per età molte

3. Linguaggi formali e automi

   Funzioni: teorie formali per definire linguaggi

   • Linguaggi formali indispensabili per programmare le macchine
   • Automi: formali che permettono di riconoscere linguaggi
   • Deterministici e non deterministici

Programma corsi 2016-2017 Docchiotiri - Modulo B

• Risanamento formale
• Quantificatori e nomi simbolici
• Equivalenza
• Dimostrazioni per assurdo
• Controesempi per induzione

Linguaggi di programmazione

Stringhe ed insiemi di stringhe

Grammatiche

• Regolari
• Liberi
• Ambiguità grammaticale
• Alberi del derivazione sintattica

Cenni su calcolabilità

• Problemi che il calcolatore non possono risolvere
• Problemi intrattabili

Parte comune ai 2 moduli

• Richiami di matematica: Insiemi, Algebra di Boole, Relazioni, Funzioni
• Introduzione all'informatica

Concetti di base Cormen et al. "Introduzione agli algoritmi", Jackson libri, CAPE

Linguaggi formali e automi, Dino Pderschi "Elementi di sintassi dei linguaggi di programmazione"

• Proseguerei il modulo: Automa
• Ricevimenti: Mercoledì 16-18

Teoria degli Insiemi (Fondamenti di Strutture Dati)

INSIEME: Collezione di elementi distinguibili (numeri o elementi)

APPARTENENZA:

x ∈ S      x ∉ S

• x elemento di S      non elemento di S
• S insieme che contiene x      S non contiene x

RAPPRESENTAZIONE ESTENSIONALE (IN EXTENSO): Descrivo insieme attraverso elenco dei soli elementi scritti tra parentesi graffe (vale solo per insiemi finiti)

Es. { 1, 2, 3 }

• Elementi di un insieme sono tutti distinti
• Non può contenere stesso oggetto più di una volta (elementi duplicati)

RAPPRESENTAZIONE INTENSIONALE (IN INTENSO): Descrivo insieme basandomi sulle proprietà degli elementi dell'insieme

Sono espressioni che descrivono insiemi con vincoli

Due insieme sono UGUALI se contengono gli stessi elementi: A = B    Es.{ 1, 2, 3 } = { 3, 2, 1 }

NOTAZIONI SPECIALI PER ALCUNI INSIEMI

N:  Insieme dei numeri naturali {0, 1, 2, 3... }

R:  Insieme dei numeri reali

Z:  Insieme dei numeri interi {-2, -1, 0, 1, 2, 3... }

∅:  Insieme vuoto (non contiene elementi o { })

:

≡  :  Uguale per definizione a...

≘  :  Dove, quindi coincide

⊂  :  Comune relazione di sottoinsieme

{ x : x ∈ Z }     INSIEME DEI NUMERI INTERI PARI

INSIEMI INFINITI

Impossibile elencare tutti i suoi elementi (estens)

Problema della rappresentazione estensionale

Ricorreremo al... MA E NOTAZIONE INTENSA

Necessario, proibire per elencare un'infinità elementi

Devo dare specifiche, formali rappresentazione intensionale

USO NOMI SIMBOLICI (VARIABILI PARAMETRI)

Espressioni aritmetiche simboliche

x + y = 4, valore dipende dal valore delle variabili

Necessario specificare insieme in cui ogni variabile assume propri valori

Preziosare omessa se insieme e il fenomeno e' chiaro dal contesto

Per specificare insieme in cui ogni variabile può assumere valori o usare...

Es in x + y = x, y devono essere valori numerici,ma non chiaro se N, Z, R

{ x | x ∈ Z, x > 0 } = N*

ESEMPIO RAPPRESENTAZIONE INTENSIONALE

Avendo a disposizione le variabili possiamo scrivere delle espressioni che descrivono insiemi utilizzando...

PARTIZIONE

DATO UN INSIEME S, UNA COLLEZIONE È UN INSIEME DI INSIEMI NON VUOTI. C_S (collezione di insieme non vuoti) FORMA UNA PARTIZIONE DI UN INSIEME S SE:

• 1. OGNI S_i È SOTTOINSIEME DI S.
• 2. OGNI COPPIA DI SOTTOINSIEMI S_i, S_j ∈ C_S È DISGIUNTA, OVVERO S_i ∩ S_j = Ø
• 3. S E COPRE TUTTO S, OVVERO ∪_i ∈ C_S S_i = S

insieme di partenza LA LORO UNIONE È S DICE S

CARDINALITÀ o DIMENSIONE |S| , n

NUMERO ELEMENTI DI UN INSIEME A (MISURA NUMERICA)

INSIEMI CON STESSA CARDINALITÀ ⇨ ELEMENTI CHE DUE INSIEMI POSSONO ESSERE MESSI IN CORRISPONDENZA

CARDINALITÀ Ø = 0

INSIEME FINITO ⇨ CARDINALITÀ DI UN INSIEME è UN NUMERO NATURALE N → |A| ∈ N

INSIEME INFINITO ⇨ CARDINALITÀ INSIEME NON E' INTERO NATURALE MA INFINITO |A| ∉ N

INFINITO NUMERABILE ⇨ I SUOI ELEMENTI POSSONO ESSERE MESSI IN CORRISPONDENZA CON N ES: Z (interi)

INFINITO NON NUMERABILE ⇨ NON PUÒ ESSERE MESSO IN CORRISPONDENZA BIUNIVOCA CON N ES: R (Reali)

Proprietà:

A ∪ B = |A| + |B| - |A ∩ B| A ∪ B ≤ |A| + |B|

A ∩ B = 0 A ∪ B = |A| + |B|

A ⊆ B allora |A| ≤ |B|

DEFINIZIONI VARIE:

SINGOLETTO = 1 ELE in l'insieme

K-SOTTOINSIEME = SOTTOINSIEME DI K ELEMENTI

N-INSIEME = INSIEME FINITO DA N ELEMENTI

INSIEME POTENZA

INSIEME DI TUTTI I POSSIBILI SOTTOINSIEMI DI UN INSIEME S INCLUSO Ø E INSIEME S STESSO

INSIEME DI POTENZA DI S: P(S), CARDINALITÀ insieme di potenza INSIEME FINITO |P(L)| = 2^|S|

Esempi: |P({a, b})| = 1P({a, b})| = 2² = 4

Es: S = {a, b} P(S) = {Ø, {a}, {b}, {a, b}}

OSSERVAZIONI SULLE RELAZIONI DI EQUIVALENZA

ANCHE LE RELAZIONI CHE SONO INSIMI POSSONO ESSERE INTENSIONALI O ESTENSIONALI

Relazione dell'_OSSERVAZIONE(3⁰) È DEFINITA ESTENSIONALE

Relazione successione definita come succ: {a_n/b_n ∈ ℕ / a ≠ 7} È INTENSIONALE

ESERCIZI SULLE RELAZIONI DI EQUIVALENZA 3⁰

R= {(a,b)/ a=b; (a,g); (e,g); (e,p; (h,f); (e,h; (f,m); (n,o)} ?

1. OPERAZIONE MODULO SUGLI INTERO Z CALCOLA IL RESTO DELLA DIVISIONE INTERA TRA a e b

   Definisci la relazione di equivalenza EQUIVALENTE MODULO n SUGLI INTERI Z_n CHE DICE:

   a R b se a modulo n = b modulo n

   • N= MOLTIPLICATORE CHE OLIVINDA

   • Q= NUMERO CHE MULTIPLICATO ARR. A UN SAME ININTERO

   CIOÈ MODULO dettor CALCOLA RESTO DIVISIONE TRA a e b

   LA RELAZIONE EQUIVALENTE MODULO n DICE CHE: (a,e,b) stanno appartengano a R,

   rist è uguale al resto della divisione di b

   a-b= n x q o a= nq+ b

   Es.:

   • 27: 7 = (14)/7 x 2 n=7 q=2

   • 25= 5 x 4 /(20) n= 5 q=4

   2 = (z)_n {(a,b) ∣ a, b ∈ Z / a= n.q+ b}

2. CALCOLA CLASSI DI EQUIVALENZA INOCITE 3⁰ SUL POLARIZZAZIONE DI EQUIVALENZA EQUIVALENZE MODULO 7

   0 ⁿ = {7, 14, 21, ²⁸, 35, ...}

   3ⁿ = {0, 7, 24, 31, ...}

   4ⁿ = {4, 3, 5, ¹¹, 8, 5, 25}

   5ⁿ = {12, 9, 26, ...}

   a= n.q + b

   REGOLA

   [Z]₂ = {16} = 7 ∣ 2 + 2 σα

   16 - 2 = 7 + 0

   a+b= n.q

4 QUANTE SONO IN GENERALE LE CLASSI DI EQUIVALENZA INDOTTA DA IN RELAZIONE EQUIVALENTE MOD. 7

SONO 7: LE CLASSI DI EQUIVALENZA SONO UGUALI AL VALORE DI N

SE n= 7 CI SONO 7 CLASSI DI EQUIVALENZA