Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

2
podobne matryce
Biorąc pod uwagę dwa macierzy i , problem decydowania o istnieniu macierzy permutacji takiej, że jest równoważny (Izomorfizm Grafów). Ale jeśli rozluźnimy aby był tylko odwracalną matrycą, to jaka jest złożoność? Czy istnieją jakieś inne ograniczenia dotyczące odwracalnej macierzy , oprócz tego, że są permutacją, które wiążą ten problem z …
1
Jak obliczyć moc macierzy kwadratowych?
Załóżmy, że otrzymujemy macierz i pozwólmy . Jak szybko możemy obliczyć moc A ^ m tej macierzy? m ∈ N 0 A mA ∈ RN.× N.ZA∈RN.×N.A \in \mathbb R^{N\times N}m ∈ N0m∈N.0m \in \mathbb N_0ZAmZAmA^m Kolejną najlepszą rzeczą w porównaniu do obliczania produktów jest zastosowanie szybkiego potęgowania, które wymaga produktów …
4
Sparametryzowany algorytm znajdowania biklików
Biorąc pod uwagę nieukierowany wykres nnn wierzchołka, jaki jest najbardziej znany środowisko uruchomieniowe dla znalezienia podrozdziału, który jest dwukolorową k × kk×kk\times k ? Czy istnieją szybsze algorytmy parametryzowane niż algorytm polegający na „zgadywaniu” jednej strony biclique i sprawdzanie, czy występuje co najmniej k innych wierzchołków przypadających na wszystkie z …
2
Reprezentowanie wykresów niepłaskich z nakładającymi się okręgami
Wiemy, że możemy przedstawić dowolny wykres płaski za pomocą zestawu kół w płaszczyźnie, znanego jako wykres monety . Każde koło reprezentuje wierzchołek, a pomiędzy dwoma wierzchołkami znajduje się krawędź wtedy i tylko wtedy, gdy koła „pocałują się” na swojej granicy. Załóżmy, że zamiast tego zezwalamy na nakładanie się kół i …
2
Charakterystyka problemów, dla których istnieją algorytmy czasu podliniowego
Zastanawiałem się, czy problemy, dla których istnieją algorytmy czasu podliniowego (w wielkości wejściowej), można scharakteryzować jako posiadające określone właściwości. Obejmuje to czas podliniowy (np. Testowanie właściwości, alternatywne pojęcie przybliżenia problemów decyzyjnych), przestrzeń podliniowa (np. Algorytmy szkicowania / przesyłania strumieniowego, w których maszyna Turinga ma taśmę tylko do odczytu, podliniową przestrzeń …
1
Twardość NP problemu podziału grafu?
Jestem zainteresowany tym problemem: Biorąc pod uwagę undirected wykres , Czy istnieje podział na wykresach i takie, że i są izomorficzne?G(E,V)G(E,V)G(E, V)GGGG1(E1,V1)G1(E1,V1)G_1(E_1, V_1)G2(E2,V2)G2(E2,V2)G_2(E_2, V_2)G1G1G_1G2G2G_2 Tutaj jest podzielony na dwa rozłączne zestawy i . Zestawy i niekoniecznie są rozłączne. i .EEEE1E1E_1E2E2E_2V1V1V_1V2V2V_2E1∪E2=EE1∪E2=EE1∪E2=EV1∪V2=VV1∪V2=VV1∪V2=V Ten problem jest co najmniej tak trudny jak problem z …
1
Gramatyka kontekstowa dla SAT?
Według klasycznego wyniku Kurody, klasa złożoności NSPACE [ ]nnn (znana również jako NLIN-SPACE) jest właśnie klasą CSL języków kontekstowych . Problem satysfakcji SAT występuje w NSPACE [ ], ponieważ domysły o liniowym rozmiarze dla rozwiązania można sprawdzić z co najwyżej liniowym obciążeniem dla księgowości. Oznacza to, że SAT musi mieć …
6
Kiedy mówi się, że dwa algorytmy są „podobne”?
Nie pracuję w teorii, ale moja praca wymaga od czasu do czasu czytania (i rozumienia) prac teoretycznych. Kiedy zrozumiem (zestaw) wyników, omawiam je z ludźmi, z którymi pracuję, z których większość również nie działa w teorii. Podczas jednej z takich dyskusji pojawiło się następujące pytanie: Kiedy mówi się, że dwa …
2
Zwroty permutacyjne z analizą LR
Wyrażenie permutacji jest rozszerzeniem standardu (E) BNF wolne definicji kontekstu gramatyczne: frazę permutacji zawiera n produkcji (lub równoważnie nieterminale) A 1 przez A n . W miejscu wyrażenia permutacyjnego chcielibyśmy zobaczyć każdą z tych produkcji dokładnie raz, ale nie jesteśmy zainteresowani kolejnością tych nieterminali.{ A1, … , An}{ZA1,…,ZAn}\{ A_1, \dots, …
2
Znajdowanie k najkrótszych ścieżek za pomocą algorytmu Eppsteina
Próbuję dowiedzieć się, jak działa wykres ścieżki według algorytmu Eppsteina w tym artykule i jak mogę zrekonstruować najkrótszych ścieżek od do z odpowiednią konstrukcją stosu .k s t H ( G )P(G)P(G)P(G)kkkssstttH(G)H(G)H(G) Jak dotąd: out(v)out(v)out(v) zawiera wszystkie krawędzie opuszczające wierzchołek na wykresie , które nie są częścią najkrótszej ścieżce . …
1
Zmniejszanie rozkładu drzewa o minimalnej szerokości w czasie wielomianowym
Jak dobrze wiadomo, rozkład drzewa wykresu składa się z drzewa ze skojarzoną torbą dla każdego wierzchołka , który spełnia następujące warunki:T T v ⊆ V ( G ) v ∈GGGTTTTv⊆V(G)Tv⊆V(G)T_v \subseteq V(G)v∈V(T)v∈V(T)v \in V(T) Każdy wierzchołek występuje w jakimś workiem .TGGGTTT Dla każdej krawędzi znajduje się worek zawierający oba punkty …
2
Liczba bramek binarnych potrzebnych do obliczenia AND i OR n bitów wejściowych jednocześnie
Jaka jest minimalna liczba bramek binarnych potrzebnych do jednoczesnego obliczenia AND i OR bitów wejściowych? Trywialna górna granica wynosi 2 n - 2 . Uważam, że jest to optymalne, ale jak to udowodnić? Nie działa tutaj standardowa technika eliminacji bramki, ponieważ poprzez przypisanie stałej do dowolnej zmiennej wejściowej trywializuje jedno …
3
Studia podyplomowe z teorii CS a matematyki stosowanej
Biorąc pod uwagę, że większość amerykańskich uniwersytetów przyjmuje wnioski tylko w jednej dziedzinie, staram się dowiedzieć, jakie są zalety / wady stosowania programu teorii CS w porównaniu z programem matematyki stosowanej, biorąc pod uwagę, że interesuje go gdzieś w obu wydziałach. Mówiąc ściślej, obszarami zainteresowań malejącego porządku są: 1. Kombinatoryka …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.