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.

1
Jak fundamentalne są matroidy i greedoidy w projektowaniu algorytmów?
Początkowo wprowadzono matroidy , aby uogólnić pojęcia liniowej niezależności zbioru podzbiorów stosunku do zbioru I podłoża . Niektóre problemy, które zawierają tę strukturę, pozwalają chciwym algorytmom znaleźć optymalne rozwiązania. Koncepcja greedoidów została później wprowadzona w celu uogólnienia tej struktury, aby uchwycić więcej problemów, które pozwalają na znalezienie optymalnych rozwiązań za …
5
Jak podejść do wyzwania Vertical Sticks
To pytanie zostało przeniesione z Teoretycznej wymiany stosów komputerowych, ponieważ można na nie odpowiedzieć w ramach wymiany stosów komputerowych. Migrował 7 lat temu . Ten problem pochodzi z wywiadstreet.com Dane są wartości całkowitych Y={y1,...,yn}Y={y1,...,yn}Y=\{y_1,...,y_n\} który reprezentuje nnn segmentów linii, tak że punktami końcowymi segmentu ijai są (i,0)(ja,0)(i, 0) i (i,yi)(ja,yja)(i, …
1
Czy istnieje skuteczny algorytm dla tego problemu pokrycia cyklu wierzchołków?
To pytanie zostało przeniesione z Mathematics Stack Exchange, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 3 lata temu . Próbowałem znaleźć algorytm do znalezienia maksymalnego pokrycia cyklu wierzchołków ukierunkowanego wykresu - to znaczy zestawu rozłącznych cykli, które zawierają wszystkie wierzchołki w , z jak największą liczbą …
3
Dlaczego Radix Sort ?
W sortowaniu radix najpierw sortujemy według najmniej znaczącej cyfry, a następnie sortujemy według drugiej najmniej znaczącej cyfry itd. I kończymy na posortowanej liście. Teraz, jeśli mamy listę liczb, potrzebujemy bitów, aby odróżnić te liczby. Tak więc liczba wykonanych przez nas przejść sortowania będzie wynosić . Każde przejście zajmuje czas O …
4
Minimalna liczba porównań potrzebnych do posortowania (uporządkowania) 5 elementów
Znajdź najmniejszą liczbę porównań potrzebną do posortowania (uporządkowania) pięciu elementów i opracuj algorytm, który sortuje te elementy przy użyciu tej liczby porównań. Rozwiązanie : Jest ich 5! = 120 możliwych wyników. Dlatego drzewo binarne do procedury sortowania będzie miało co najmniej 7 poziomów. Rzeczywiście, ≥ 120 oznacza≥ 7. Ale 7 …
4
Czy nie ma algorytmu sortowania ze wszystkimi konkretnymi pożądanymi właściwościami?
Na stronie internetowej Sorting Algorytmy wysunięto następujące oświadczenie: Idealny algorytm sortowania miałby następujące właściwości: Stabilny: nie zmienia się kolejności klawiszy równych. Działa w miejscu, wymagając dodatkowej przestrzeni.O ( 1 )O(1)O(1) Porównania klawiszy w najgorszym przypadku .O ( n ⋅ lg( n ) )O(n⋅lg⁡(n))O(n\cdot\lg(n)) Zamiany najgorszym przypadku .O ( n )O(n)O(n) …
3
Algorytm minimalizujący pole powierzchni, przy danej objętości
Rozważ następujące zadanie algorytmiczne: Dane wejściowe: dodatnia liczba całkowita wraz z podstawową faktoryzacją Znajdź: dodatnie liczby całkowite które minimalizują , z zastrzeżeniem ograniczenia, żennnx,y,zx,y,zx,y,zxy+yz+xzxy+yz+xzxy+yz+xzxyz=nxyz=nxyz=n Jaka jest złożoność tego problemu? Czy istnieje algorytm czasu wielomianowego? Czy to trudne NP? Ten problem zasadniczo pyta: ze wszystkich prostokątnych brył, których objętość wynosi i …
7
Jeden element, który różni się dwiema tablicami. Jak znaleźć to skutecznie?
Przygotowuję się do wywiadu na temat programowania i naprawdę nie mogę znaleźć najbardziej skutecznego sposobu rozwiązania tego problemu. Załóżmy, że mamy dwie tablice składające się z liczb nieposortowanych. Tablica 2 zawiera liczbę, której nie ma tablica 1. Obie tablice mają losowo rozmieszczone liczby, niekoniecznie w tej samej kolejności lub przy …
3
Konwertowanie problemów matematycznych na instancje SAT
Chcę zmienić problem matematyczny, który mam, w logiczny problem satysfakcji (SAT), a następnie rozwiązać go za pomocą SAT Solvera. Zastanawiam się, czy ktoś zna instrukcję, przewodnik lub cokolwiek, co pomoże mi przekonwertować mój problem na instancję SAT. Chcę też rozwiązać ten problem w czasie lepszym niż wykładniczy. Mam nadzieję, że …
2
Teoretyczne podstawy podziału i podboju
Przy projektowaniu algorytmów często stosuje się następujące techniki: Programowanie dynamiczne Chciwa strategia Dziel i rządź Podczas gdy w przypadku dwóch pierwszych metod istnieją dobrze znane podstawy teoretyczne, a mianowicie zasada optymalności Bellmana i teoria matroidów (odpowiednio greedoid), nie mogłem znaleźć takiej ogólnej struktury algorytmów opartych na D&C. Po pierwsze, zdaję …
4
Algorytmy sortowania, które akceptują losowy komparator
Ogólne algorytmy sortowania zazwyczaj wymagają zestawu danych do sortowania i funkcji komparatora, która może porównywać dwa pojedyncze elementy. Jeśli komparator jest relacją rzędu¹, to wynikiem działania algorytmu jest posortowana lista / tablica. Zastanawiam się jednak, które algorytmy sortowania faktycznie działałyby z komparatorem, który nie jest relacją rzędu (w szczególności, który …
6
w czasie O (n): Znajdź największy element w zestawie, w którym porównanie nie jest przechodnie
Tytuł zawiera pytanie. Jako dane wejściowe mamy listę elementów, które możemy porównać (określić, która jest największa ). Żaden element nie może być równy. Kluczowe punkty: Porównanie nie jest przechodnie (pomyśl o papierowych nożycach): może to być prawda: A> B, B> C, C> A (zwróć uwagę, że nie jest to poprawny …
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.