Pytania otagowane jako combinatorics

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) …

17 formal-languages  regular-languages  combinatorics  word-combinatorics 

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ę …

16 combinatorics  modelling  information-theory  sudoku 

Pracowałem nad następującym problemem z tej książki . Pewien język przetwarzania ciągów oferuje prymitywną operację, która dzieli ciąg na dwie części. Ponieważ ta operacja polega na skopiowaniu oryginalnego ciągu, n zajmuje ciąg n jednostek czasu o długości n, niezależnie od lokalizacji cięcia. Załóżmy teraz, że chcesz rozbić sznurek na wiele …

16 algorithms  combinatorics  strings  dynamic-programming 

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. …

15 algorithms  turing-machines  combinatorics 

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 ) …

15 algorithms  combinatorics 

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 …

15 combinatorics  discrete-mathematics  trees  average-case  random-walks 

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 …

14 algorithms  algorithms  machine-learning  statistics  testing  terminology  asymptotics  landau-notation  reference-request  optimization  scheduling  complexity-theory  time-complexity  lower-bounds  communication-complexity  computational-geometry  computer-architecture  cpu-cache  cpu-pipelines  operating-systems  multi-tasking  algorithms  algorithm-analysis  education  correctness-proof  didactics  algorithms  data-structures  time-complexity  computational-geometry  algorithms  combinatorics  efficiency  partitions  complexity-theory  satisfiability  artificial-intelligence  operating-systems  performance  terminology  computer-architecture 

Biorąc pod uwagę alfabet Σ = { a , b }Σ={za,b}\Sigma = \{ a,b \} , ile jest różnych języków regularnych, które może zaakceptować nnn stanowy niedeterministyczny automat skończony? Jako przykład rozważmy n=3n=3n=3 . Następnie mamy 2182182^{18} różnych konfiguracji przejścia i 23232^3 różne konfiguracje stanu początkowego i końcowego, więc mamy …

14 formal-languages  regular-languages  finite-automata  combinatorics 

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 …

14 graph-theory  combinatorics  cryptography  discrete-mathematics  expanders 

Jeśli wykres jest połączony i nie ma ścieżki o długości większej niż k , udowodnij, że co dwie ścieżki w G o długości k mają co najmniej jeden wspólny wierzchołek. GGGkkkGGGkkk Myślę, że ten wspólny wierzchołek powinien znajdować się na środku obu ścieżek. Ponieważ jeśli tak nie jest, możemy mieć …

14 graph-theory  graphs  combinatorics 

Próbuję udowodnić, że drzewo binarne z węzłami ma co najwyżej ⌈ nnnnliści. Jak miałbym to robić z indukcją?⌈n2⌉⌈n2⌉\left\lceil \frac{n}{2} \right\rceil Dla osób, które śledziły pierwotne pytanie o stosy, zostało tu przeniesione .

14 data-structures  binary-trees  combinatorics  graph-theory  proof-techniques 

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 …

13 algorithms  combinatorics  probability-theory  permutations  sampling 

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 …

13 data-structures  combinatorics  binary-trees  search-trees  graph-traversal 

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 …

12 combinatorics  balls-and-bins 

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 …

11 combinatorics