Pytania otagowane jako ds.algorithms

Pytania dotyczące dobrze zdefiniowanych instrukcji wykonania zadania oraz odpowiedniej analizy pod względem czasu / pamięci / itp.

4
Definicja wykładnika mnożenia macierzy
Potocznie definicja wykładnika mnożenia macierzy jest najmniejszą wartością, dla której znany jest algorytm mnożenia macierzy . Nie jest to dopuszczalne, formalnej definicji matematycznej tak Chyba określenie techniczne jest czymś w infimum na wszystkich tak, że istnieje algorytm mnożenia macierzy w .n ω t n tωω\omeganωnωn^{\omega}tttntntn^t W tym przypadku nie możemy …
1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
3
Wyprzedaż Boba (zmiana kolejności par z ograniczeniami w celu zminimalizowania sumy produktów)
Jakiś czas temu zadałem to pytanie na temat Przepełnienia stosu: Problem: sprzedaż Boba . Ktoś zasugerował także opublikowanie pytania tutaj. Ktoś już zadał tutaj pytanie związane z tym problemem - minimalna waga lasów danej liczności - ale o ile rozumiem, nie pomaga mi to z moim problemem. Warto również przyjrzeć …
2
Minimalna liczba transpozycji do sortowania listy
Próbując opracować własny algorytm sortowania, szukam optymalnego testu porównawczego, z którym mogę go porównać. W przypadku nieposortowanego uporządkowania elementów A i posortowanego uporządkowania B , jaki jest skuteczny sposób obliczenia optymalnej liczby transpozycji, które można uzyskać od A do B ? Transpozycja jest definiowana jako zmiana pozycji 2 elementów na …
1
Projektowanie i złożoność algorytmów - jak myśleć w ten „sposób”?
Moje pytanie jest ogólne: jak zacząć myśleć o projektowaniu i złożoności algorytmów? Mam zamiar podjąć kurs magisterski z projektowania algorytmów. Zapisałem się na to wcześniej, ale porzuciłem go później, ponieważ nie mogłem nadążyć. Muszę wziąć ten kurs jako wymóg. Czy istnieje „sztuczka” do myślenia w ten sposób? Wiem, że jest …
3
Super Mario płynie w NP?
Klasycznym rozszerzeniem problemu maksymalnego przepływu jest problem „maksymalnego przepływu w czasie”: otrzymujesz wykrój, którego dwa węzły są rozróżniane jako źródło i zlew, przy czym każdy łuk ma dwa parametry, wydajność na czas i opóźnienie. Jesteś również biorąc pod uwagę horyzont czasowy . Celem jest, aby obliczyć przepływ w czasie której …
1
Rozkłady grafów do łączenia „lokalnych” funkcji etykietowania wierzchołków
∑x∏i j ∈ Efa( xja, xjot)∑x∏jajot∈mifa(xja,xjot)\sum_x \prod_{ij \in E} f(x_i,x_j)maxx∏i j ∈ Efa( xja, xjot)maxx∏jajot∈mifa(xja,xjot)\max_x \prod_{ij \in E} f(x_i,x_j) Gdzie Max lub suma przejmuje wszystkie labelings z , produkt wprowadza się na wszystkie krawędzie dla grafu G = \ {V, E \} i f jest dowolną funkcją. Ilość ta jest …
1
Rzadka transformacja Walsha-Hadamarda
Walsh-Hadamard'a transformacji (BLK) jest uogólnieniem transformaty Fouriera i jest prostopadła do przetwarzania na wektorze rzeczywistych lub liczb zespolonych o wymiarze . Transformacja jest popularna w obliczeniach kwantowych, ale ostatnio badano ją jako rodzaj warunku wstępnego losowych rzutów wektorów wielowymiarowych do wykorzystania w dowodzie lematu Johnsona-Lindenstraussa. Jego główną cechą jest to, …
6
Złożoność algorytmu tasowania Fishera-Yatesa
To pytanie dotyczy algorytmu Fishera-Yatesa służącego do zwracania losowego losowania danej tablicy. The Wikipedii mówi, że jego złożoność wynosi O (n), ale myślę, że jest to O (n log n). W każdej iteracji i losowa liczba całkowita jest wybierana między 1 a i. Po prostu zapisywanie liczby całkowitej w pamięci …
3
Izomorfizm podsgrafu z drzewem
Jeśli mamy duży (skierowany) wykres i mniejsze ukorzenione drzewo H , jaka jest najbardziej znana złożoność znajdowania podgraphów G izomorficznych względem H ? Zdaję sobie sprawę z wyników dla izomorfizmu poddrzewa, w którym zarówno G, jak i H są drzewami, a także gdzie G jest płaski lub ma ograniczoną szerokość …
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 …
3
Sprawdzenie wzorów dwa kwantyfikatorów (
Solwery SAT dają potężny sposób na sprawdzenie poprawności formuły logicznej za pomocą jednego kwantyfikatora. Na przykład, aby sprawdzić poprawność , możemy użyć solwera SAT, aby ustalić, czy φ ( x ) jest zadowalające. Aby sprawdzić ważność ∀ x . φ ( x ) , możemy użyć solwera SAT do ustalenia, …
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.