Informatyka algorithms

1

Znajdź najkrótsze ścieżki na zważonym wykresie unipatycznym

Mówi się, że ukierunkowany wykres jest unipatyczny, jeśli dla dowolnych dwóch wierzchołków i na wykresie istnieje co najwyżej jedna prosta ścieżka od do .uuuvvvG=(V,E)G=(V,E)G=(V,E)uuuvvv Załóżmy, że otrzymałem wykres jednoczynnościowy taki, że każda krawędź ma dodatnią lub ujemną wagę, ale nie zawiera żadnych ujemnych cykli masy.GGG Z tego chcę znaleźć algorytm, …

12 algorithms graphs

1

Czy programowanie liniowe dopuszcza algorytm silnie wielomianowy?

Problem programowania liniowego: znajdź algorytm silnie wielomianowy, który dla danej macierzy A ∈ Rm × n i b ∈ Rm decyduje, czy istnieje x ∈ Rn z Ax ≥ b. Wiem, że Steve Smale wymienia niektóre nierozwiązane problemy matematyki. Ale czy taki liniowy problem programowania jest do tej pory nierozwiązywalny?

12 algorithms polynomial-time linear-programming

2

Dlaczego nie możemy znaleźć najkrótszych ścieżek o ujemnych wagach, po prostu dodając stałą, aby wszystkie wagi były dodatnie?

Obecnie czytam wprowadzenie do algorytmów i przyszedłem przez algorytm Johnsona, który polega na upewnieniu się, że wszystkie ścieżki są pozytywne. algo zależy od znalezienia nowej funkcji wagi (w '), która jest dodatnia dla wszystkich krawędzi i zachowuje poprawność relacji najkrótszych ścieżek. Odbywa się to poprzez obliczenie wartości h (s), h …

12 algorithms graph-theory graphs shortest-path

2

Algorytm określający, czy dwa wyrażenia regularne są równoważne

Biorąc pod uwagę dwa dowolne wyrażenia regularne, czy istnieje „wydajny” algorytm do ustalenia, czy pasują one do tego samego zestawu ciągów? Mówiąc bardziej ogólnie, czy możemy obliczyć rozmiar przecięcia dwóch zestawów dopasowań? W jakich algorytmach można to zrobić i w jakiej klasie złożoności żyją? Jeśli odrzucimy gwiazdę Kleene, czy to …

12 algorithms regular-expressions

3

Co to znaczy „Asymptotycznie bardziej wydajny”?

Co to znaczy, kiedy mówimy, że algorytm XXX jest asymptotycznie bardziej wydajny niż YYY ? XXX będzie lepszym wyborem dla wszystkich danych wejściowych. XXX będzie lepszym wyborem dla wszystkich danych wejściowych oprócz małych danych wejściowych. XXX będzie lepszym wyborem dla wszystkich danych wejściowych oprócz dużych danych wejściowych. YYY będzie lepszym …

12 algorithms algorithm-analysis terminology asymptotics

3

Wydajny algorytm do obliczania tej liczby Fibonacciego

p liczbę Fibonacciego można obliczyć w czasie liniowej stosując następujący nawrotu:nnn def fib(n): i, j = 1, 1 for k in {1...n-1}: i, j = j, i+j return i p liczbę Fibonacciego może być obliczana jako . Ma to jednak problemy z zaokrąglaniem nawet dla stosunkowo niewielkiej . Prawdopodobnie są …

11 algorithms time-complexity recurrence-relation

2

Jak znaleźć wszystkie niezrównoważone pareny w ciągu w czasie liniowym ze stałą pamięcią?

Podczas wywiadu dostałem następujący problem: Daje ciąg znaków, który zawiera pewną mieszankę parenów (nie nawiasów klamrowych ani nawiasów klamrowych - tylko pareny) z innymi znakami alfanumerycznymi, zidentyfikuj wszystkie pareny, które nie mają pasujących paren. Na przykład w ciągu „) (ab))” indeksy 0 i 5 zawierają pareny, które nie mają pasujących …

11 algorithms

3

Złożoność czasowa dodawania

Wikipedia wymienia złożoność czasową dodawania jako , gdzie jest liczbą bitów.nnnnnnn Czy to sztywna teoretyczna dolna granica? Czy to tylko złożoność obecnie najszybszego znanego algorytmu. Chcę wiedzieć, ponieważ złożoność dodawania podkreśla wszystkie inne operacje arytmetyczne i wszystkie algorytmy, które ich używają. Czy teoretycznie niemożliwe jest uzyskanie algorytmu dodawania działającego w …

11 algorithms algorithm-analysis arithmetic

2

Najbliższa para punktów między dwoma zestawami, w 2D

Mam dwa zestawy punktów w płaszczyźnie dwuwymiarowej. Chcę znaleźć najbliższą parę punktów s , t taką, że s ∈ S , t ∈ T , a odległość euklidesowa między s , t jest tak mała, jak to możliwe. Jak skutecznie można to zrobić? Czy można tego dokonać w czasie O …

11 algorithms computational-geometry

1

Indeksowanie w bazie danych wzorców - rozwiązanie Corf Optimal Rubik's Cube

Jako zabawny projekt pracowałem nad implementacją C # Richarda Korfa - Znalezienie optymalnych rozwiązań dla kostki Rubika przy użyciu baz danych wzorców. https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf Właściwie to działa, staram się tylko ulepszyć swoje rozwiązanie. Jedną rzeczą, na którą Korf patrzy w swoim artykule, jest to, jak przechowuje i indeksuje bazy danych wzorców. …

11 algorithms permutations

1

Znalezienie minimalnego pokrycia podzbioru skończonego produktu kartezjańskiego według produktów kartezjańskich

Biorąc pod uwagę podzbiór iloczynu kartezjańskiego dwóch skończonych zestawów, chciałbym znaleźć jego minimalną osłonę przez zestawy, które same są produktami kartezjańskimi.I×JI×JI \times J Na przykład, biorąc pod uwagę iloczyn między i , mogę obserwować podzbiór i spróbuj pokryć go minimalną liczbą produktów kartezjańskich.I={A,B,C}I={A,B,C}I=\{A,B,C\}J={1,2,3}J={1,2,3}J=\{1,2,3\}{(A,2),(B,3),(B,2)}{(A,2),(B,3),(B,2)}\{(A,2), (B,3), (B,2)\} to zrobić na dwa sposoby: …

11 algorithms set-cover

3

Czy jest jakiś dowód, że komputery kwantowe są bardziej wydajne niż komputery klasyczne?

Algorytm Shora jest często używany jako argument. Może rozwiązać problem faktoryzacji szybciej niż jakikolwiek znany algorytm dla klasycznych komputerów. Jednak nie mamy dowodu, że klasyczne komputery nie mogą również efektywnie uwzględniać liczb całkowitych. Czy istnieje jakiś faktyczny dowód, że komputery kwantowe mogą rozwiązać niektóre problemy szybciej niż klasyczne komputery?

11 algorithms efficiency quantum-computing

1

Jak szybko możemy obliczyć rozmiar maksymalnego dopasowania na nieważonym grafie dwustronnym?

Czy istnieje sposób na obliczenie wielkości maksymalnego dopasowania na nieważonym grafie dwustronnym bardziej efektywnie (np. Szybciej) niż obliczenie maksymalnego dopasowania? Jest to dalekie ujęcie, ale często interesującym problemem jest unikanie takich niepotrzebnych obliczeń. Motywacja Problem, który próbuję rozwiązać, to match-2, w którym oba zestawy mają różne rozmiary. Muszę ustalić, czy …

11 algorithms graphs optimization matching bipartite-matching

1

Jakie algorytmy są szybsze z komputerem kwantowym?

Jestem początkującym studentem CS i uczę się algorytmów. Słyszałem, że nawet w przypadku komputerów kwantowych ogólne algorytmy sortowania nigdy nie mogą mieć czasu lepszego niż . Wiem jednak również, że algorytmy faktoringowe byłyby znacznie szybsze. Ogólnie, jakie algorytmy stałyby się znacznie szybsze przy komputerach kwantowych?n lognnlog⁡nn\log n

11 algorithms quantum-computing

1

Generuj sieci bez skali z rozkładami stopni mocy i prawa za pomocą Barabasi-Alberta

Próbuję odtworzyć sieci syntetyczne (wykresy) opisane w niektórych artykułach. Stwierdzono, że model Barabasi-Albert został wykorzystany do stworzenia „sieci rozkładach stopni mocy, P_A (k) ∝ k ^ {- λ}PA(k)∝k−λPA(k)∝k−λP_A(k) ∝ k^{-λ} ”. PAPAP_A to rozkład prawdopodobieństwa, który zwraca prawdopodobieństwo węzła o stopniu kkk . Na przykład PA(2)PA(2)P_A(2) wskazuje prawdopodobieństwo losowego wyboru …

11 algorithms graph-theory graphs randomness sampling

Pytania otagowane jako algorithms