Teoretyczne informatyka

3

Rozwiązanie programowania liniowego w jednym przejściu z uporządkowanymi zmiennymi

Mam rodzinę problemów z programowaniem liniowym: maksymalizuj c′xdo′xc' x z zastrzeżeniem Ax≤bZAx≤bA x\le b, x≥0x≥0x\ge0. ElementyAZAA, bbb, i cdoc są liczbami całkowitymi nieujemnymi, cdocściśle pozytywne. (xxx powinien być również integralny, ale będę się tym martwić później). W mojej aplikacji często zdarza się, że współczynniki AAA i ccc są takie, że …

9 ds.algorithms reference-request linear-programming matrices

3

Ile słów długości

EDYTOWANO, ABY DODAĆ : Na to pytanie zasadniczo udzielono odpowiedzi; zobacz ten wpis na blogu, aby uzyskać więcej informacji. Dziękujemy wszystkim, którzy opublikowali tutaj komentarze i odpowiedzi. PYTANIE ORYGINALNE Jest to, mam nadzieję, mądrzejsza i lepiej poinformowana wersja pytania, które zadałem na MathOverflow. Kiedy zadałem to pytanie, nie znałem nawet …

9 co.combinatorics

1

Systematyczne badania sumy kwadratowych wielomianów podniesione do kwadratu

Zastanawiam się, czy istnieją systematyczne badania sum kwadratowych form kwadratowych, podobnych do form kwadratowych, co praktycznie znajduje odzwierciedlenie w rozkładzie wartości własnych (co ma ogromne praktyczne implikacje). Kilka przykładów związanych ze znaczeniem pytania. Analizy głównych składników (PCA) . Biorąc pod uwagę zestaw punktówxi∈Rn,i=1..kxi∈Rn,i=1..kx_i \in \mathbb{R^n}, i=1..k znajdź zestaw osi u1u1u_1, …

9 ds.algorithms polynomials semidefinite-programming

2

Średnia liczba rocznych publikacji dla postdoców CS

Jaka jest średnia liczba publikacji (w tym materiałów konferencyjnych) rocznie dla badaczy z tytułem doktora CS w USA? Jakie są sposoby na znalezienie lub oszacowanie tej liczby?

9 soft-question advice-request research-practice career

2

Wydajne algorytmy przeszukiwania kolekcji drzew

Mam duży zestaw danych o drzewach i chciałbym je przeszukać, określając treelet (połączony podgrupa). Kwerenda powinna zwrócić wszystkie wystąpienia treeline w zbiorze danych. Czy istnieją wydajne algorytmy do tego celu? Myślałem o czymś takim jak tablice sufiksów, jednak naiwne kodowanie drzew, ponieważ łańcuchy (przez ustaloną kolejność ich węzłów) nie będą …

9 graph-algorithms ds.data-structures tree graph-isomorphism string-search

2

Punktem wyjścia dla algorytmów ignorowanych przez pamięć podręczną?

Interesuję się, gdy dowiaduję się więcej o algorytmach i strukturach danych nieobsługiwanych przez pamięć podręczną, ale jest tak wiele dokumentów, że tak naprawdę nie wiem od czego zacząć. Znalazłem oryginalną tezę Prokupa na ten temat, co wydaje się dobrym punktem wyjścia, ale jeśli istnieje proste i przystępne wprowadzenie do tematu, …

9 ds.algorithms reference-request cache-oblivious

2

Czy kilkaset kroków redukcji jest zbyt wiele, aby uzyskać normalną postać Y fac ⌜3⌝?

Ponieważ ostatnio uczę podstaw rachunku λ, wdrożyłem prosty ewaluator λ w Common Lisp. Kiedy pytam o normalną formę Y fac 3redukcji w normalnym porządku, zajmuje to 619 kroków, co wydawało się trochę za dużo. Oczywiście, za każdym razem, gdy robiłem podobne redukcje na papierze, nigdy nie korzystałem z nietypowego rachunku …

9 lo.logic lambda-calculus

1

Jaka jest rola dwukolorowego rachunku konstrukcji?

Czytam więc trochę o opracowaniu, w szczególności algorytmach opartych na dwukolorowym rachunku budowy i jestem trochę zdezorientowany. Nie rozumiem, jaki dokładnie jest cel tegododob jadodobjaCC^{bi}jest. Wydaje się być identyczny zdodododoCCz wyjątkiem tego, że istnieje rozróżnienie między niejawnymi i jawnymi argumentami funkcji. W szczególności nie widzę, jak pozwala ci pisać( i …

9 type-theory lambda-calculus type-inference dependent-type

2

Czy mogę ograniczyć liczebność zbioru, jeśli wiadomo, że testowanie członkostwa w nim jest zakończone NP?

Chciałbym ograniczyć się do liczności zbioru grafów dysków jednostkowych N.NNwierzchołki. Wiadomo, że sprawdzenie, czy wykres należy do tego zestawu, jest trudne dla NP. Czy prowadzi to do jakiejkolwiek dolnej granicy liczności, zakładając, że P≠≠\neq NP? Załóżmy na przykład, że na wszystkich wykresach występuje kolejność N.NNwierzchołki. Czy twardość NP oznaczałaby wówczas, …

9 cc.complexity-theory graph-theory

1

Euklidesowy problem z pojemną lokalizacją obiektu

W instrumentu Capacitated Lokalizacja problem (CFLP) , daje nam szereg klientów oraz zestaw potencjalnych obiektów . Każdy klient ma żądanie które musi być obsługiwane przez jedno lub więcej otwartych obiektów. Każdy obiekt ma koszt otwarcia i ma pojemność , które jest popyt, że maksymalny zakład może służyć. Koszt obsługi jednej …

9 ds.algorithms cg.comp-geom approximation-algorithms

2

Metoda postaci normalnej Chomsky'ego: implikacje wydajności parsera CYK?

Parsery wykresów mogą być implementowane w oparciu o normalną postać Chomsky'ego lub bezpośrednio w oparciu o reguły produkcji. Załóżmy na chwilę, że mamy parser wykresu CYK, który używa normalnej postaci Chomsky'ego. Binaryzacja nie jest jednoznacznie zdefiniowana. Czy wpływa to na wydajność analizy wykresu CYK. Czy można to wykorzystać do poprawy …

9 fl.formal-languages parsing

1

Stała macierzy i z wyznaczników

Niech będzie macierzą lub z wpisami . Czy ktoś może mi dostarczyć macierz , aby ? Jaki jest najmniejszy znany jawny B , taki że \ operatorname {per} (A) = \ det (B) ? Wszelkie odniesienia do tego z wyraźnymi przykładami?AZAA3×33)×3)3 \times 34×44×44 \times 4aijzajajota_{ij}BbBper(A)=det(B)za⁡(ZA)=det(b)\operatorname{per}(A) = \det(B)BbBper(A)=det(B)za⁡(ZA)=det(b)\operatorname{per}(A) = \det(B) Niektóre …

9 cc.complexity-theory algebraic-complexity permanent

2

Najkrótsze ścieżki uniemożliwiające każdą krawędź

Byłbym wdzięczny za wszelkie wskazówki lub warunki, które mogłyby doprowadzić mnie do właściwego kierunku. Mamy ukierunkowany wykres G = ( V, E)G=(V,E)G=(V,E) i długości lI jlijl_{ij} dla każdej krawędzi I jijijktóre można uznać za pozytywne. Istnieje specjalny węzeł początkowysss i węzeł końcowy ttt. Dla każdej krawędzi I jijij, chcielibyśmy obliczyć …

9 ds.algorithms reference-request graph-algorithms

1

Osadzanie wykresu jako zbioru czworościanów rozłącznych wewnętrznie

Zdefiniuj siatkę w 3D jako połączoną kolekcję czworościanów z rozłącznymi wnętrzami (więc czworościany mają tylko k-face, k ≤ 2k≤2)k \le 2). Czy na podstawie dowolnego wykresu istnieje skuteczna procedura sprawdzania, czy można go osadzić jako siatkę? Osadzanie polega na odwzorowaniu wierzchołków wykresu na punkty w R3)R3)R^3 a krawędzie do linii …

9 ds.algorithms graph-theory

1

Jaka jest właściwa rola weryfikacji w próbkowaniu kwantowym, symulacji i testowaniu metodą rozszerzonego kościoła-Turinga (ECT)?

Ponieważ nie udzielono odpowiedzi, ustawiono flagę z prośbą o przekształcenie tego pytania w wiki społeczności. Komentarze Aarona Sterlinga, Sasho Nikolova i Vora zostały zsyntetyzowane do następującej rozdzielczości, która jest otwarta na dyskusję wiki społeczności: Rozwiązane: W odniesieniu do klasycznych algorytmów, które generują liczby, próbki lub trajektorie symulacji, ścisła logika matematyczna …

9 quantum-computing program-verification sample-complexity