Pytania otagowane jako combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

11
Rozwiązywanie lub aproksymacja relacji powtarzalności dla sekwencji liczb
W informatyce często musimy rozwiązywać relacje powtarzalności , to znaczy znaleźć zamkniętą formę dla rekurencyjnie zdefiniowanej sekwencji liczb. Rozważając środowiska wykonawcze, często jesteśmy zainteresowani głównie asymptotycznym wzrostem sekwencji . Przykładami są Czas działania funkcji rekurencyjnej ogona schodzącej w dół do 000 od nnn którego ciało wymaga czasu f(n)f(n)f(n) : T(0)T(n+1)=0=T(n)+f(n)T(0)=0T(n+1)=T(n)+f(n)\qquad …
2
Dlaczego jest więcej funkcji, które nie są obliczalne niż funkcje obliczalne?
Obecnie czytam książkę o algorytmach i złożoności. W tej chwili czytam o funkcjach obliczalnych i niepoliczalnych, a moja książka stwierdza, że ​​jest o wiele więcej funkcji, które nie są obliczalne niż obliczalne, w rzeczywistości większość jest niepoliczalna. W pewnym sensie intuicyjnie mogę to zaakceptować, ale książka nie daje formalnego dowodu …
2
Liczenie drzew binarnych
(Jestem studentem z pewnym doświadczeniem matematycznym i chciałbym wiedzieć, jak policzyć liczbę określonego rodzaju drzew binarnych). Patrząc na stronę Wikipedii dotyczącą drzew binarnych , zauważyłem to twierdzenie, że liczba zakorzenionych drzew binarnych o rozmiarze będzie katalońską : C_n = \ dfrac {1} {n + 1} {2n \ wybierz n}nnnCn=1n+1(2nn)Cn=1n+1(2nn)C_n = …
2
Wydajny algorytm do „sumowania” zestawu sum
Biorąc pod uwagę zbiór wielu liczb naturalnych X, rozważ zestaw wszystkich możliwych sum: sums(X)={∑i∈Ai|A⊆X}sums(X)={∑i∈Ai|A⊆X}\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\} Na przykład podczas gdy .sumy ( { 1 , 1 } ) = { 0 , 1 , 2 }sums({1,5})={0,1,5,6}sums({1,5})={0,1,5,6}\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}sums({1,1})={0,1,2}sums({1,1})={0,1,2}\textrm{sums}(\left\{1,1\right\}) = …
1
Jak fundamentalne są matroidy i greedoidy w projektowaniu algorytmów?
Początkowo wprowadzono matroidy , aby uogólnić pojęcia liniowej niezależności zbioru podzbiorów stosunku do zbioru I podłoża . Niektóre problemy, które zawierają tę strukturę, pozwalają chciwym algorytmom znaleźć optymalne rozwiązania. Koncepcja greedoidów została później wprowadzona w celu uogólnienia tej struktury, aby uchwycić więcej problemów, które pozwalają na znalezienie optymalnych rozwiązań za …
1
Reklamacja pizzy w wysokości 34 milionów kombinacji
Reklama pizzy twierdzi, że możesz połączyć ich składniki z 34 milionami różnych kombinacji. Nie wierzyłem w to, więc odkurzyłem swoje zardzewiałe umiejętności kombinatoryczne i próbowałem to rozgryźć. Oto, co do tej pory mam: z witryny zamawiania online mam wybór skorupa (4 rodzaje, wybierz 1) rozmiar (4 typy, wybierz 1) niektóre …
1
Czy każdy wystarczająco duży ciąg ma powtórzenia?
Niech będzie skończonym zestawem znaków o ustalonym rozmiarze. Niech będzie ciągiem znaków nad . Mówimy, że niepusty substrat z jest powtórzeniem, jeśli dla jakiegoś ciągu .α Σ β αΣΣ\Sigmaαα\alphaΣΣ\Sigmaββ\betaαα\alphaγβ= γγβ=γγ\beta = \gamma \gammaγγ\gamma Teraz moje pytanie dotyczy tego, czy: Dla każdego istnieje pewna liczba taka, że ​​dla każdego łańcucha powyżej …
1
Złożoność znalezienia współczynnika dwumianowego równego liczbie
Załóżmy, że otrzymujesz liczbę mmm (używając O(logm)O(log⁡m)O(\log m) bitów w kodowaniu binarnym). Jak szybko można znaleźć (lub stwierdzić, że takie nie istnieje) ?n,k∈N,1&lt;k≤n2:(nk)=mn,k∈N,1&lt;k≤n2:(nk)=mn,k\in \mathbb N, 1<k\leq\frac{n}{2}:{n \choose k}=m Na przykład, biorąc pod uwagę wejście , można wyprowadzić .m=8436285m=8436285m=8436285n=27,k=10n=27,k=10n=27, k=10 Naiwny algorytm dla problemu przekroczyłby wszystkie możliwe wartości dla i szukałby …
2
Ile krawędzi może mieć wykres unipatyczny?
Wykres unipatyczny jest wykresem ukierunkowanym, tak że istnieje co najwyżej jedna prosta ścieżka z jednego wierzchołka do dowolnego innego wierzchołka. Wykresy unipatyczne mogą mieć cykle. Na przykład podwójnie połączona lista (nie okrągła!) Jest grafem unipatycznym; jeśli lista zawiera elementów, wykres ma cykli o długości 2, w sumie .n - 1 …
1
Liczba cykli hamiltonowskich na wykresie Sierpińskiego
Jestem nowy na tym forum i jestem tylko fizykiem, który robi to, aby utrzymać swój mózg w dobrej formie, więc proszę okaż łaskę, jeśli nie używam najbardziej eleganckiego języka. Proszę również zostawić komentarz, jeśli uważasz, że inne tagi byłyby bardziej odpowiednie. Próbuję rozwiązać ten problem, dla którego muszę obliczyć liczbę …
4
Rekurencje i funkcje generujące w algorytmach
Kombinatoryka odgrywa ważną rolę w informatyce. Często stosujemy metody kombinatoryczne zarówno w analizie, jak i projektowaniu w algorytmach. Na przykład jedna metoda znajdowania zestawu okładek kkk -vertex na wykresie może po prostu sprawdzić wszystkie możliwe podzbiory . Podczas gdy funkcje dwumianowe rosną wykładniczo, jeśli jest jakąś stałą stałą, w wyniku …
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.