Informatyka

2

Co to jest algorytm aproksymacji bicriteria?

Co to jest algorytm aproksymacji bicriteria? Nadal pojawia się to w przypadku klastrowania strumienia danych. Czy ma to związek z optymalizacją wielu celów? Właśnie tam natknąłem się na: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. Artykuł dotyczy strumieniowej wersji algorytmu k-średnich. W pracy znajdują się odniesienia, ale żadne z nich nie wyjaśnia, czym jest algorytm aproksymacji …

11 optimization approximation

3

Zrozumienie algorytmu problemu ze stacją benzynową

W przypadku problemu ze stacją benzynową podajemy miast i drogi między nimi. Każda droga ma długość, a każde miasto określa cenę paliwa. Jedna jednostka drogi kosztuje jedną jednostkę paliwa. Naszym celem jest przejście ze źródła do miejsca docelowego w najtańszy możliwy sposób. Nasz czołg jest ograniczony pewną wartością.{ 0 , …

11 algorithms graphs recurrence-relation

1

Złożoność znalezienia macierzy pseudoinwersyjnej

Ile operacji arytmetycznych jest wymaganych do znalezienia pseudo-odwrotnej macierzy Moore'a i Penrose'a o dowolnym polu? Jeśli macierz jest odwracalna i ma złożoną wartość, to jest to tylko odwrotność. Znalezienie odwrotności zajmuje czas , gdzie jest stałą mnożenia macierzy. Jest to Twierdzenie 28.2 we Wstępie do Algorytmów 3. edycja.ωO(nω)O(nω)O(n^\omega)ωω\omega Jeśli macierz …

11 algorithms linear-algebra

1

Maszyna Turinga - nieskończona taśma w jednym lub dwóch kierunkach

Widziałem maszyny Turinga przedstawiane za pomocą taśm nieskończonych w jednym i w dwóch kierunkach. Czy jest jakaś różnica w mocy takich maszyn Turinga, czy są one zasadniczo równoważne? W mojej głowie myślę, że są one równoważne, ponieważ sądzę, że musi istnieć jakiś sposób na przedstawienie dwustronnej nieskończonej taśmy jako jednokierunkowej …

11 turing-machines

1

Jak szybko możemy zdecydować, czy dany DFA jest minimalny?

Minimalizowanie deterministycznych automatów skończonych (DFA) to problem, który został dokładnie przestudiowany w literaturze, i zaproponowano kilka algorytmów w celu rozwiązania następującego problemu: Biorąc pod uwagę DFA , oblicz odpowiednią minimalną DFA akceptującą ten sam język, co \ mathscr {A} . Większość tych algorytmów działa w czasie wielomianowym.ZAA\mathscr{A}ZAA\mathscr{A} Zastanawiam się jednak, …

11 algorithms formal-languages finite-automata

1

Algorytm równoległy do znalezienia maksymalnego czasu przy użyciu procesorów

Zostaliśmy zaprezentowani w klasie z algorytmem znajdowania maksimum w tablicy równolegle w złożoności czasowej z komputerami.O ( 1 )O(1)O(1)n2)n2)n^2 Algorytm był: Biorąc pod uwagę tablicę A o długości n: Utwórz tablicę flag B o długości n i zainicjuj ją zerami z komputerów.nnn Porównaj co 2 elementy i napisz 1 w …

11 algorithms search-algorithms parallel-computing

2

Trudny problem obliczeniowy na specjalnej klasie grafów dwustronnych

Interesują mnie właściwości klasy grafów dwustronnych których wszystkie węzły w są 3-regularne, wszystkie węzły w są 2-regularne, a. Po pierwsze, czy jest to dobrze znana klasa grafów? Po drugie,X Y | X | = | 2 T / 3 |G ( X∪ Y, E)G(X∪Y,E)G(X \cup Y, E)XXXYYY| X| = | …

11 complexity-theory graph-theory

3

Algorytm dopasowywania liczb przy minimalnej liczbie ruchów

Jest to rodzaj pytania do edycji i jest bardzo łatwe. Jestem po prostu dość martwy w tym temacie i jak dotąd nie mogę tego rozgryźć. Biorąc pod uwagę szereg liczb, np [3, 1, 1, 1] Jak najskuteczniej przekształcić wszystkie liczby w tę samą liczbę przy minimalnej liczbie „ruchów”? Przez „przeniesienie” …

11 algorithms optimization

1

Czy to trudne NP? Nie mogę tego udowodnić.

Mam problem i myślę, że jest to trudny NP, ale nie mogę tego udowodnić. Oto wykres warstw, w którym warstwa 0 jest najwyższą warstwą, a warstwa L najniższą. istnieje pewna ukierunkowana krawędź między warstwami, gdzie krawędź (A, B) wskazuje, że węzeł A może [pokrywać] węzeł B. A kiedy A może …

11 graphs np

2

Przykłady języków bezkontekstowych z uzupełnieniami bezkontekstowymi

Języki bezkontekstowe nie są zamknięte pod uzupełnieniem. W wykładach podano nam ten sam argument, co tutaj na Wikipedii : A={anbncm; m,n∈N0}andB={ambncn; m,n∈N0},A={anbncm; m,n∈ℕ0}andB={ambncn; m,n∈ℕ0},A = \{\mathtt a^n \mathtt b^n \mathtt c^m;~m, n ∈ ℕ_0\}\quad\text{and}\quad B = \{\mathtt a^m \mathtt b^n \mathtt c^n;~m, n ∈ ℕ_0\}, oba AAA i BBB są …

11 formal-languages context-free

1

Wskazówki dotyczące nauczania przy użyciu kodowania na żywo

Uczestniczę w kursie programowania i algorytmów pierwszego roku. W ostatnim wykładzie postanowiłem zaprezentować materiał przy użyciu kodowania na żywo , co w zasadzie oznaczało, że siedzę za klawiaturą i piszę kod i oceniam go, używając emacsa, aby ułatwić ten proces. Było to dość udane i uczniowie skomentowali, jak bardzo doceniają …

11 education didactics

1

Wariant problemu plecakowego

Jak podchodziłbyś do problemu plecaka w sytuacji dynamicznego programowania, gdybyś musiał teraz ograniczyć liczbę przedmiotów w plecaku o stałe ppp ? Jest to ten sam problem (maksymalna waga WWW , każdy przedmiot ma wartość vvv i ciężar www ), ale można dodać tylko ppp przedmiotów do plecaka i oczywiście trzeba …

11 algorithms optimization dynamic-programming knapsack-problems

3

Dlaczego wyrażenia regularne są definiowane za pomocą operacji łączenia, łączenia i operacji gwiazdowych?

Regularne expresssion jest zdefiniowany rekurencyjnie jako aaa dla niektórych jest wyrażeniem regularnym,a∈Σa∈Σa \in \Sigma εε\varepsilon jest wyrażeniem regularnym, ∅∅\emptyset jest wyrażeniem regularnym, (R1∪R2)(R1∪R2)(R_1 \cup R_2) gdzie i są wyrażeniami regularnymi, jest wyrażeniem regularnym,R1R1R_1R2R2R_2 (R1∘R2)(R1∘R2)(R_1 \circ R_2) gdzie i są wyrażeniami regularnymi, jest wyrażeniem regularnym,R1R1R_1R2R2R_2 (R1)∗(R1)∗(R_1)^* gdzie jest wyrażeniem regularnym jest …

11 formal-languages regular-languages regular-expressions

3

Czy istnieją algorytmy potęgowania równoległego macierzy, które są bardziej wydajne niż mnożenie sekwencyjne?

Wymagane jest znalezienie mocy (dodatniej liczby całkowitej) macierzy liczb rzeczywistych. Istnieje wiele wydajnych algorytmów mnożenia macierzy (np. Niektóre algorytmy równoległe to Cannon, DNS ), ale czy istnieją algorytmy, które są przeznaczone właśnie do znalezienia mocy macierzy i które są bardziej wydajne niż sekwencyjne wykonywanie mnożenia macierzy? Szczególnie interesują mnie algorytmy …

11 algorithms parallel-computing efficiency matrices numerical-algorithms

1

Jak zamapować taśmy maszyny Turinga typu „k-tape” na pojedynczą taśmę maszyny Turinga typu „1-tape”

Czytam Sipser i trudno mi zrozumieć, na czym polega ten proces, więc jeśli dasz mi k maszyn Turinga z k taśmami, mogę wypluć równoważną maszynę Turinga za pomocą tylko jednej taśmy. Przykład byłby miły. Właściwie to naprawdę opracowany przykład, który pokazuje, jak przejść z TM z taśmami na tę, która …

11 turing-machines simulation