Pytania otagowane jako combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

3
Liczba słów w zwykłym języku
Według Wikipedii , dla każdego zwykłego języka istnieją stałe i wielomiany takie, że dla każdego liczby słów o długości w spełnia równanieLLLλ1,…,λkλ1,…,λk\lambda_1,\ldots,\lambda_kp1(x),…,pk(x)p1(x),…,pk(x)p_1(x),\ldots,p_k(x)nnnsL(n)sL(n)s_L(n)nnnLLL sL(n)=p1(n)λn1+⋯+pk(n)λnksL(n)=p1(n)λ1n+⋯+pk(n)λkn\qquad \displaystyle s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n . Język L={02n∣n∈N}L={02n∣n∈N}L =\{ 0^{2n} \mid n \in\mathbb{N} \} jest zwykły ( (00)∗(00)∗(00)^* pasuje do niego). sL(n)=1sL(n)=1s_L(n) = 1 iff n jest parzyste, a sL(n)=0sL(n)=0s_L(n) …

1
Skuteczne kodowanie łamigłówek sudoku
Określenie dowolnej dowolnej siatki 9x9 wymaga podania pozycji i wartości każdego kwadratu. Naiwne kodowanie tego może dać 81 (x, y, wartość) trypletów, wymagając 4 bitów dla każdego x, y i wartości (1-9 = 9 wartości = 4 bity) w sumie 81x4x3 = 972 bitów. Numerując każdy kwadrat, można zmniejszyć informację …


8
Kardynalność zbioru algorytmów
Ktoś w dyskusji przywołał, że (uważa) może istnieć co najmniej ciągła liczba strategii podejścia do określonego problemu. Specyficznym problemem były strategie handlowe (nie algorytmy, ale strategie), ale myślę, że to nie ma znaczenia dla mojego pytania. To sprawiło, że pomyślałem o liczności zbioru algorytmów. Trochę szukałem, ale nic nie wymyśliłem. …

1
Konstruowanie nierównych macierzy binarnych
Próbuję skonstruować wszystkie nierówne macierze (lub n × n, jeśli chcesz) z elementami 0 lub 1. Operacją, która daje macierze równoważne, jest jednoczesna wymiana wiersza i i j ORAZ kolumny i i j. na przykład. dla 1 ↔ 2 ( 0 0 0 0 1 1 1 0 0 ) …

1
O „Średniej wysokości posadzonych platanów” Knuth, de Bruijn i Rice (1972)
Staram się czerpać z klasycznej pracy tytułowej tylko elementarne środki (bez funkcji generujących, bez złożonej analizy, bez analizy Fouriera), choć ze znacznie mniejszą precyzją. Krótko mówiąc, „tylko” chcę udowodnić, że średnia wysokość drzewa z węzłami (to znaczy maksymalną liczbą węzłów od korzenia do liścia) spełnia .hnhnh_nnnnhn∼πn−−−√hn∼πnh_n \sim \sqrt{\pi n} Zarys …

6
Znalezienie maksymalnego XOR dwóch liczb w przedziale: czy możemy zrobić coś lepszego niż kwadratowy?
Załóżmy, że otrzymaliśmy dwie liczby i i że chcemy znaleźć dla l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Naiwny algorytm sprawdza po prostu wszystkie możliwe pary; na przykład w rubinie mielibyśmy: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if …


2
Jak praktycznie konstruować zwykłe wykresy ekspanderów?
Muszę skonstruować wykres ekspandera regularnego d dla niektórych małych stałych d (jak 3 lub 4) n wierzchołków. Jaka jest najłatwiejsza metoda na zrobienie tego w praktyce? Konstruujesz losowy wykres d-regularny, który okazał się być ekspanderem? Czytałem także o konstrukcjach Margulis i grafach Ramanujana, które są ekspanderami i konstrukcją wykorzystującą produkt …



2
Wydajny algorytm do generowania losowo dwóch rozproszonych, obłąkanych permutacji multiset
tło \newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak S}\newcommand\mfm[1]{#1}\def\po{\color{#f63}{\mfm{1}}}\def\pc{\color{#6c0}{\mfm{c}}}\def\pt{\color{#08d}{\mfm{2}}}\def\pth{\color{#6c0}{\mfm{3}}}\def\pf{4}\def\pv{\color{#999}5}\def\gr{\color{#ccc}}\let\ss\gr Załóżmy, że mam dwie identyczne partie nnn kulek. Każdy marmur może mieć jeden z kolorów ccc , gdzie c≤nc≤nc≤n . Niech ninin_i oznacza liczbę kulek koloru iii w każdej partii. Niech SS\msS będzie multiset {1,…,1n1,2,…,2n2,…,1c,…,cnc}{1,…,1⏞n1,2,…,2⏞n2,…,1c,…,c⏞nc}\small\{\overbrace{\po,…,\po}^{n_1},\;\overbrace{\pt,…,\pt}^{n_2},\;…,\;\overbrace{\vphantom 1\pc,…,\pc}^{n_c}\} reprezentujący jedną partię. W reprezentacji częstotliwości , SS\msS …

2
Liczba możliwych ścieżek wyszukiwania podczas wyszukiwania w BST
Mam następujące pytanie, ale nie mam na to odpowiedzi. Byłbym wdzięczny, jeśli moja metoda jest poprawna: P: Podczas wyszukiwania wartości klucza 60 w drzewie wyszukiwania binarnego węzły zawierające wartości klucza 10, 20, 40, 50, 70, 80, 90 są przemieszczane, niekoniecznie w podanej kolejności. Ile jest możliwych różnych zamówień, w których …

1
Napełnianie pojemników parami kulek
Kosz jest nazywany pełnym, jeśli zawiera co najmniej kulek. Naszym celem jest, aby jak najwięcej pojemników było pełnych.kkk W najprostszym scenariuszu otrzymujemy piłek i możemy je dowolnie rozmieścić. W takim przypadku, oczywiście najlepsze, co możemy zrobić, to wybrać kosze i umieścić dowolnie kulki w każdej z nich.nnn⌊n/k⌋⌊n/k⌋\lfloor n/k \rfloorkkk Interesuje …

3
Reprezentuj układ 5 kart
Talia kart to 52. Ręka to 5 kart z 52 (nie może mieć duplikatu). Jaka jest najmniejsza liczba bitów reprezentująca układ 5 kart i jak? Ręka NIE jest zależna od kolejności (KQ = QK). 64329 = 96432 Tak, można użyć 52 bitów. Może to stanowić układ dowolnej liczby kart. Biorąc …

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.