Pytania otagowane jako algorithms

Algorytm jest sekwencją dobrze zdefiniowanych kroków, które definiują abstrakcyjne rozwiązanie problemu. Użyj tego tagu, gdy Twój problem dotyczy projektowania i analizy algorytmów.

2
Złożoność znalezienia piłki, która maksymalizuje liczbę leżących w niej punktów
Biorąc pod uwagę zbiór punktów x1,…,xn∈R2x1,…,xn∈R2x_1, \ldots, x_n \in \mathbb{R}^2 i promień . Co jest złożonością znalezienia punktu o większej liczbie punktów w odległości mniejszej niż . Np. Ten, który maksymalizuje ?rrrrrr∑ni=11∥x−xi∥≤r∑i=1n1‖x−xi‖≤r\sum_{i=1}^n \mathbb{1}_{\|x - x_i\| \leq r} Algorytm brutalnej siły polegałby na przejściu każdego punktu i zliczeniu liczby punktów znajdujących …
1
Czy parser Earleya można przekształcić w rozmyty parser podobny do Levenshtein Automata Algo dla DFA?
Istnieje sposób wykonywania rozmytego parsowania (akceptuje ciągi nawet w literówkach do określonej odległości edycji), z DFA i skonstruowanymi w czasie wykonywania automatami Levenshtein słowa wejściowego. Czy coś podobnego można zrobić z parserem Earley? Trudno mi zrozumieć algorytm, a co dopiero odpowiedzieć na to pytanie.
2
Czy ten kombinatoryczny problem optymalizacji jest podobny do jakiegokolwiek znanego problemu?
Problem jest następujący: Mamy dwuwymiarową tablicę / siatkę liczb, z których każda reprezentuje pewną „korzyść” lub „zysk”. Także ma dwie nieruchome całkowite i h (jako „szerokość” i „wysokość”). A stałej całkowitej n .wwwhhhnnn Teraz chcą nałożyć prostokątów o wymiarach szer × h na siatce, tak aby łączna suma wartości komórek …
4
Czy istnieje metoda automatycznej analizy algorytmów w czasie wykonywania?
Zastanawiam się, czy istnieje metoda automatycznej analizy środowiska wykonawczego, która działa co najmniej na odpowiednim podzbiorze algorytmów (algorytmów, które można analizować)? Poszukałem „Automatycznej analizy algorytmu”, co mi to dało, ale to zbyt math. Chcę tylko prosty przykład w psuedocode, który mogę zrozumieć. Może to być zbyt szczegółowe, ale pomyślałem, że …
4
Cięcie równych drążków z różnych drążków
Masz drążków o dowolnej długości, niekoniecznie integralnych.nnn Cięcie niektórych patyków (jedno cięcie tnie jeden patyk, ale możemy ciąć tak często, jak chcemy), chcesz uzyskać takich, aby:k &lt; nk&lt;nk<n Wszystkie te kije mają taką samą długość;kkk Wszystkie kije są co najmniej tak długie, jak wszystkie inne kije.kkk Pamiętaj, że po wykonaniu …
2
Relacje równoważności obejmują problem (w teorii grafów)
Relację równoważności na skończonym zestawie wierzchołków można przedstawić za pomocą nieukierunkowanego wykresu, który jest rozłącznym połączeniem klików. Zestaw wierzchołków reprezentuje elementy, a krawędź reprezentuje równoważność dwóch elementów. Jeśli mam wykres i wykresy G 1 , … , G k , mówimy, że G jest objęty G 1 , … , …
3
Dlaczego Miller – Rabin zamiast testu pierwotności Fermata?
Z dowodu Millera-Rabina , jeśli liczba przechodzi test pierwotności Fermata , musi również przejść test Millera-Rabina z tą samą podstawą (zmienną w dowodzie). A złożoność obliczeń jest taka sama.zaaa Z testu pierwotności Fermata wynika : Chociaż liczby Carmichaela są znacznie rzadsze niż liczby pierwsze, 1 jest ich wystarczająco dużo, aby …
1
Krótki i sprytny dowód silnego twierdzenia o dualności dla programowania liniowego
Rozważ programy liniowe Primal:Ax⃗ ≤b⃗ maxc⃗ Tx⃗ Primal:Ax→≤b→maxc→Tx→\begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array} Dual:c⃗ ≤y⃗ TAminy⃗ Tb⃗ Dual:c→≤y→TAminy→Tb→\begin{array}{|ccc|} \hline Dual: & \vec{c} \leq \vec{y}^TA \hspace{.5cm} & \min \vec{y}^T\vec{b} \\ \hline \end{array} Twierdzenie o słabym dualności mówi, że jeśli i spełniają ograniczenia, to …
4
Przykład algorytmu, w którym element wykonawczy niskiego rzędu dominuje w środowisku wykonawczym dla jakichkolwiek praktycznych danych wejściowych?
Notacja Big-O ukrywa stałe współczynniki, więc istnieją pewne algorytmy O(n)O(n)O(n) , które są niewykonalne dla jakiegokolwiek rozsądnego rozmiaru wejściowego, ponieważ współczynnik na jest tak duży.nnn Czy są jakieś znane algorytmy, których środowisko wykonawcze to ale z jakimś niskim terminem, który jest tak ogromny, że dla rozsądnych wielkości wejściowych całkowicie dominuje …
3
Minimalizacja długości przewodów
Mój problem jest taki: Mam fizyczny układ reprezentowany jako wykres. Węzły reprezentują haki / kanały, w których drut może się zakotwiczyć, a krawędzie są możliwym połączeniem między 2 węzłami, z których może przejść drut. Istnieją specjalne Węzły, zwane rozdzielaczami, z których pojedynczy drut można podzielić na 2 lub więcej do …
3
Podczas testowania n elementów, jak pokryć wszystkie podzbiory t przez jak najmniejszą liczbę podzbiorów s?
Ten problem powstał w wyniku testowania oprogramowania. Problem jest trochę trudny do wyjaśnienia. Najpierw podam przykład, a następnie spróbuję uogólnić problem. Do przetestowania jest 10 elementów, od A do J, oraz narzędzie testujące, które może testować 3 elementy jednocześnie. Kolejność elementów w narzędziu testowym nie ma znaczenia. Oczywiście do wyczerpujących …
1
Problem z kamykami
Pebbling to gra w pasjansa rozgrywana na niekierowanym grafie , gdzie każdy wierzchołek ma zero lub więcej kamyków. Pojedynczy ruch kamyka polega na usunięciu dwóch kamyków z wierzchołka v i dodaniu jednego kamyka do dowolnego sąsiada v . (Oczywiście, wierzchołek v musi mieć co najmniej dwa kamyki przed ruchem). Problem …
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.