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...
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...
Według tej strony algorytm Dijkstry to po prostu BFS z kolejką priorytetową. Czy to naprawdę takie proste? Myślę, że
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...
W matematyce istnieje wiele dowodów na istnienie, które nie są konstruktywne, więc wiemy, że istnieje pewien obiekt, chociaż nie wiemy, jak go znaleźć. Szukam podobnych wyników w informatyce. W szczególności: czy istnieje problem, który możemy udowodnić, że można go rozstrzygać bez pokazywania...
Chcę udowodnić lub obalić istnienie algorytmu, który, biorąc pod uwagę tablicę ZAZAA liczb całkowitych, znajduje trzy indeksy ja , jja,joti, j i kkk takie, że i < j < kja<jot<ki < j < k i A [ i ] < A [ j ] < A [ k ]ZA[ja]<ZA[jot]<ZA[k]A[i] < A[j] < A[k] (lub stwierdza, że...
Tablica lub wektor to tylko sekwencja wartości. Z pewnością można je zaimplementować za pomocą połączonej listy. To tylko kilka węzłów ze wskaźnikami do następnego węzła. Stosy i kolejki to dwa abstrakcyjne typy danych powszechnie nauczane na kursach CS wprowadzających. Gdzieś w klasie uczniowie...
Jestem ciekawy, jak można bardzo kompaktowo skompresować domenę dowolnej nazwy hosta IDN (zgodnie z definicją w RFC5890 ) i podejrzewam, że może to stać się ciekawym wyzwaniem. Host lub nazwa domeny Unicode (etykieta U) składa się z ciągu znaków Unicode, zwykle ograniczonego do jednego języka w...
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óć...
Chcę wiedzieć, który algorytm jest najszybszy do pomnożenia dwóch liczb n-cyfrowych? Złożoność przestrzeni można tutaj
Skończyłem większość materiału w książce Cormen's Intro to Algorytmy i szukam książki o algorytmach, która obejmowałaby materiał poza książką Cormana. Czy są jakieś rekomendacje? UWAGA: Zapytałem o to przy przepełnieniu stosu, ale nie byłem zbyt zadowolony z odpowiedzi. UWAGA: Patrząc na...
Często wchodzę w interakcje z ludźmi, którzy chcą poprosić o algorytm dla problemu obliczeniowego (lub jego złożoności), ale nie wyrażają go w sposób rygorystyczny dla nas (informatyków) do zrozumienia. Odsyłanie ich do książek takich jak CLRS nie jest pomocne, ponieważ tamtejsze przykłady zwykle...
Mam zadanie, w którym muszę skorzystać z drzewa wyszukiwania binarnego i zmienić je, aby samo uporządkować się tak, aby elementy, do których najczęściej uzyskiwano dostęp (mają wyższy priorytet), znajdowały się na szczycie drzewa, przy czym węzeł główny był najczęściej dostępnym węzłem . Profesor...
Zastanawiam się, jak znaleźć obwód rzadkiego nieukierunkowanego wykresu. Przez rzadki mam na myśli . Przez optymalne rozumiem najmniejszą złożoność czasową.| mi| =O ( | V|)|mi|=O(|V.|)|E|=O(|V|) Myślałem o pewnej modyfikacji algorytmu Tarjana dla niekierowanych grafów, ale nie znalazłem dobrych...
Chciałbym napisać prosty program, który akceptuje zestaw okien (szerokość + wysokość) oraz rozdzielczość ekranu i wyświetla układ tych okien na ekranie, aby okna zajmowały najwięcej miejsca. Dlatego można zmienić rozmiar okna, zachowując output size >= initial sizei proporcje. Tak więc dla okna...
Otrzymujesz n liczb całkowitych wszystkie od do . Pod każdą liczbą całkowitą należy wpisać liczbę całkowitą między a z warunkiem, że tworzą ciąg nie malejący. Zdefiniuj odchylenie takiej sekwencji na . Zaprojektuj algorytm, który znajdzie b_i z minimalnym odchyleniem w czasie wykonywania O (n \...
Czy są jakieś problemy w które mają algorytmy losowe przekraczające dolne granice algorytmów deterministycznych? Mówiąc konkretniej, czy znamy jakieś dla którego ? Tutaj \ mathsf {PTIME} (f (n)) oznacza zestaw języków rozstrzygalnych przez losową TM z błędem o stałym ograniczeniu (jedno- lub...
Przed przeczytaniem „Sztuki programowania komputerowego” (TAOCP) nie zastanawiałem się głęboko nad tymi pytaniami. Używałbym pseudokodu do opisywania algorytmów, rozumienia ich i szacowania czasu działania tylko o rzędach wzrostu. TAOCP gruntownie zmienia zdanie. TAOCP używa angielskiego...
W większości implementacji algorytmów genetycznych nacisk kładziony jest na krzyżowanie i mutację. Ale w jakiś sposób większość z nich pomija diploidalną (dominującą / recesywną) naturę genów. O ile moje (ograniczone) rozumienie dominuje / recesywna natura genów jest bardzo ważnym czynnikiem...
bbbab=cmodNab=cmodNa^b=c \bmod NaaacccNNN Zastanawiam się, w jakich grupach złożoności (np. Dla komputerów klasycznych i kwantowych) to jest i jakie podejścia (tj. Algorytmy) są najlepsze do wykonania tego zadania. Powyższy link do Wikipedii tak naprawdę nie zapewnia bardzo konkretnych środowisk...