Riassunto esame Programming for Data Science, prof. Ruggieri, libro consigliato Discrete mathematics and its applications, Rosen

R).

Dato che non tutte le relazioni sono

transitive, è possibile estendere una

relazione per renderla transitiva. Come si fa?

Aggiungendo il minimo numero di coppie

alla relazione per renderla transitiva. 44

La chiusura solo transitiva è il >. Mentre la chiusura transitiva-riflessiva è il ≥.

Cosa succederà qui? Devo prendere tutti i possibili passi e includerli per

ottenere la chiusura transitiva.

ORDINAMENTO PARZIALE

Gli ordinamenti sono delle relazioni che hanno le seguenti proprietà: riflessività, antisimmetricità,

transitività.

→

≤ ≤ l’uguale indica la riflessività quindi l’ordinamento è minore o uguale di se stesso. L’antisimmetrica

ci servirà quando avremo a≤b e b≤a per concludere che è l’unico caso possibile è quando a=b. Invece la

transitività è utile quando avremo a≤b≤c per concludere che a è minore di c.

Poset: insieme con una relazione d’ordine sull’insieme e viene indicato come . Ad esempio, i numeri

interi con la relazione ≤ sono un poset. Sullo stesso insieme possiamo definire più ordinamenti ad esempio

sull’insieme degli interi potremmo definire anche la relazione di ≥.

→ interi positivi e relazione di divisibilità ovvero {1,2,3..}, a|b.

Vediamo come soddisfa le proprietà: Le frecce indicano gli interi che

soddisfano la relazione. 1 divide tutti i

numeri, 2 divide 4, 6 e così via. Cosa

posso dedurre? Il 2 divide il 3? No quindi

non tutti i numeri sono confrontabili con

la relazione di divisore. Non posso dire

né che 2 divide 3, né che 3 divide 2.

Questo è quindi un ordinamento non totale.

→insieme delle parti. Un insieme S prende

tutti i sottoinsiemi e li confronta attraverso l’inclusione.

Confrontabilità: Due elementi a e b di un poset sono confrontabili se

Quando tutti gli elementi sono comparabili a coppie diciamo che l’ordinamento è

totale.

Ordinamenti buoni: se è un poset e ogni sottoinsieme non vuoto ha un

elemento minimo. 45

Ordinamento lessicografico:

Ad esempio, nel registro delle superiori a parità di cognome si andava a confrontare il nome.

Come rappresentiamo graficamente gli ordinamenti? Attraverso i diagrammi di Hasse.

Poset Stretti: Un ordinamento parziale è stretto se è non riflessivo, antisimmetrico e transitivo. Ciò che

cambia è che la coppia (a,a) non deve appartenere all’ordinamento. dato un Poset,

→

posso farlo diventare stretto e viceversa corrispondenza biunivoca.

Ordinamento ben fondato: se non esiste una catena discendente i cui elementi sono minori stretti dell’altro.



Esempio: (N, ) perché ovunque io parta arrivo a zero e sottozero non posso andare. Se considero i naturali

)

interi questo limite inferiore non esiste e quindi (Z, non è un ordinamento ben fondato.

Se l’ordinamento è ben ordinato allora la parte stretta è ben fondata.

Induzione ben fondata:

Prendiamo un ordinamento ben fondato, per dimostrare che tutti gli elementi di s soddisfano una proprietà

P prendo un qualsiasi elemento di S, assumo che tutti gli elementi più piccoli di x soddisfino la proprietà P e

dimostro che anche x soddisfa la proprietà. +

Istanziato il principio di induzione ben fondata Z , se per ogni

numero numero positivo, assumendo che P valga sui numeri

più piccoli valga anche per n o che per tutti i numeri positivi

vale P.

Perché questo è esattamente il principio di Induzione forte? Distinguiamo due casi: 46

→

- N=1 per ogni numero maggiore stretto di 1, in realtà non c’è nessun numero che soddisfa la

proprietà. Allora abbiamo l’insieme vuoto che è True. True implica P(1). Cosa vuol dire questo? Not

False or P(1). Not False non serve a niente, Quindi P(1). →

- N>1. Devo dimostrare che per ogni n>m vale p(1), p(2)… P(n-1) P(n)

A cosa ci serve l’induzione ben fondata?

-TERMINAZIONE programma

-CORRETTEZZA programma

Abbiamo visto la formula del binomiale

Considero l’ordinamento indotto dalle chiamate ricorsive: Posso usare l’induzione ben

fondata per dimostrare la correttezza del programma. Se dimostro che nei casi base ovvero

quelli senza altre induzioni sotto la formula è corretta e assumendo che sia corretta che nei

risultati allora la loro somma è corretta. (comunque il prof. Non vuole approfondirla tanto)

Elemento Massimale: se non c’è nessun altro elemento

→

strettamente più grande di lui. Figura (A) b,c,d sono

massimali

Elemento massimo: Quando l’elemento è massimale e

tutti gli altri elementi sono minori o uguali di lui. Figura

(C)→ d è l’elemento massimo (ovvero se ho un unico

massimale questo è il massimo).

→ →

Viceversa per i minimi figura (B) minimali a,b Figura (A)→a minimo

Upper bound: x è un upper bound per A se x è maggiore di tutti gli elementi y in A.

Se considero il sottoinsieme a,b,c allora e,f,j,h sono degli upper bound mentre g non può

esserlo perché non raggiunge c.

Viceversa per il lower bound.

Il più piccolo upper bound rispetto agli altri viene chiamato LUB. Nell’esempio a fianco il

LUB è e.

Qual è least upper bound se prendiamo l’insieme delle parti di S? L’unione dei suoi

sottoinsiemi.

Viceversa greatest lower bound: GLB

Ordinamento topologico: in figura viene mostrato i passaggi della costruzione di

una casa, ogni passo è in relazione con i successivi in base ad una precedenza. In

che ordine sequenziale posso schedulare tutti questi eventi rispettando le

precedenze che ci sono nel poset? Partiamo dall’insieme di tutte le attività, finché

ho un’attività da fare ne scelgo una minimale la tolgo dall’insieme e vado avanti 47

RELAZIONI DI EQUIVALENZA

Le relazioni di equivalenza sono: riflessive, simmetriche e transitive. ≠ relazioni di ordinamento che sono

riflessive, antisimmetriche e transitive. Gli elementi che sono nella relazione di equivalenza vengono

indicati così .

La relazione R tra due stringhe che vale se e solo se le due stringhe hanno la stessa lunghezza è una

relazione di equivalenza?

Dati due insiemi X e Y questi sono theta equivalenti se e solo se il cover (insieme delle transazioni che

includono quell’itemset) è il medesimo. Ad esempio, AC theta ACE vuol dire che in tutti i carrelli in cui

compare AC sono esattamente tutti i carelli in cui compare ACE.

Le relazioni di equivalenza sono importanti perché se vale la relazione di equivalenza possiamo guardare

gli elementi del dominio partizionandoli in classi.

Classe di equivalenza: prendendo un elemento A di una relazione R, la sua classe di equivalenza sono tutti

gli elementi che sono in relazione S con A in R. .

Esempi: Se avessi [5] avrei lo stesso insieme che

4

ottengo per uno, quindi notiamo che in realtà

che partendo da una relazione di equivalenza

le classi partizionano gli elementi del dominio in sottoinsiemi disgiunti. Questi sottoinsiemi possono essere

denotati da tutti gli elementi del sottoinsieme. 48

Cosa sarà una classe rispetto alla definizione di theta equivalenza? Sono tutti gli itemset che hanno lo

stesso cover. qual è l’importanza pratica di questa classe? Supponiamo di

voler analizzare tutti i carrelli che soddisfano un certo pattern.

Trovo il pattern AC e ci faccio un qualche ragionamento trovo il

pattern ACE e ci faccio altri ragionamenti. Ha senso ragionare in

questo modo? Non ha senso perché sto facendo 2 azioni che

vanno a colpire lo stesso cover di carrelli, sono due pattern che sono acquistati dalle stesse transazioni.

Quindi molto spesso non siamo interessati agli itemset frequenti ma alle loro classi di equivalenza.

Teorema delle classi di equivalenza: Sostanzialmente dice che A è in relazione con B se e

solo se le loro classi di equivalenza sono le stesse e non

sono vuote. Le classi di equivalenza quindi o coincidono

o sono disgiunte ovvero se hanno un elemento in

comune poi ce li hanno tutti.

La conseguenza di questo teorema è che le queste classi

partizionano il dominio in insiemi disgiunti. Cosa vuol dire

partizione? Collezione di sottoinsiemi non vuoti disgiunti a

coppie e la loro unione è l’intero insieme S.

Tra gli item che sono nella classe di equivalenza (ad esempio [AC] = {AC, ACE, ABCE} ce n’è uno più

rappresentativo degli altri? Si può dimostrare che nella classe esiste un item che è più lungo di tutti gli altri:

∈ ∈

AC è contenuto in ABCE e ACE è contenuto in ABCE. Perché esiste? Supponiamo che x [Z]0 e y [Z]0.

 ∈

Concluderò che x y [Z]. Quindi il cover di x e y è uguale al cover di Z.

L’item più lungo di tutti che allo stesso tempo è unico prende il nome di itemset chiuso. 49

CAPITOLO 13 – LINGUAGGI E GRAMMATICHE

I linguaggi naturali come quelli di programmazione seguono regole di:

Sintassi: forma della parola.

- Semantica: significato della parola, ciò che veicola.

-

Anche in Python notiamo che questi due aspetti sono fondamentali per la corretta esecuzione di un

programma che altrimenti viene interrotta.

SINTASSI

Le regole della sintassi all’interno dei linguaggi di programmazione vengono definiti tramite le

grammatiche.

Una grammatica formale è una struttura astratta che descrive un linguaggio tramite un sistema di regole

che delineano matematicamente un insieme di sequenza finite di simboli (stringhe) appartenenti a un

alfabeto anch’esso finito.

I linguaggi si definiscono formali quando posso definire se una stringa appartiene o meno a quel linguaggio.

Uso le grammatiche per formare asserzioni valide facendo una serie di sostituzioni fino a che non ci sono più

regole da applicare.

I simboli che possono essere sostituiti prendono il nome di simboli non terminali e vengono

- indicati con la lettera maiuscola. (per esempio: S→A (A è non terminale)

I simboli che non possono essere sostituiti prendono il nome di simboli terminali e vengono

- indicati con la lettera minuscola. (per esempio: S→a (a è non terminale)

Tali simboli appartengono a V, alfabeto o vocabolario della grammatica: un vocabolario è un

- insieme finito e non vuoto di simboli. V*: è l’insieme di tutte le stringhe appartenenti al

vocabolario V. Qualsiasi linguaggio definito su V è quindi un sottoinsieme di V*.

λ: indica la stringa vuota, non contenente nessun simbolo.

-

Una grammatica è una quadrupla G=(V,T,S,P):

- Vocabolario

- simboli Terminali

→

- Start symbo