Il teorema di Bondy

Il teorema di Bondy In matematica, Il teorema di Bondy è un limite al numero di elementi necessari per distinguere gli insiemi in una famiglia di insiemi l'uno dall'altro. Appartiene al campo della combinatoria, e prende il nome da John Adrian Bondy, in chi l'ha pubblicato 1972.[1] Contenuti 1 Dichiarazione 2 Esempio 3 Applicazione della teoria dell'apprendimento 4 Notes Statement The theorem is as follows: Sia X un insieme di n elementi e sia A1, A2, ..., An essere sottoinsiemi distinti di X. Then there exists a subset S of X with n − 1 elements such that the sets Ai ∩ S are all distinct.

In altre parole, se abbiamo un 0-1 matrice con n righe e n colonne in modo tale che ogni riga sia distinta, we can remove one column such that the rows of the resulting n × (n - 1) matrice sono distinti.[2][3] Example Consider the 4 × 4 matrice {stile di visualizzazione {inizio{bmatrice}1&1&0&1\0&1&0&1\0&0&1&1\0&1&1&0end{bmatrice}}} dove tutte le righe sono distinte a coppie. Se cancelliamo, Per esempio, la prima colonna, la matrice risultante {stile di visualizzazione {inizio{bmatrice}1&0&1\1&0&1\0&1&1\1&1&0end{bmatrice}}} non ha più questa proprietà: la prima riga è identica alla seconda riga. Tuttavia, dal teorema di Bondy sappiamo che possiamo sempre trovare una colonna che può essere cancellata senza introdurre righe identiche. In questo caso, possiamo eliminare la terza colonna: all rows of the 3 × 4 matrice {stile di visualizzazione {inizio{bmatrice}1&1&1\0&1&1\0&0&1\0&1&0end{bmatrice}}} sono distinti. Un'altra possibilità sarebbe stata eliminare la quarta colonna.

Learning theory application From the perspective of computational learning theory, Il teorema di Bondy può essere riformulato come segue:[4] Sia C una classe concettuale su un dominio finito X. Allora esiste un sottoinsieme S di X con la dimensione al massimo |C| − 1 such that S is a witness set for every concept in C.

Ciò implica che ogni classe di concetti finiti C ha la sua dimensione di insegnamento delimitata da |C| − 1.

Note ^ Bondy, J. UN. (1972), "Sottoinsiemi indotti", Rivista di teoria combinatoria, Serie B, 12: 201–202, doi:10.1016/0095-8956(72)90025-1, SIG 0319773. ^ Yukna, Stasi (2001), Combinatoria estrema con applicazioni in informatica, Springer, ISBN 978-3-540-66313-3, Sezione 12.1. ^ Cloto, Peter; Remme, Jeffrey B. (1995), Matematica fattibile II, Birkhauser, ISBN 978-3-7643-3675-2, Sezione 4.1. ^ Kushilevitz, Eyal; lineare, Nathan; Rabinovich, Yuri; Saks, Michael (1996), "Set di testimoni per famiglie di vettori binari", Rivista di teoria combinatoria, Serie A, 73 (2): 376–380, doi:10.1016/S0097-3165(96)80015-X, SIG 1370141. Categorie: Teoria dell'apprendimento computazionale Teoremi in combinatoria