Informatyka algorithms

2

Algorytm zastępowania stron zegara - już istniejące strony

Czy podczas symulacji algorytmu zastępowania strony zegara, gdy pojawia się odwołanie, które jest już w pamięci, wskazówka zegara wciąż rośnie? Oto przykład: Z 4 miejscami, wykorzystując algorytm zastępowania strony zegara Lista referencyjna: 1 2 3 4 1 2 5 1 3 2 4 5 Początkowa lista wyglądałaby następująco: -> [1][1] …

9 algorithms paging virtual-memory

1

Znalezienie najkrótszej ścieżki między dwoma węzłami

Biorąc pod uwagę ważony digraf G=V,EG=V,EG=V,Ei funkcja wagi, d(u,v)d(u,v)d(u,v), zwykle można użyć algorytmu Dijkstry, aby uzyskać najkrótszą ścieżkę. Interesuje mnie to, jak uzyskać2nd2nd2^{nd}- najkrótsza ścieżka, 3rd3rd3^{rd}-krótko i tak dalej. Pytania: Czy istnieje skuteczny algorytm do uzyskania i-tej najkrótszej ścieżki między dwoma węzłami na wykresie ważonym? Czy istnieje skuteczny algorytm pozwalający …

9 algorithms graphs shortest-path graph-traversal

2

Projekt oceny rówieśniczej - wybór wykresu w celu uzyskania dokładnych rankingów / ocen

Tło. Piszę kod do półautomatycznej gradacji, używając gradacji rówieśniczej jako części procesu gradacji. Uczniowie otrzymują pary esejów na raz, a uczniowie mają suwak do wyboru, który jest lepszy io ile lepszy. np. suwak może wyglądać mniej więcej tak: A---X-B Na podstawie wyników oceny rówieśniczej eseje są klasyfikowane, a nauczyciel oceni …

9 algorithms graphs modelling

1

jeśli chcę tylko jednego elementu macierzy odwrotnej, czy istnieje szybki algorytm?

Używam Mathematiki do rozwiązywania problemów. Mam pytanie dotyczące macierzy odwrotnej. jeśli chcę tylko jednego elementu macierzy odwrotnej, czy istnieje szybszy algorytm niż użycie Inversedo obliczenia całej macierzy odwrotnej i wyodrębnienie elementu, który chcę?

9 algorithms

3

Losowe próbkowanie w wielokącie

Chciałbym pobrać próbkę jednorodnie losowego punktu w wielokącie ... Gdyby pobrać próbkę dużej liczby, równie dobrze mogliby wpaść w dwa regiony, jeśli mają ten sam obszar. Byłoby to dość proste, gdyby był kwadratem, ponieważ jako moje współrzędne wziąłbym dwie liczby losowe w [0,1]. Kształt, który mam, jest zwykłym wielokątem, ale …

9 algorithms randomness sampling random-number-generator

4

Jaki jest dobry algorytm do generowania losowych DFA?

Generuję losowe DFA, aby przetestować na nich algorytm redukcji DFA. Algorytm, którego teraz używam, jest następujący: dla każdego stanu , dla każdego symbolu w alfabecie dodaj do jakiegoś losowego stanu. Każde państwo ma takie samo prawdopodobieństwo, że stanie się stanem końcowym.qqqdodocδ( q, c )δ(q,do)\delta (q, c) Czy to dobra metoda …

9 algorithms finite-automata randomness pseudo-random-generators random-graphs

3

Dowiedz się, czyja kolej na zakup rogalików

Zespół zdecydował, że każdego ranka ktoś powinien przynieść rogaliki dla wszystkich. Nie powinna to być ta sama osoba za każdym razem, więc powinien istnieć system określający, która kolej będzie następna. Celem tego pytania jest określenie algorytmu decydującego o tym, czyja kolej przyniesie rogaliki jutro. Ograniczenia, założenia i cele: Który z …

9 algorithms scheduling

3

Co to są zdegenerowane wielokąty?

Co to są zdegenerowane wielokąty? Jak sprawdzić, czy dana para wielokątów jest zdegenerowana, czy nie?

9 algorithms computational-geometry

1

Jaką miarę zaburzeń należy zastosować podczas analizy Quicksort

Próbuję zrozumieć, dlaczego quicksort z użyciem partycji Lomuto i ustalonego elementu przestawnego działa nieprawidłowo, ale ogólnie słabo, na losowo generowanych danych wejściowych. Myślę, że chociaż dane wejściowe są generowane losowo, sekwencje mogą być uporządkowane, ale nie jestem pewien, jak zmierzyć poziom nieporządku w sekwencjach. Myślałem o użyciu liczby inwersji, ale …

9 algorithms sorting

2

Złożoność znalezienia piku 2-D (MIT OCW 6.006)

W wideo recytacyjnym dla MIT OCW 6.006 o 43:30, Biorąc pod uwagę m × nm×nm \times n matryca ZAAA z mmm kolumny i nnn wiersze, algorytm 2-D znajdowania pików, w którym pik jest dowolną wartością większą lub równą sąsiednim sąsiadom, opisano jako: Uwaga: W przypadku nieporozumień przy opisywaniu kolumn za …

9 algorithms algorithm-analysis asymptotics matrices

1

Usuń minimalną liczbę wierzchołków, aby rozłączyć wykres

Zastanów się nad niekierowanym wykresem ze źródłem i wierzchołkiem ujścia. Chcemy usunąć minimalną liczbę wierzchołków na tym wykresie, aby odłączyć dowolną ścieżkę między źródłem a ujściem. Czy możemy to zrobić, używając algorytmu maksymalnego przepływu, minimalnego cięcia?

9 algorithms graph-theory network-flow

1

Znajdź najdłuższy powtarzający się wzór w ciągu

Szukam wydajnego algorytmu do znajdowania najdłuższego powtarzającego się wzorca w ciągu. Weźmy na przykład następujący ciąg liczb: 5431428571428571428571428571427623874534. Jak widać, 142857142857jest to najdłuższy wzór, który powtarza się kilka razy (przynajmniej dwa razy) w tym ciągu. Powtarzany ciąg nie powinien zawierać żadnych pomysłów, a nie brutalną siłę?

9 algorithms strings subsequences

1

Minimalny rozcięcie na ważonych ukierunkowanych wykresach acyklicznych z potencjalnie ujemnymi wagami

Wystąpił następujący problem: Biorąc pod uwagę ukierunkowany wykres acykliczny z rzeczywistymi wartościami grubości krawędzi oraz dwoma wierzchołkami s i t, oblicz minimalny st st cut. Dla ogólnych wykresów jest to trudne NP, ponieważ można w prosty sposób zredukować maksymalne cięcie, po prostu odwracając wagi krawędzi (popraw mnie, jeśli się mylę). …

9 algorithms complexity-theory graph-theory weighted-graphs

1

Wybór funkcji drzewa decyzyjnego o stałej długości w celu zminimalizowania średniej wydajności wyszukiwania

Mam złożone zapytanie używane do przeszukiwania zestawu danych celu znalezienia . Każde zapytanie zajmuje średni czas więc całkowity czas w wyszukiwaniu liniowym wynosi. Mogę podzielić zapytanie na prostsze zapytania częściowe q_i i znaleźć i gdzie . Każde podzapytanie jest znacznie szybsze do obliczenia, więc ogólnie szybciej jest znaleźć a następnie …

9 algorithms optimization machine-learning greedy-algorithms databases

3

Skuteczne wyszukiwanie liczby mniejszych elementów dla każdego elementu w tablicy

Utknąłem na tym problemie: Biorąc pod uwagę tablicę AZAA z pierwszego nnn liczby naturalne losowo permutowane, tablica BbB jest zbudowany tak, że B(k)b(k)B(k) jest liczbą elementów od A(1)ZA(1)A(1) do A(k−1)ZA(k-1)A(k-1) które są mniejsze niż A(k)ZA(k)A(k). i) Biorąc pod uwagę AZAA czy możesz znaleźć BbB w O(n)O(n)O(n)czas? ii) Biorąc pod uwagęBbB …

9 algorithms arrays permutations

Pytania otagowane jako algorithms