Teoretyczne informatyka ds.algorithms

1

Interesuje mnie wariant maksymalnego dopasowania wagi na wykresie, który nazywam „maksymalnym uczciwym dopasowaniem”. Załóżmy, że wykres jest pełny (tj E=V×VE=V×VE=V\times V) Ma liczbę nawet wierzchołków, a masa jest podawana przez funkcję zysk . Biorąc pod uwagę pasujące , oznacz przez zysk krawędzi jest dopasowany.p:(V2)→Np:(V2)→Np:{V\choose 2}\to \mathbb NMMMM(v)M(v)M(v)vvv Pasujące jest sprawiedliwym …

9 ds.algorithms graph-algorithms np-hardness matching bipartite-graphs

1

Znajdowanie podobnych wektorów w czasie subkwadratowym

Pozwolić d:{0,1}k×{0,1}k→Rd:{0,1}k×{0,1}k→Rd:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}być funkcją, którą nazywamy funkcją podobieństwa . Przykłady funkcji podobieństwa to odległość cosinus,l2l2l_2 norma, odległość Hamminga, podobieństwo Jaccard itp. Rozważać nnn binarne wektory długości kkk: v⃗ ∈({0,1}k)nv→∈({0,1}k)n\vec{v} \in (\{0,1\}^k)^n. Naszym celem jest grupowanie wektorów, które są podobne. Bardziej formalnie chcemy obliczyć wykres podobieństwa, w którym węzły …

9 ds.algorithms graph-algorithms clustering

1

Sekretarka zatrudniająca

Jest to rozszerzenie klasycznego problemu sekretarza . W grze o zatrudnianie masz zestaw kandydatów i porządek na temat umiejętności każdego pracownika.C={c1,…,cN}C={c1,…,cN}\mathcal C=\{c_1,\ldots,c_N\} Wlog, zakładamy, że jest najbardziej wykwalifikowany, a następnie itd.c1c1c_1c2c2c_2 Kolejność, w jakiej kandydaci są wybierani losowo, jest jednolita i (oczywiście) nieznana pracodawcom. Załóżmy teraz, że masz rynek z …

9 ds.algorithms gt.game-theory

1

Sprawdzanie, czy wielomian wpływa na czynniki liniowe

Niech będzie wielomianem podanym przez obwód arytmetyczny o rozmiarze . Biorąc pod uwagę jako dane wejściowe, czy istnieje algorytm deterministyczny, aby sprawdzić, czy wszystkie nieredukowalne czynniki w są formami liniowymi? W pokrewnej uwadze, biorąc pod uwagę postać liniową , możemy sprawdzić deterministycznie, czy jest współczynnikiem . Oczywiście chcemy, aby czas …

9 ds.algorithms algebraic-complexity arithmetic-circuits

1

Podzielić zbiór punktów na dwa optymalne podzbiory

Chcę podzielić zestaw punktów na dwa równe podzbiory, aby zminimalizować sumę kwadratów wewnątrz klastra. Możemy założyć, że punkty znajdują się w dwuwymiarowej przestrzeni euklidesowej. Mam nadzieję na coś szybszego niż ogólny algorytm grupowania k-średnich, biorąc pod uwagę, że k = d = 2. Czy ktoś może wskazać mi dobry algorytm? …

9 ds.algorithms approximation-algorithms clustering

2

Wybierz dwie liczby, które sumują się do , używając sublinearnego czasu zapytania

Oto problem najbliższego sąsiada. Biorąc pod uwagę liczby rzeczywiste (bardzo duże !), Plus cel rzeczywisty , znajdź i których SUMA jest najbliższe . Umożliwiamy rozsądne wstępne przetwarzanie / indeksowanie (do ), ale w czasie zapytania (dane ) wynik powinien zostać zwrócony bardzo szybko (np. czas).za1, ... ,zana1,…,ana_1, \ldots, a_nnnnpppzajaaia_izajotaja_jpppza1, ... …

9 ds.algorithms cg.comp-geom ds.data-structures

1

Znalezienie optymalnej równoległości z ogólnego ważonego niekierowanego wykresu

Rozwiązuję problem „mieszania” zestawów nakładających się obrazów. Te zestawy mogą być reprezentowane przez niekierowany ważony wykres, taki jak ten: Każdy węzeł reprezentuje obraz. Nakładające się obrazy są połączone krawędzią. Ciężar krawędzi reprezentuje wielkość obszaru nakładania się ( wcześniejsze połączenie większego nakładania prowadzi do lepszej ogólnej jakości ). Algorytm ogólnie usuwa …

9 ds.algorithms graph-theory graph-algorithms directed-acyclic-graph parallel

1

Heapsort: Heaps = ~ Quicksort: BSTs = ~ Mergesort: ___?

Proszę wybaczyć zwięzłość tytułu, mogłem poświęcić jasność na ołtarzu zwięzłości. Widać, że wstawienie elementów tablicy do binarnego drzewa wyszukiwania i ich ponowne odczytanie wymaga (przy wstawianiu) takich samych porównań, jak uruchomienie Quicksort na tej tablicy. Sekwencja osi przestawnych używanych przez Quicksort to sekwencja wstawek do drzewa wyszukiwania binarnego. Jest to …

9 ds.algorithms ds.data-structures sorting

3

Znajdź pozostałą część dużego stałego wielomianu po podzieleniu przez niewielki nieznany wielomian

Załóżmy, że działamy w polu skończonym. Otrzymujemy duży stały wielomian p (x) (powiedzmy stopnia 1000) nad tym polem. Ten wielomian jest znany wcześniej i możemy wykonywać obliczenia przy użyciu dużej ilości zasobów w „fazie początkowej”. Wyniki te mogą być przechowywane w stosunkowo małych tabelach przeglądowych. Pod koniec „fazy początkowej” otrzymamy …

9 cc.complexity-theory ds.algorithms algebra algebraic-complexity polynomials

1

Zwiększenie wydajności w celu maksymalizacji minimalnego cięcia

Rozważ wykres ze wszystkimi krawędziami o pojemności jednostkowej. Można znaleźć min. Cięcie w czasie wielomianowym. Załóżmy, że mogę zwiększyć pojemność dowolnego kkkkrawędzie do nieskończoności (równoważne scalaniu węzłów po obu stronach krawędzi). Jaki jest optymalny sposób wyboru optymalnego zestawukkk krawędzie (których pojemność zostanie zwiększona do nieskończoności), aby zmaksymalizować minimalne cięcie?

9 ds.algorithms graph-theory co.combinatorics max-flow-min-cut

2

Generowanie interesujących problemów optymalizacji kombinatorycznej

Prowadzę kurs meta-heurystyki i muszę wygenerować ciekawe przykłady klasycznych problemów kombinatorycznych dla projektu semestralnego. Skupmy się na TSP. Zajmujemy się wykresami wymiarów200200200i większe. Próbowałem oczywiście wygenerować wykres z macierzą kosztów z wartościami pobranymi z losowegoU( 0 , 1 )U(0,1)U(0,1)i odkrył, że (zgodnie z oczekiwaniami) histogram kosztu ścieżki (sporządzony przez próbkowanie …

9 ds.algorithms co.combinatorics optimization tsp heuristics

1

Optymalność algorytmu Grovera z dużym prawdopodobieństwem powodzenia

Dobrze wiadomo, że złożoność kwantowej kwerendy błędu ograniczonego funkcji to . Teraz pytanie brzmi: czy chcemy, aby nasz algorytm kwantowy odniósł sukces dla każdego wejścia z prawdopodobieństwem a nie ze zwykłą . Jeśli chodzi o jakie byłyby odpowiednie górne i dolne granice?O R (x1,x2), ... ,xn)OR(x1,x2,…,xn)OR(x_1,x_2,\ldots, x_n)Θ (n--√)Θ(n)\Theta(\sqrt{n})1 - ϵ1−ϵ1-\epsilon2 …

9 cc.complexity-theory ds.algorithms quantum-computing lower-bounds

2

Problem ODD NAWET DELTA

Niech będzie wykresem. Niechbyć liczbą całkowitą. Niech będzie liczbą indukowanych przez krawędź posiadających wierzchołków i nieparzystą liczbę krawędzi. Niech będzie liczbą podgraphów indukowanych przez krawędź, mających wierzchołków i parzystą liczbę krawędzi. Niech . Problem ODD NAWET DELTA polega na obliczeniu , biorąc pod uwagę G i k .G = ( …

9 ds.algorithms graph-theory graph-algorithms counting-complexity

1

Jaki jest najgorszy przypadek losowego algorytmu triangulacji przyrostowej delauny?

Wiem, że oczekiwany najgorszy czas działania randomizowanego przyrostowego algorytmu triangulacji delauny (jak podano w geometrii obliczeniowej ) to . Istnieje ćwiczenie sugerujące, że najgorszym środowiskiem uruchomieniowym jest . Próbowałem skonstruować przykład, w którym tak naprawdę jest, ale jak dotąd nie udało się.O(nlogn)O(nlog⁡n)\mathcal O(n \log n)Ω(n2)Ω(n2)\Omega(n^2) Jeden z tych prób było …

9 ds.algorithms randomized-algorithms delaunay-triangulation worst-case

1

Czy istnieje odpowiedni algorytm do rysowania mieszanego wykresu okręgu / zależności w układzie współrzędnych?

Szukam algorytmu do rysowania mieszanego wykresu okręgów / zależności (dla aplikacji językowych). Taki wykres miałby dwa różne typy wierzchołków (tokeny, węzły) i dwa różne typy krawędzi (hierarchiczne, niehierarchiczne). Jestem nowy w teorii grafów i algorytmach w ogóle i mam nadzieję, że to pytanie nie koliduje np. Z wymaganiami dotyczącymi tej …

9 ds.algorithms graph-algorithms cg.comp-geom graph-drawing

Pytania otagowane jako ds.algorithms