Teoretyczne informatyka reference-request

2

Czy są jakieś najnowsze książki na temat algorytmów online? Znam tylko dwie książki na ten temat. Obliczenia online i analiza konkurencji Allana Borodina i Ran El-Yaniv: Jest to klasyczna, ale stara książka i nie zawiera wielu najnowszych osiągnięć w tej dziedzinie. Projektowanie konkurencyjnych algorytmów online za pomocą podejścia pierwotnego podwójnego …

13 reference-request big-list online-algorithms

1

Czy jest jakaś praca łącząca uczenie maszynowe z bardziej egzotycznymi formami teorii złożoności?

Wydaje mi się, że eksperci od uczenia maszynowego / eksploracji danych znają P i NP, ale rzadko mówią o niektórych bardziej subtelnych klasach złożoności (np. NC, BPP lub IP) i ich implikacjach dla skutecznego analizowania danych. Czy jest jakaś ankieta na temat tej pracy?

13 cc.complexity-theory reference-request machine-learning

1

Najmniejszy znany wzór na wyznacznik

Najmniejsza znana formuła dla wyznacznika ma rozmiar zgodnie z folklorem (lub Ran Raz w swoim artykule Wieloliniowe formuły na stałe i determinant mają rozmiar wielobiegowy ).nO (logn )nO(log⁡n)n^{\mathcal O(\log n)} Czy masz na to jakieś odniesienia? W szczególności, czym jest ta formuła?

13 cc.complexity-theory reference-request algebraic-complexity determinant

4

Alan Turing Dokumentalne

Aby uczcić 100. urodziny Alana Turinga, chcę obejrzeć film dokumentalny o jego życiu. Istnieje jednak kilka dokumentów do wyboru. Który dokument o Alanie Turingu jest twoim ulubionym? Podaj tylko jeden dokument na odpowiedź.

13 reference-request soft-question big-list ho.history-overview

1

Osadzanie wykresów, które maksymalizuje minimalny kąt

Biorąc pod uwagę wykres płaski, można go osadzić w liniowym czasie przechodzącym swobodnie w siatkę . Interesuje mnie, czy znane są efektywne algorytmy linii prostej osadzającej płaski wykres przecinający się swobodnie w siatce n c × n c , dla jakiegoś małego c , tak, że minimalny kąt między dwiema …

13 reference-request graph-theory graph-drawing

1

Złożoność dominującego problemu w określonych podklasach wykresów akordowych

Interesuje mnie złożoność problemu dominującego zestawu (DSP) w niektórych określonych klasach grafów, które są podklasami grafów akordowych . Wykres jest nieukierowanym wykresem ścieżki, jeśli jest to wykres przecięcia wierzchołków rodziny ścieżek w jakimś niekierowanym drzewie. Niech UP będzie klasą niekierowanych grafów ścieżek. Wykres jest grafem EPT, jeśli jest to wykres …

13 reference-request graph-theory graph-algorithms np-hardness

2

Zastosowanie liczb Ramseya

Definicja liczb Ramseya jest następująca: Niech jest dodatnią liczbą taką, że każdy wykres zamówienia na przynajmniej R ( , b ) obejmuje albo klika w ciągu wierzchołków lub zestaw się na stałym b wierzchołków.R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)aaabbb Pracuję nad jakimś rozszerzeniem Ramsey Numbers. Chociaż badanie ma pewne teoretyczne zainteresowania, ważne byłoby poznanie motywacji …

13 reference-request co.combinatorics ramsey-theory

4

Modelowanie obiektów (OOP) w teorii typów zależnych

Interesuje mnie modelowanie obiektów, od programowania obiektowego, w teorii typów zależnych. Jako możliwą aplikację chciałbym mieć model, w którym mogę opisać różne cechy imperatywnych języków programowania. Znalazłem tylko jeden artykuł na temat modelowania obiektów w teorii typów zależnych, a mianowicie : Programowanie obiektowe w teorii typów zależnych A. Setzer (2006) …

13 reference-request pl.programming-languages type-theory coq dependent-type

1

Algorytmy redukcji SERF i algorytmy podwykładnicze

Mam pytanie dotyczące redukowalności SERF impagliazzo, Paturi i Zane'a oraz algorytmów podwykładniczych. Definicja SERF-redukowalności daje następujące: Jeśli jest redukowalne przez SERF do P 2 i istnieje algorytm O ( 2 ε n ) dla P 2 dla każdego ε > 0 , wówczas istnieje algorytm O ( 2 ε n …

13 cc.complexity-theory reference-request

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

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

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

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

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

Pytania otagowane jako reference-request