Informatyka

3

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

9 algorithms computational-geometry

2

Badam uczenie się PAC (teorii uczenia obliczeniowego) jako początkujący bez wcześniejszej wiedzy o uczeniu maszynowym / sztucznej inteligencji. Model badam głównie z historycznego punktu widzenia. W tym celu najważniejsze są oczywiście wyniki oparte na modelu. Istnieje wystarczająco dużo dokumentów, które dokumentują te wyniki. Ale chcę też napisać coś o tym, …

9 machine-learning

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

1

Konwertuj CFG na PDA

Czy istnieje zestaw reguł lub metod służących do konwersji gramatyki bezkontekstowej na automaty wypychające? Znalazłem już kilka slajdów w Internecie, ale nie byłem w stanie ich zrozumieć. W slajdzie 10 mówi o niektórych zasadach, czy ktokolwiek mógłby to wyjaśnić?

9 context-free formal-grammars pushdown-automata simulation

1

Poszukuję książki popularnonaukowej na temat bioinformatyki lub genomiki obliczeniowej

Inteligentny 15-latek, którego znam, interesuje się zarówno informatyką, jak i genetyką. Powiedziałem jej, że te pola stanowią doskonałą kombinację. Chciałbym dać jej książkę o bioinformatyce lub genomice obliczeniowej. Szukam fajnej książki, a nie podręcznika. W szczególności powinno to zainspirować ludzi do chęci studiowania tej dziedziny, a nie do zapewnienia samej …

9 education books bioinformatics

4

Jaki jest rodzaj semantyki języka programowania?

W rozdziale 1 Praktycznych podstaw języków programowania autor wspomina, że abstrakcyjne drzewa składniowe są powiązane z sortowaniem . Intuicyjnie, rodzaje są jak typy, ale chciałbym wiedzieć, czy mają precyzyjną definicję. Byłbym zadowolony, gdyby podano również niektóre referencje.

9 terminology programming-languages semantics

1

Różnica między językami akceptowanymi przez dwa DFA o różnych stanach początkowych / stanach akceptacji?

Ostatnio zadałem pytanie na temat Math SE. Na razie brak odpowiedzi. To pytanie jest związane z tym pytaniem, ale bardziej technicznymi szczegółami w kierunku informatyki. Biorąc pod uwagę dwa DFA i gdzie zbiór stanów, alfabet wejściowy i funkcja przejścia i są takie same, stany początkowe i stany końcowe (akceptujące) mogą …

9 formal-languages reference-request finite-automata

2

Czy przydatne są probabilistyczne struktury danych wyszukiwania?

SkipList zapewnia to samo O(logn)O(log⁡n)O(\log n)ogranicza wyszukiwanie jako drzewo zrównoważone z tą zaletą, że ponowne zbalansowanie nie jest konieczne. Ponieważ SkipList jest konstruowany przy użyciu losowych rzutów monetą, granice te obowiązują tylko tak długo, jak długo struktura SkipList jest wystarczająco „zrównoważona”. W szczególności z prawdopodobieństwem1/nc1/nc1/n^c dla jakiejś stałej c>0c>0c>0, zrównoważona …

9 data-structures search-trees probabilistic-algorithms

2

Dwustanowa maszyna Turinga do dopasowywania nawiasów

Na studiach poznawaliśmy ogólnie teorię obliczeń, a dokładniej maszyny Turinga. Jednym z wielkich wyników teoretycznych jest to, że kosztem potencjalnie dużego alfabetu (symboli) można zmniejszyć liczbę stanów do zaledwie 2. Szukałem przykładów różnych maszyn Turinga, a częstym przedstawionym przykładem jest dopasowywanie / sprawdzanie nawiasów. Zasadniczo sprawdza, czy ciąg nawiasów, np. …

9 turing-machines context-free parsers

1

Czy następująca transformacja zachowuje płynność kontekstową?

Napotkałem ten problem związany z manipulowaniem językiem bezkontekstowym. Niech będzie językiem bezkontekstowym. Zdefiniuj dla każdego . Czy zawsze jest pozbawione kontekstu? Domyślam się, że zachowa kontekstowość. Czy ktoś może przedstawić podstawowy dowód na to?LL.LL#={x:xi∈LL.#={x:xja∈L.L^{\#} = \{ x : x^i \in Li=0,1,2,...}ja=0,1,2),...}i=0,1,2,...\}L#L.#L^{\#}

9 formal-languages context-free

2

Czy istnieje algorytm „sortowania”, który zwraca losową permutację podczas korzystania z komparatora z monetą?

Zainspirowane tym pytaniem, w którym pytający chce wiedzieć, czy czas działania zmienia się, gdy komparator użyty w standardowym algorytmie wyszukiwania zostaje zastąpiony uczciwym rzucie monetą, a także wyraźnym niepowodzeniem Microsoftu w napisaniu jednolitego generatora permutacji, moje pytanie jest zatem : Czy istnieje algorytm sortowania oparty na porównaniu, który w zależności …

9 sorting randomized-algorithms permutations

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

3

Którym komponentem oprogramowania zarządza pamięć podręczna procesora?

Pamięci podręczne procesora są wykorzystywane przez wykorzystanie lokalizacji czasowej i przestrzennej. Moje pytanie brzmi: kto jest odpowiedzialny za zarządzanie tymi pamięciami podręcznymi? Czy ten system operacyjny rozpoznaje określony wzorzec dostępu, a następnie zarządza pamięcią podręczną (tj. Przechowuje dane) przy użyciu wywołań funkcji OS?

9 computer-architecture cpu-cache

2

Czy sieci semantyczne są ontologiami?

Walczę z kilkoma definicjami reprezentacji wiedzy i szukam wiarygodnej pomocy w ich rozróżnieniu. Szukałem na wikipedii i wielu stronach internetowych różnicy między ontologiami a sieciami semantycznymi (nie mylić z siecią semantyczną). Chociaż strona wikipedii w sieci semantycznej nigdy nie odwołuje się do ontologii, wydają się one bardzo podobne i mają …

9 terminology knowledge-representation ontologies

1

Twardość zbliżonych programów całkowitych 0-1

Biorąc pod uwagę (binarny) program liczbowy w postaci:0 , 10,10,1 minśwfa( x )A x = bxja≥ 0xja∈ { 0 , 1 }∀ i∀ iminf(x)s.t.Ax=bxi≥0∀ixi∈{0,1}∀i \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} & …

9 complexity-theory np-complete approximation integer-programming