Teoretyczne informatyka ds.algorithms

2

Punktem wyjścia dla algorytmów ignorowanych przez pamięć podręczną?

Interesuję się, gdy dowiaduję się więcej o algorytmach i strukturach danych nieobsługiwanych przez pamięć podręczną, ale jest tak wiele dokumentów, że tak naprawdę nie wiem od czego zacząć. Znalazłem oryginalną tezę Prokupa na ten temat, co wydaje się dobrym punktem wyjścia, ale jeśli istnieje proste i przystępne wprowadzenie do tematu, …

9 ds.algorithms reference-request cache-oblivious

1

Euklidesowy problem z pojemną lokalizacją obiektu

W instrumentu Capacitated Lokalizacja problem (CFLP) , daje nam szereg klientów oraz zestaw potencjalnych obiektów . Każdy klient ma żądanie które musi być obsługiwane przez jedno lub więcej otwartych obiektów. Każdy obiekt ma koszt otwarcia i ma pojemność , które jest popyt, że maksymalny zakład może służyć. Koszt obsługi jednej …

9 ds.algorithms cg.comp-geom approximation-algorithms

2

Najkrótsze ścieżki uniemożliwiające każdą krawędź

Byłbym wdzięczny za wszelkie wskazówki lub warunki, które mogłyby doprowadzić mnie do właściwego kierunku. Mamy ukierunkowany wykres G = ( V, E)G=(V,E)G=(V,E) i długości lI jlijl_{ij} dla każdej krawędzi I jijijktóre można uznać za pozytywne. Istnieje specjalny węzeł początkowysss i węzeł końcowy ttt. Dla każdej krawędzi I jijij, chcielibyśmy obliczyć …

9 ds.algorithms reference-request graph-algorithms

1

Osadzanie wykresu jako zbioru czworościanów rozłącznych wewnętrznie

Zdefiniuj siatkę w 3D jako połączoną kolekcję czworościanów z rozłącznymi wnętrzami (więc czworościany mają tylko k-face, k ≤ 2k≤2)k \le 2). Czy na podstawie dowolnego wykresu istnieje skuteczna procedura sprawdzania, czy można go osadzić jako siatkę? Osadzanie polega na odwzorowaniu wierzchołków wykresu na punkty w R3)R3)R^3 a krawędzie do linii …

9 ds.algorithms graph-theory

1

Heurystyka dla optymalizacji

Ponieważ jest piątek, czas na pytanie CW. Szukam heurystyki, która ma szerokie zastosowanie w problemach związanych z optymalizacją. Aby ograniczyć zakres do bardziej „przyjaznej teorii” heurystyki, oto zasady (niektóre arbitralne, niektóre nie) Powinna to być dobrze zdefiniowana metoda bez wielu parametrów i z konkretnym czasem pracy (może na iterację) Powinny …

9 ds.algorithms reference-request optimization heuristics

2

Czy istnieje struktura danych umożliwiająca szybkie manipulowanie listami i zapytania dotyczące zamówień?

Mamy zestaw, LLL, list elementów z zestawu N= { 1 , 2 , 3 , . . . ,n}N={1,2,3,...,n}N = \{ 1, 2, 3, ..., n \}. Każdy element zNNN pojawia się na jednej liście w LLL. Szukam struktury danych, która może wykonać następujące aktualizacje: c o n c at(x,y)concat(x,y)concat(x, …

9 ds.algorithms graph-algorithms ds.data-structures

1

Decyzja, czy ciąg znaków zastępczych jest całkowicie dopasowany do innego ciągu znaków zastępczych w zestawie

Oto problem, który dręczy mnie od dłuższego czasu. Powiedzmy, że łańcuch jest sekwencją 1 i 0, a łańcuch wieloznaczny to sekwencja 1, 0 i? S. Wszystkie ciągi znaków i symbole wieloznaczne mają tę samą długość. Są to standardowe symbole wieloznaczne UNIX; 10 ?? 1 pasuje do 10011, 10111 itd. - …

9 ds.algorithms ds.data-structures approximation-algorithms string-matching string-search

1

Potężne algorytmy, które są zbyt trudne do wdrożenia - jak się upewnić, że mają rację?

Odnoszę się tutaj do pytania: potężne algorytmy zbyt złożone, aby je zaimplementować . Jeśli algorytm jest potężny, ale zbyt skomplikowany, aby go wdrożyć, skąd możesz mieć pewność, że algorytm jest poprawny? Bez implementacji nie będzie można przetestować algorytmu w scenariuszu ze świata rzeczywistego, a tak złożony algorytm może zawierać błędy, …

9 ds.algorithms implementation

3

Algorytmy triangulacji wielokąta

Miałem trudności ze znalezieniem algorytmu lub opublikowaniem artykułów na temat triangulacji samoblokującego się wielokąta (również wielokąta o strukturze dziury). Czy ktoś może poprowadzić mnie do znalezienia opublikowanej pracy / algorytmu, proszę? PS: proszę odpowiednio oznaczyć to pytanie, nie mam wystarczającej liczby punktów reputacji, aby to zrobić.

9 ds.algorithms reference-request cg.comp-geom

3

Jak mogę losowo wygenerować drzewa o ograniczonej wysokości?

W przypadku projektu, nad którym pracuję, powinienem wygenerować losowo rozciągające się drzewa o ograniczonej wysokości. Zasadniczo wykonuję następujące czynności: 1) Wygeneruj drzewo opinające 2) Sprawdź wykonalność, jeśli to możliwe, zachowaj ją. 1) Zaczynając od minimalnego drzewa opinającego (Prim'a lub Kruskala), dodaję nieistniejącą krawędź i to tworzy cykl, wykrywam ten cykl …

9 ds.algorithms graph-algorithms random-walks

1

Jakieś sformułowania SAT / SMT VRP / VRPTW (TSP, Job-Shop-Scheduling)?

zastanawiam się, czy są jakieś podejścia do formułowania problemu trasy pojazdu z systemem Windows-Time ( VRPTW ) (jako problemem decyzyjnym) jako instancji SAT / SMT? (alternatywnie: TSP) Na przykład: „Czy istnieje prawidłowe rozwiązanie odwiedzające wszystkich klientów w ich ramach czasowych przy n = 10 pojazdach?” Ten problem decyzyjny może być …

9 ds.algorithms reference-request sat reductions tsp

3

Rozkład drzewa dla grafów płaskich

Najpierw zapytany na stronie math.SE bez odpowiedzi Załóżmy, że mam wykres płaski z osadzeniem planarnym, jak znaleźć rozkład drzewa? Jaki jest optymalny rozkład drzewa siatki kwadratowej -by- ? Nie do końca pewny, jak zdefiniować „optymalny”, ale powinien odróżniać rozkład z jedną dużą torbą od rozkładu z wieloma dużymi torbami.dddddd

9 ds.algorithms graph-theory graph-algorithms treewidth integer-lattice

2

Złożoność czasowa algorytmu Held-Karp dla TSP

Kiedy przejrzałem „ Dynamiczne podejście programistyczne do problemów z sekwencjonowaniem ” autorstwa Michaela Helda i Richarda M. Karpa, wpadłem na następujące pytanie: dlaczego złożoność ich algorytmu dla TSP jest (s. 199), mam na myśli skąd biorą współczynnik ? Jeśli dobrze zrozumiałem, k-1 oznacza liczbę dodatków dla każdego podzbioru miast. To …

9 ds.algorithms tsp exp-time-algorithms

1

Złożoność znalezienia składowej składowej macierzy * symetrycznej *

To jest wyspecjalizowana wersja poprzedniego pytania: Złożoność znalezienia składowej macierzy . W przypadku macierzy symetrycznych NxN wiadomo, że czas O (N ^ 3) wystarcza do obliczenia rozkładu własnego. Pytanie brzmi: czy możemy osiągnąć sub-sześcienną złożoność? Dzięki.

9 ds.algorithms time-complexity matrices linear-algebra na.numerical-analysis

2

Testowanie właściwości dla niezależnych zestawów

Załóżmy, że otrzymaliśmy wykres GGG i parametry k,ϵk,ϵk,\epsilon. Czy istnieją zakresy wartości dlakkk (czy jest to wykonalne dla wszystkich kkk), dla których można sprawdzić, czy GGG jest ϵϵ\epsilon-dużo posiadania niezależnego zestawu przynajmniej wielkości kkk w samą porę O(n+poly(1/ϵ))O(n+poly(1/ϵ))O(n + \text{poly}(1/\epsilon)) ? Jeśli użyjemy zwykłego pojęcia ϵϵ\epsilon-dale (tj. co najwyżej ϵn2ϵn2\epsilon …

9 ds.algorithms graph-theory reference-request property-testing

Pytania otagowane jako ds.algorithms