Teoretyczne informatyka

2

Najlepszy sposób na określenie minimalnego wymiaru konstrukcji, biorąc pod uwagę tylko odległości między punktami

Zetknąłem się z tym problemem w dziedzinie fizyki dość dalekiej od informatyki, ale wydaje się, że jest to pytanie, które było badane w CS, więc pomyślałem, że spróbuję szczęścia, zadając to tutaj. Wyobraź sobie, że otrzymałeś zestaw punktów oraz listę niektórych odległości między punktami d i j . Jaki jest …

13 ds.algorithms cg.comp-geom

1

Elementarne granice parametru w ciągliwości parametrów stałych?

W definicji (silnej) ciągliwości parametrów stałych ustalony czas jest wyrażeniem postaci gdzie instancja wejściowa to ( x , k ) z parametrem k , p jest wielomianem, a f jest funkcją obliczalną .f(k).p(|x|),f(k).p(|x|),f(k).p(|x|),(x,k)(x,k)(x,k)kkkpppfff Możliwe jest zastąpienie wymogu obliczeniowego dla innymi klasami funkcji, o ile pojęcie redukcji jest podobnie ograniczone. (Na …

13 cc.complexity-theory reference-request fixed-parameter-tractable

1

Przypadki prawie liniowych układów liniowych rozwiązanych w czasie

Niech kwadratowa rzeczywista macierz A i dwa wektory x i b o długości n , takie, że A x = b . Rozwiązanie x poprzez standardową eliminację Gaussa daje łączną złożoność prawie O ( n 3 ) . Są jednak przypadki, w których rozwiązywanie (lub ϵ - rozwiązywanie w przybliżeniu) …

13 cc.complexity-theory linear-algebra matrices

2

Zdecentralizowany algorytm do określania wpływowych węzłów w sieciach społecznościowych

W tym artykule Kempe-Kleinberg-Tardos autorzy proponują zachłanne algorytmy oparte na funkcjach submodularnych w celu określenia najbardziej wpływowych węzłów na wykresie, z zastosowaniem do sieci społecznościowych.kkk Zasadniczo algorytm wygląda następująco: S=empty setS=empty setS = {\rm empty~set} wybierz węzeł o najwyższym indywidualnym wpływie, nazwij go ; S = S ∪ v 1v1v1v_1S=S∪v1S=S∪v1S …

13 ds.algorithms graph-theory dc.distributed-comp social-sciences heuristics

1

Algorytmy równoległe dla osiągalności w ukierunkowanych grafach płaskich

Chong, Han i Lam pokazali, że nieukierunkowaną łączność st można rozwiązać na EREW PRAM w czasie pomocą procesorów O ( m + n ) .O(logn)O(logn)O({\log}n)O(m+n)O(m+n)O(m+n) Jaki jest najbardziej znany algorytm równoległy dla łączności st w ukierunkowanych grafach płaskich? Podaj czas działania, deterministyczny / losowy algorytm i zastosowany model PRAM (zakładając, …

13 ds.algorithms graph-theory dc.parallel-comp

1

Problem NP-zupełny dla geometrii euklidesowej, ale w P dla geometrii innej niż euklidesowa?

Czy są jakieś problemy, które są NP-całkowite przy stosowaniu geometrii euklidesowej, ale są dobrze zdefiniowane i możliwe do rozwiązania w czasie wielomianowym dla niektórych geometrii nie-euklidesowych?

13 reference-request cg.comp-geom

1

Na podstawie wykresu zdecyduj, czy jego łączność brzegowa wynosi co najmniej n / 2, czy nie

Rozdział 1 książki Metoda probabilistyczna autorstwa Alona i Spencera wymienia następujący problem: Biorąc pod uwagę wykres , zdecyduj, czy jego łączność brzegowa wynosi co najmniej czy nie.GGGn/2n/2n/2 Autor wspomina o istnieniu przez Matula algorytmu i ulepsza go do .O(n3)O(n3)O(n^3)O(n8/3logn)O(n8/3log⁡n)O(n^{8/3}\log n) Moje pytanie brzmi: jaki jest najbardziej znany czas wykonywania tego …

13 ds.algorithms open-problem graph-algorithms

3

Skuteczne zastosowanie metod rozgałęzionych i związanych z problemami trudnymi dla NP

Rozgałęzienie i powiązanie to skuteczna heurystyka dla problemów wyszukiwania, a Wikipedia wymienia wiele trudnych problemów, w których zastosowano rozgałęzienie i powiązanie. Jednak nie udało mi się znaleźć referencji sugerujących, że jest to więcej niż „jedna metoda” rozwiązania tych problemów. Anegdotycznie słyszałem, że jedne z najlepszych heurystyki dla programowania SAT i …

13 ds.algorithms reference-request optimization heuristics

1

Parzystość-L vs. NL

Parzystość-L, znana również jako , jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko liczbę parzystą lub nieparzystą liczby ścieżek „akceptacji”. Ostatnie powiązane pytanie zadał Niel de Beaudrap.⊕⊕\oplus Moje pytanie jest następujące: Czy wiemy, czy NL ⊕ L? Czy te dwie klasy są uważane za nieporównywalne?⊆⊆\subseteq ⊕⊕\oplus

13 cc.complexity-theory counting-complexity

1

Czy liczenie maksymalnych klików na wykresie nieporównywalności # P jest kompletne?

To pytanie jest motywowane pytaniem MathOverflow Peng Zhanga . Valiant wykazał, że zliczanie maksymalnych klików na wykresie ogólnym jest zakończone metodą # P, ale co jeśli ograniczymy się do wykresów nieporównywalności (tzn. Chcemy policzyć maksymalne antichains w skończonym zestawie)? To pytanie wydaje się na tyle naturalne, że podejrzewam, że zostało …

13 cc.complexity-theory counting-complexity partial-order clique

5

Dlaczego kodowanie Huffmana eliminuje entropię, której nie ma Lempel-Ziv?

Popularny algorytm DEFLATE wykorzystuje kodowanie Huffmana na Lempel-Ziv. Ogólnie rzecz biorąc, jeśli mamy losowe źródło danych (= 1 bit entropii / bit), żadne kodowanie, w tym Huffman, prawdopodobnie nie skompresuje go średnio. Gdyby Lempel-Ziv był „idealny” (do którego zbliża się większość klas źródeł, ponieważ długość dochodzi do nieskończoności), kodowanie postów …

13 ds.algorithms it.information-theory coding-theory encoding

3

Wdrożony kod do obliczania szerokości ścieżki (= numer wyszukiwania węzła, numer separacji wierzchołków, grubość przedziału)

Szukam implementacji algorytmu do obliczania szerokości ścieżki wykresu. Dobrze wiadomo, że obliczenie szerokości ścieżki jest równoważne z obliczeniem numeru wyszukiwania węzła, numeru separacji wierzchołków lub grubości przedziału wykresu. Algorytm nie musi być bardzo szybki; Chcę uruchomić go na wykresach o maksymalnie 20 wierzchołkach. Wymagam od algorytmu dokładnego obliczenia szerokości ścieżki, …

13 ds.algorithms reference-request graph-algorithms implementation

2

Jakie są prawa równań dla typów zerowych?

Oświadczenie : chociaż dbam o teorię typów, nie uważam się za eksperta w dziedzinie teorii typów. W prostym typie rachunku lambda typ zerowy nie ma konstruktorów i unikalnego eliminatora: Γ⊢M:0Γ⊢initial(M):AΓ⊢M:0Γ⊢initial(M):A\frac{\Gamma \vdash M \colon 0}{\Gamma \vdash initial (M) \colon A} Z denotacyjnego punktu widzenia równanie initial(M1)=initial(M2)initial(M1)=initial(M2)initial (M_1) = initial(M_2) jest oczywiste …

13 pl.programming-languages type-theory lambda-calculus semantics

1

Żądanie referencyjne: dowód bez teorii liczb, że maksymalne grupy stabilizatorów określają stany unikalne

Kontekst. Piszę na tematy takie jak twierdzenia Gottesman-Knill korzystając Pauli grupy stabilizator, ale w przypadku d -wymiarowej qudits - gdzie d może mieć więcej niż jeden czynnik pierwszy. (Podkreślam to, ponieważ ogromna większość literatury na temat formalizmu stabilizatora w „wyższych wymiarach” dotyczy przypadków d pierwszej lub d pierwszej mocy i …

13 reference-request quantum-computing

2

Odniesienie do optymalnego algorytmu faktoringu Levina?

W „ Poradzie dla początkującego studenta ” Manuela Bluma : LEONID LEVIN wierzy, jak to robię, niezależnie od odpowiedzi na P = NP? problem, to nie będzie tak, jak myślisz, że powinno być. Podał też wspaniałe przykłady. Po pierwsze, podał FACTORING ALGORITHM, który jest optymalnie optymalny, aż do stałej multiplikatywnej. …

13 ds.algorithms reference-request factoring