Teoretyczne informatyka

1

Znajdowanie ścieżek rozłącznych wierzchołków od minimum do maksimum ze wspólnym źródłem na wykresach planarnych

Biorąc pod uwagę płaski wykres nieważony i zbiór par wierzchołków ( k ≥ 2 jest stałą), znajdź k ścieżek rozłącznych wierzchołków (z wyjątkiem źródła) od s do t i tak, że długość najdłuższej ścieżki jest zminimalizowana.( s , t1) , … , ( S , tk)(s,t1),…,(s,tk)(s,t_1),\dots,(s,t_k)k ≥ 2k≥2k\ge2kkkssstjatit_i Pytanie: Czy …

10 ds.algorithms graph-algorithms

2

Pokrycie prostego wielokąta okręgami

Załóżmy, że mam prosty wielokąt i liczbę całkowitą k . Jakie są istniejące podejścia do znalezienia najmniejszego promienia r takie, że mogę pokryć S z k okręgi o promieniu R ? A może r zostanie naprawiony i chcę zminimalizować k ?SSSkkkrrrSSSkkkrrrrrrkkk

10 cg.comp-geom planar-graphs set-cover

3

Zasób / książka najnowszych osiągnięć w statystycznej teorii uczenia się

Znam dobrze teorię VC-Dimension, ale teraz patrzę na ostatnie (ostatnie 10 lat) postępy w statystycznej teorii uczenia się: (lokalne) średnie Rademachera, Lemma klasy skończonej Massarta, Liczby obejmujące, Łańcuchy, Łańcuch Dudleya Twierdzenie, Pseudodimension, Fat Shattering Dimension, Numery pakowania, Skład Rademacher i ewentualnie inne wyniki / narzędzia, których nie jestem świadomy. Czy …

10 reference-request machine-learning lg.learning books vc-dimension

1

Łączenie komórek za pomocą permutacji liniowych i kolumnowych w skończonej siatce

Chciałbym wiedzieć, czy wcześniej zbadano następujący prosty problem i czy znane jest jakieś rozwiązanie. Niech G będzie siatką skończoną (MxN), S podzbiorem komórek G („okruchy”). Mówi się, że dwie okruchy są (lokalnie) połączone, jeśli ich współrzędne różnią się co najwyżej o jeden (tj. Jeśli narysowane jako kwadraty, dzielą co najmniej …

10 ds.algorithms graph-theory graph-algorithms

1

Zwykły wykres wysokiego obwodu z „lokalnie jednolitym” całkowitym porządkiem w węzłach

Definicje Niech i niech d , r i g będą dodatnimi liczbami całkowitymi (z g > 2 r + 1 ).ϵ>0ϵ>0\epsilon > 0dddrrrgggg>2r+1g>2r+1g > 2r+1 Niech są proste, d -regular, nieukierunkowane skończonej wykres z obwodu co najmniej g .G=(V,E)G=(V,E)G = (V,E)dddggg Niech być całkowity porządek na V .≤≤\leVVV Dla każdego …

10 graph-theory co.combinatorics dc.distributed-comp

1

Twardość przybliżonej ułamkowej liczby chromatycznej na wykresach ze stopniem granicznym

Czy trudno jest apx-przybliżać ułamkową liczbę chromatyczną na wykresach ze stopniem granicznym?

10 cc.complexity-theory graph-theory approximation-hardness graph-colouring bounded-degree

3

Wnioskowanie typu dla instrukcji rozkazujących innych niż przypisanie

W poszukiwaniu artykułów naukowych na temat systemów typów dla języków imperatywnych znajduję rozwiązania tylko dla języka ze zmiennymi odnośnikami, ale bez prawdziwych struktur kontroli imperatywnej, takich jak operatory złożone, pętle lub warunki warunkowe. Nie jest więc jasne, w jaki sposób można wdrożyć imperatywny język z częściowym wnioskiem o typie, taki …

10 reference-request pl.programming-languages type-theory type-inference imperative-programming

2

Czy istnieje algorytm kwantowy ala algorytm Deutscha, który oblicza AND zamiast XOR?

Algorytm Deutscha jest dobrze znanym obliczeniem kwantowym z tylko jedną oceną . Jeśli zastąpimy z problem wydaje się być inna. Moje pytanie brzmi: czy istnieje algorytm kwantowy obliczający wartość (lub AND, jeśli wolisz) przy użyciu tylko jednej oceny . W przeciwnym razie: czy wiadomo, że taki algorytm nie istnieje?f(0)+f(1)mod2f(0)+f(1)mod2f(0) + …

10 reference-request quantum-computing

3

Redukcja trudnych problemów do modeli fizycznych

Szukam przykładów trudnych problemów (w NP lub trudniejszych) z informatyki, które można sprowadzić do modeli procesów fizycznych. Na przykład max-2-sat można zredukować do minimalizacji energii w modelu Isinga. Chciałbym znaleźć więcej przykładów tego rodzaju redukcji.

10 cc.complexity-theory reductions physics formal-modeling

1

Czy taka matryca może istnieć?

Podczas mojej pracy wpadłem na następujący problem: Usiłuję znaleźć macierz n × nn×nn \times n M dla dowolnego n > 3 o następujących właściwościach:( 0 , 1 )(0,1)(0,1)M.M.Mn > 3n>3)n > 3 Wyznacznik M.M.M jest parzysty. Dla niepustych podzbiorów ja, J⊆ { 1 , 2 , 3 }ja,jot⊆{1,2),3)}I,J\subseteq\{1,2,3\} z | …

10 graph-theory co.combinatorics linear-algebra matrices boolean-matrix

1

Doktorat; Taktyka przeglądu literatury

Nie jestem pewien, czy prawidłowy obszar, ale oto idzie. Rozpoczęcie doktoratu z zakresu zarządzania zaufaniem i reputacją w sieciach komunikacyjnych (dużo teorii grafów, analizy probabilistycznej itp.) I dużo czytania przede mną. Czy ktoś może doradzić najlepsze sposoby zarządzania czytaniem akademickim i co powinienem zwrócić uwagę na przegląd literatury / raporty …

10 soft-question advice-request research-practice

1

Znalezienie rozpinających się pająków

Czy istnieje algorytm wielomianowy do znalezienia - jeśli taki istnieje - pająka rozpinającego danego wykresu ? Pająk to drzewo z co najmniej jednym węzłem o stopniu większym niż 2: Wiem, że różne warunki stopnia na (zasadniczo wystarczająco duże stopnie węzła) gwarantują istnienie pająka rozpinającego. Ale zastanawiam się, czy istnieje algorytm …

10 ds.algorithms reference-request graph-theory graph-algorithms

2

Sortowanie punktów, aby zminimalizować minimalną odległość euklidesową między kolejnymi punktami

Biorąc pod uwagę zestaw punktów w trójwymiarowej przestrzeni kartezjańskiej, szukam algorytmu, który posortuje te punkty, tak aby zminimalizować minimalną odległość euklidesową między dwoma kolejnymi punktami. Byłoby również korzystne, gdyby algorytm miał tendencję do wyższej średniej odległości euklidesowej między kolejnymi punktami.

10 graph-algorithms cg.comp-geom optimization

3

Uwagi wstępne na temat paralelizacji, w szczególności schematów problemów i algorytmów

Szukam dostępnych w Internecie notatek z wykładów lub innych zasobów, które stanowią dobre wprowadzenie do programowania równoległego, podobnie jak równoległy analog podstawowych zajęć z informatyki. Skupiam się na następujących zagadnieniach: chociaż jestem w stanie mówić o dzieleniu i podbijaniu, chciwych algorytmach, programowaniu dynamicznym itp., Tj. Podstawowych wzorcach algorytmów sekwencyjnych (i …

10 reference-request soft-question dc.parallel-comp survey

2

Kiedy właściwość FO zabija twardość NL?

Kontekst: Rozważamy tylko digrafy. Niech CYKL będzie językiem grafów z cyklem; jest to problem kompletny dla NL. Niech HASEDGE będzie językiem grafów z co najmniej jedną krawędzią. Zatem w sposób trywialny nie jest już trudny dla NL, podczas gdy zostaje.CYCLE∪HASEDGECYCLE∪HASEDGE\text{CYCLE} \cup \text{HASEDGE}CYCLE∪HASEDGE¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯CYCLE∪HASEDGE¯\text{CYCLE} \cup \overline{\text{HASEDGE}} Rzeczywisty problem: zastanawiam się, czy język …

10 cc.complexity-theory graph-theory descriptive-complexity