Pytania otagowane jako co.combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

2
Znajdź wszystkie pary wartości bliskich odległości Hamminga
Mam kilka milionów wartości 32-bitowych. Dla każdej wartości chcę znaleźć wszystkie inne wartości w odległości Hamminga wynoszącej 5. W podejściu naiwnym wymaga to porównań O(N2)O(N2)O(N^2) , których chcę uniknąć. Uświadomiłem sobie, że jeśli potraktowałem te 32-bitowe wartości jako liczby całkowite i posortowałem listę raz, to wartości, które różniły się tylko …
1
Najnowocześniejszy system słonecznika
Interesuje mnie system słonecznika i jego zastosowania w informatyce. Biorąc pod uwagę Wszechświat i zbiór k zbiorów A i nazywa się układem k-słonecznika, jeśli A i ∩ A j = Y dla wszystkich i ≠ j . A Y nazywa się rdzeniem, a A i - Y nazywa się płatkami. …
2
Pokryj wielokąt wklęsły minimalną liczbą prostokątów
Próbuję pokryć prosty wklęsły wielokąt minimalnymi prostokątami. Moje prostokąty mogą mieć dowolną długość, ale mają maksymalną szerokość, a wielokąt nigdy nie będzie miał ostrego kąta. Pomyślałem o próbie rozłożenia mojego wklęsłego wielokąta na trójkąty, które wytwarzają zestaw minimalnie nakładających się prostokątów minimalnie ograniczających każdy trójkąt, a następnie łączenie tych prostokątów …
1
Prosty (?) Śmieszny problem kombinatoryczny!
Pozwólmy naprawić 0<E<10<E<100 . dla dowolnego nnn i dla dowolnego wektora c¯∈[0,1]nc¯∈[0,1]n\bar{c} \in [0,1]^n taki, że ∑i∈[n]ci≥E×n∑i∈[n]ci≥E×n\sum_{i\in [n]} c_i \geq E \times n Ac¯:=|{S⊆[n]:∑i∈S ci≥E×t}|≥(E×nt)Ac¯:=|{S⊆[n]:∑i∈S ci≥E×t}|≥(E×nt)A_{\bar{c}} :=|\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \times t \}| \geq \binom{ E \times n}{ t } Nie wiem, czy …
2
Rozpuszczalność wypełnienia matrycy
Macierz ma wymiar n × n ( n - 1 ) . Chcemy wypełnić A za pomocą liczb całkowitych od 1 do n włącznie.AAAn×n(n−1)n×n(n−1)n \times n(n-1)AAA111nnn Wymagania: Każda kolumna jest permutacją 1 , … , n .AAA1,…,n1,…,n1, \dots, n Żadna submatrix utworzona z dwóch rzędów nie może mieć identycznych kolumn.AAA …
3
Regularne wykresy i izomorfizm
Chciałbym zapytać, czy jest na to już opublikowany wynik: Bierzemy wszystkie możliwe różne ścieżki między każdą parą węzłów dwóch połączonych regularnych (o powiedzmy stopnia , i liczby węzłów ) wykresów i zapisujemy ich długości. Oczywiście ta liczba odrębnych ścieżek ma charakter wykładniczy. Moje pytanie brzmi: jeśli posortujemy długości i porównamy …
1
Obliczanie maks. Zestawów wolnych od H
Na wykresie niezależny zestaw jest podzbiorem wierzchołków, który nie zawiera krawędzi jako indukowanego podsgrafu. Problem znajdowania największych niezależnych zestawów na wykresie jest fundamentalnym zagadnieniem algorytmicznym i trudnym. Rozważmy bardziej ogólne pytanie dotyczące znalezienia (wielkości) największego zestawu wolnego od H na wykresie, gdzie wolny od H oznacza, że ​​nie indukuje on …
2
Losowy spacer i średni czas trafienia na prostym niekierowanym wykresie
Niech będzie prostym nieukierowanym wykresem na wierzchołkach i krawędziach.n mG=(V,E)sol=(V.,mi)G=(V,E)nnnmmm Próbuję określić czas oczekiwany prowadzeniem algorytmu Wilsona do generowania losowych rozpinające drzewo . Tam pokazano, że to , gdzie to średni czas uderzenia : gdzie:O ( τ ) τGsolGO(τ)O(τ)O(\tau)ττ\tauτ=∑v∈Vπ(v)⋅H(u,v),τ=∑v∈V.π(v)⋅H.(u,v),\tau = \sum_{v \in V} \pi(v) \cdot H(u, v), ππ\pi to rozkład …
1
Błąd logiczny korygujący kod w
Czy istnieje znana konstrukcja kodu korygującego błędy liniowe (z rozsądnymi parametrami), na przykład gdy podano logiczny wektor zwraca również wartość logiczną wektora logicznego? (chociaż to koniec \ mathbb {F} _q )ECC:Fnq→FmqECC:Fqn→Fqm\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^mv∈{0,1}nv∈{0,1}nv\in \{0,1\}^nFqFq\mathbb{F}_q (to znaczy Pr[ECC(v)∈{0,1}m]>1−ϵPr[ECC(v)∈{0,1}m]>1−ϵ\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon , gdzie prawdopodobieństwo jest przejmowane równomiernie wybierając v∈{0,1}nv∈{0,1}nv\in \{0,1\}^n , a …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.