Pytania otagowane jako matrices

2
Jaki jest najszybszy algorytm do obliczania rangi macierzy prostokątnej?
Biorąc pod uwagę macierz m×nm×nm \times n (przy założeniu, że m≥nm≥nm \ge n ), jaki jest najszybszy algorytm obliczający swoją pozycję i podstawę kolumn? Wiem, że można to rozwiązać za pomocą liniowego przecięcia macierzy, co implikuje algorytm deterministyczny czasowy i algorytm randomizowany czasowo O ( m n ω - 1 …
4
Znalezienie najrzadszego rozwiązania układu równań liniowych
Jak trudno jest znaleźć najrzadsze rozwiązanie układu równań liniowych? Bardziej formalnie, rozważ następujący problem decyzyjny: Instancja: układ równań liniowych o współczynnikach całkowitych i liczbie ccc . Pytanie: Czy istnieje rozwiązanie dla systemu z co najmniej ccc zmiennymi przypisanymi do zera? Próbuję również ustalić, na czym polega zależność od ccc . …
1
Jaka jest złożoność sprawdzenia, czy macierz można diagonalizować?
Biorąc pod uwagę macierzy A z racjonalnym pozycji. Jaką złożoność sprawdzenia A można diagonalizować?n×nn×nn\times nAAAAAA Podejrzewam, że można to zrobić w P, ale nie znam żadnego odniesienia. Bardziej interesujące jest jednak pytanie, czy istnieje jakaś lepsza klasa złożoności, aby uchwycić ten problem? Wszelkie wskazówki / komentarze są mile widziane! Dzięki.
2
Złożoność testowania członkostwa dla skończonych grup abelowych
Rozważ następujący problem testowania członkostwa w podgrupie abelian . Wejścia: Skończona grupa abelowa G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m} o dowolnie dużych didid_i . Wytwarzające osadzone {h1,…,hn}{h1,…,hn}\lbrace h_1,\ldots,h_n\rbrace podgrupy H⊂GH⊂GH\subset G . Element b∈Gb∈Gb\in G . Wyjście: „tak”, jeżeli b∈Hb∈Hb\in H i „nie” w innym miejscu. Pytanie: Czy ten problem można skutecznie rozwiązać na klasycznym …
1
Konstruowanie wektorów w pozycji ogólnej
Niech prawdziwa macierz k×nk×nk\times n ( k≤nk≤nk\le n ) AA{\bf A} z tą właściwością, że dowolny zbiór kkk kolumn ma pełną rangę. P: istnieje efektywny sposób deterministyczny znaleźć wektor tak że zmodyfikowanym matrycy ' = [aa{\bf a}A′=[Aa]A′=[Aa]{\bf A}' = [{\bf A}\;{\bf a}] zachowuje tę samą właściwość coAA{\bf A} : dowolnekkk …
2
Algorytm mnożenia wektora macierzy przy użyciu minimalnej liczby dodatków
Rozważ następujący problem: Biorąc pod uwagę macierz , chcemy zoptymalizować liczbę dodatków w algorytmie mnożenia do obliczania .MMMv↦Mvv↦Mvv \mapsto Mv Uważam ten problem za interesujący ze względu na jego związek ze złożonością mnożenia macierzy (ten problem jest ograniczoną wersją mnożenia macierzy). Co wiadomo o tym problemie? Czy są jakieś interesujące …
2
Dokładna formuła dla liczby drzew rozpinających prostokąta
Ten blog mówi o generowaniu „krętych małych labiryntów” za pomocą komputera i ich liczeniu. Wyliczenia można dokonać za pomocą algorytmu Wilsona, aby uzyskać UST , ale nie pamiętam wzoru na ich liczbę. http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike Zasadniczo Twierdzenie o Drzewie Matrycowym stwierdza, że ​​liczba drzew spinających na wykresie jest równa wyznacznikowi macierzy Laplaciana …
1
Jaka jest największa różnica między rangą a przybliżoną rangą?
Wiemy, że log stopnia macierzy 0-1 jest dolną granicą deterministycznej złożoności komunikacji, a log przybliżonej rangi jest dolną granicą losowości złożoności komunikacji. Największa różnica między deterministyczną złożonością komunikacji a losową złożonością komunikacji ma charakter wykładniczy. A co z różnicą między rangą a przybliżoną rangą macierzy boolowskiej?
1
Czy możemy uzyskać posortowaną listę z posortowanej macierzy w
Jestem zmieszany. Chcę udowodnić, że problem sortowania macierzy przez , tj. Wiersze i kolumny są w porządku rosnącym, to . Kontynuuję, zakładając, że można to zrobić szybciej niż i próbuję złamać dolną granicę Dla porównań potrzebnych do posortowania m elementów. Mam dwie sprzeczne odpowiedzi:nnnnnnΩ (n2)logn )Ω(n2)log⁡n)\Omega(n^2\log n)n2)lognn2)log⁡nn^2\log nlog( m ! …
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 …
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.