Pytania otagowane jako combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

2
Uprość złożoność n multichoose k
Mam algorytm rekurencyjny o złożoności czasowej równoważnej do wybierania elementów k z powtórzeniem i zastanawiałem się, czy mogę uzyskać bardziej uproszczone wyrażenie big-O. W moim przypadku może być większe niż i rosną one niezależnie.kkknnn W szczególności oczekiwałbym wyraźnego wyrażenia wykładniczego. Najlepsze, jakie do tej pory mogłem znaleźć, to oparte na …
1
Jaki jest kompaktowy sposób reprezentowania partycji zestawu?
Istnieją wydajne struktury danych do reprezentowania ustawionych partycji. Te struktury danych charakteryzują się dużą złożonością czasową dla operacji takich jak Union i Find, ale nie są szczególnie efektywne pod względem przestrzeni. Jaki jest oszczędny przestrzennie sposób reprezentowania partycji zestawu? Oto jeden z możliwych punktów wyjścia: Wiem, że liczba partycji zestawu …
2
Czy ten kombinatoryczny problem optymalizacji jest podobny do jakiegokolwiek znanego problemu?
Problem jest następujący: Mamy dwuwymiarową tablicę / siatkę liczb, z których każda reprezentuje pewną „korzyść” lub „zysk”. Także ma dwie nieruchome całkowite i h (jako „szerokość” i „wysokość”). A stałej całkowitej n .wwwhhhnnn Teraz chcą nałożyć prostokątów o wymiarach szer × h na siatce, tak aby łączna suma wartości komórek …
3
Podczas testowania n elementów, jak pokryć wszystkie podzbiory t przez jak najmniejszą liczbę podzbiorów s?
Ten problem powstał w wyniku testowania oprogramowania. Problem jest trochę trudny do wyjaśnienia. Najpierw podam przykład, a następnie spróbuję uogólnić problem. Do przetestowania jest 10 elementów, od A do J, oraz narzędzie testujące, które może testować 3 elementy jednocześnie. Kolejność elementów w narzędziu testowym nie ma znaczenia. Oczywiście do wyczerpujących …
2
Jaka jest średnia wysokość drzewa binarnego?
Czy istnieje formalna definicja średniej wysokości drzewa binarnego? Mam pytanie instruktażowe dotyczące znalezienia średniej wysokości drzewa binarnego przy użyciu następujących dwóch metod: Naturalnym rozwiązaniem może być przyjęcie średniej długości wszystkich możliwych ścieżek od korzenia do liścia avh1(T)=1# leaves in T⋅∑v leaf of Tdepth(v)avh1⁡(T)=1# leaves in T⋅∑v leaf of Tdepth⁡(v)\qquad \displaystyle …
2
Jak sklasyfikować problem optymalizacji wejścia emulatora i z jakim algorytmem powinienem do niego podejść?
Ze względu na charakter pytania muszę podać wiele podstawowych informacji (ponieważ moje pytanie brzmi: jak to zawęzić?) To powiedziawszy, można je streścić (o ile wiem): Jakie metody istnieją, aby znaleźć lokalne optimum na bardzo dużych kombinatorycznych przestrzeniach poszukiwań? tło W społeczności superplay wspieranych narzędziami staramy się zapewnić specjalnie spreparowane (nie …
1
Stabilność dla par w problemie ze stabilnym dopasowaniem
W Stable Matching Problem stwierdzono, że mogą istnieć przypadki, w których lista mężczyzn może być zadowolona z ich decyzji, ale lista f nie może, gdy algorytm jest uruchamiany z propozycjami mężczyzn.mmmfff Z tego, co przeczytałem, niestabilne dopasowanie występuje, gdy i f wolą się od swoich obecnych partnerów.mmmfff Jestem trochę zagubiony …
2
Znajdź optymalne zamówienie
Natknąłem się na ten problem i staram się znaleźć sposób, aby go rozwiązać. Jakiekolwiek propozycje będą mile widziane! Załóżmy, że mamy matrycę {−1,0,1}n × k{−1,0,1}n × k\{-1, 0, 1\}^{n\ \times\ k} , na przykład, ⎡⎣⎢⎢⎢⎢⎢⎢1−10−11001−101010000010−11−11−1⎤⎦⎥⎥⎥⎥⎥⎥[1010−1−100010110−1−1−10111000−1]\begin{bmatrix} 1 & 0 & 1 & 0 & -1 \\ -1 & 0 & 0 …
1
Najcięższy plansza podrzędna
Rozważ następujący problem. Biorąc pod uwagę: Pełny wykres z rzeczywistymi nieujemnymi wagami na krawędziach. Zadanie: znajdź płaski wykres podrzędny o maksymalnej masie. („Maksimum” wśród wszystkich możliwych płaskich wykresów podrzędnych.) Uwaga: Podgraf maksymalnej wagi będzie triangulacją; jeśli cały wykres jest na wierzchołkach, będzie miał krawędzi.nnnm = 3 n - 6m=3)n-6m=3n-6 Pytanie: …
1
Unikalne nachylenie kwadratów
Chcemy kafelki m×mm×mm\times m-kwadrat przy użyciu dwóch rodzajów kafelków: 1×11×11 \times 1- kwadratowa płytka i 2×22×22 \times 2- kwadratowy kafelek, tak aby każdy leżący pod nim kwadrat był przykryty bez nakładania się. Zdefiniujmy funkcjęf(n)f(n)f(n) co daje rozmiar największego, unikalnego, możliwego do uprawy kwadratu nnn 1×11×11\times 1- kwadraty i dowolna liczba …
1
Wyrażanie arbitralnej permutacji jako sekwencji operacji (wstawianie, przenoszenie, usuwanie)
Załóżmy, że mam dwa ciągi. Nazywamy je i . Żaden ciąg nie ma powtarzających się znaków.AAABBB Jak znaleźć najkrótszą sekwencję operacji wstawiania, przenoszenia i usuwania, która zamienia w , gdzie:AAABBB insert(char, offset)wstawia charna podany offsetw ciągu move(from_offset, to_offset)przesuwa postać aktualnie przesuniętą from_offsetdo nowej pozycji, tak aby przesunęła sięto_offset delete(offset) usuwa …
3
Minimalna liczba wskazówek, aby w pełni określić jakieś sudoku?
Wiemy z tego artykułu , że nie istnieje układanka, którą można rozwiązać, zaczynając od 16 lub mniej wskazówek, ale sugeruje, że istnieje układanka, którą można rozwiązać na podstawie 17 wskazówek. Czy wszystkie prawidłowe łamigłówki sudoku można podać w 17 wskazówkach? Jeśli nie, jaka jest minimalna liczba wskazówek, które mogą całkowicie …
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.