 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[HELP] Matroidi
Clicca QUI per vedere il messaggio nel forum |
| kingoff |
Scusate ragazzi ma non riesco a capire veramente cosa sono i matroidi...ho imparato la definizione a memoria, ma non mi è ancora familiare il concetto...non sono riuscito ad acquisirlo...sarò un po' stupido!:oops:
Qualche anima gentile mi spiega in modo terra terra cosa sono e a che servono???:)
Grazie!! |
| kingoff |
| dai....una rispostina... |
| yoruno |
| Magari su Wikipedia trovi qualche esempio che ti possa aiutare :) |
| maynard80 |
| anche su wiki è spiegato in maniera complicata... nessuno sa spiegarlo in maniera + terra terra? |
| NoWhereMan |
nota: con 2^E indico 2 con E scritto all'apice, come nelle potenze, e con {} l'insieme vuoto
Si abbiano due insiemi E ed F, dove F è un sottoinsieme delle parti di E con due particolari proprietà
dati
E={a,b,c}
P(E) = 2^E = { {}, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c} }
Gli elementi dell'insieme delle parti di E (ricordiamolo), come si vede, sono a loro volta degli insiemi.
La coppia <E, F> è un sistema di indipendenza se, presi due elementi di F, se A è elemento di F, e B è sottoinsieme di A allora B è elemento di F;
ad esempio se F1 = { {}, {b}, {a}, {a, b} } //mi sorge un dubbio... {} fa parte di F1?? :/
<E, F1> è s.i. infatti {a,b} elem di F1, {b} è contenuto in {a,b}, e anche {b} è elem di F1
Un matroide è un s.i. tale che presi due elementi A,B, di F (i quali, ricordiamolo ancora, sono insiemi), se la cardinalità di B è uguale alla cardinalità di A meno uno, cioè se |A| = |B| + 1, ovverosia se A ha un elemento in più di B, allora esiste un elemento "b" contenuto in B ma non in A allora l'unione tra {b} e A è comunque un elemento del matroide.
F1, per esempio, dovrebbe essere un matroide :B
infatti presi B={a} e A={a,b}, |{a}|=1, |{a,b}|=2,
la differenza tra A e B, A-B = {b}
che è proprio l'elemento che unito a B dà ancora A
si noti che <E,P(E)> è un matroide (e quindi anche un s.i.)
spero di essere stato d'aiuto :/
ciao |
|
|
|
|
