Byłem studiowania Współczynnik korelacji rang Spearmana ρ=∑i(xi−x¯)(yi−y¯)∑i(xi−x¯)2∑i(yi−y¯)2−−−−−−−−−−−−−−−−−−−√ρ=∑i(xi−x¯)(yi−y¯)∑i(xi−x¯)2∑i(yi−y¯)2\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}} . dla dwóch list i ....
Pytanie brzmi: ćwiczenie 1.9 z książki Arory-Barak Computational Complexity - A Modern Approach : Zdefiniuj maszynę RAM Turing jako maszynę Turinga, która ma pamięć o dostępie swobodnym. Sformalizujemy to w następujący sposób: Maszyna ma nieskończoną tablicę A, która jest inicjalizowana dla...
Czy z dostępem Oracle do większy niż ? Rozumiem, że to tylko maszyna Turinga, która może wysyłać zapytania do innej maszyny , jeśli tak, to może symulować ? Czy coś jest nie tak z tym
Adresy IPv6 w postaci 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0są znacznie trudniejsze do zapamiętania lub nawet transkrypcji niż 4 oktety IPv4. Tam nie było próby ograniczenia tego, co adresy IPv6 jakoś bardziej niezapomniany. Czy istnieje celowo słaba funkcja haszująca, którą można odwrócić, aby...
Czy istnieje formalna definicja średniej wysokości drzewa binarnego? Mam pytanie instruktażowe dotyczące znalezienia średniej wysokości drzewa binarnego przy użyciu następujących dwóch metod: Naturalnym rozwiązaniem może być przyjęcie średniej długości wszystkich możliwych ścieżek od korzenia do...
Nie jestem pewien, czy to pytanie należy tutaj i przepraszam, jeśli nie. Chcę opracować programowy sposób, w jaki mogę probabilistycznie określić, czy dany ciąg „należy” do worka ciągów. Na przykład, jeśli mam torbę z 10 000 nazwami miast w USA, a następnie mam ciąg „Philadelphia”, chciałbym...
Poprosiłem (nasion) pytanie o sumach Landau warunkach przed , próbując ocenić niebezpieczeństwa nadużywania notacji asymptotyka w arytmetyce, z mieszanym powodzeniem. Teraz, tutaj nasz guru ds. Nawrotów, JeffE , zasadniczo robi to: ∑i=1nΘ(1i)=Θ(Hn)∑i=1nΘ(1i)=Θ(Hn)\qquad \displaystyle \sum_{i=1}^n...
Załóżmy, że to zwykły język nad uporządkowanym alfabetem. Czy język jest zbudowany przez wzięcie każdego słowa w i posortowanie go zawsze jako zwykłego
\newcommand\ldotd{\mathinner{..}} Biorąc pod uwagę, że A[1..n]A[1..n]A[1\ldotd n] to liczby całkowite takie, że 0≤A[k]≤m0≤A[k]≤m0\le A[k]\le m dla wszystkich 1≤k≤n1≤k≤n1\le k\le n oraz występowanie każdego liczba z wyjątkiem określonej liczby w A[1..n]A[1..n]A[1\ldotd n] jest liczbą nieparzystą....
Jaka jest złożoność obliczeń ?nn2,n∈Nnn2,n∈Nn^{n^2},\;n \in
W Wikipedii podano implementację oddolnego schematu programowania dynamicznego dla odległości edycji. Nie jest całkowicie zgodny z definicją; komórki wewnętrzne są obliczane w następujący sposób: if s[i] = t[j] then d[i, j] := d[i-1, j-1] // no operation required else d[i, j] := minimum (...
Dla zabawy próbuję stworzyć przeglądarkę z ramką dla DCPU-16 . Rozumiem, jak to zrobić wszystko oprócz ukrywania linii ukrytych w ramce drucianej. Wszystkie pytania tutaj na SO zakładają, że masz dostęp do OpenGL, niestety nie mam dostępu do niczego takiego w przypadku DCPU-16 (ani żadnego rodzaju...
Jak zbudować przykład DFA, który ma stanów, w których równoważny NFA ma n stanów. Oczywiście zestaw stanów DFA powinien zawierać wszystkie podzestawy zestawu stanów NFA, ale nie wiem jak zacząć. Jakieś sugestie, żeby postawić mnie na właściwej
W dowodzeniu twierdzenia o rozdzielczości zwykle przyjmuje się, że zmienne w różnych klauzulach są różne. To nie dzieje się automatycznie; do wdrożenia wymaga znacznego dodatkowego kodu i obliczeń. Biorąc to pod uwagę, szukam dla niego skrzynki testowej. Problem polega na tym, że we wszystkich...
Szukam specjalizacji z informatyki teoretycznej; szczególnie interesuje mnie teoria złożoności i teoria automatów probabilistycznych. Kiedy kończę rok, jakie zaawansowane kursy matematyczne (jak na przykład teoria Galois lub analiza harmoniczna) są przydatne do przejęcia kolejnych dwóch semestrów?...
Czy zaakceptowanie oznacza, że TM odczyta i rozpozna znak z komórki, z której obecnie czyta? I czy tak się dzieje, że TM zatrzymuje się, jeśli dane wejściowe są
Czytałem na Wikipedii, że zjednoczenie jest procesem rozwiązywania problemu satysfakcji. Jednocześnie wiem, że takie solwery nazywane są „solverami SAT” lub „solverami SMT”. Czy są to różne nazwy dla tej samej rzeczy? Jeśli powiesz, że się różnią, proszę wskazać wadę mojego leczenia....
Szukam szybkiego algorytmu dopasowywania ciągów typu k-mismatch. Biorąc pod uwagę ciąg wzorca P o długości m i ciąg tekstowy T o długości n, potrzebuję szybkiego algorytmu (czas liniowy), aby znaleźć wszystkie pozycje, w których P pasuje do podłańcucha T z co najwyżej k niedopasowań. Różni się to...
Byłem zdezorientowany podczas rozwiązywania następującego problemu (pytania 1–3). Pytanie D -ary sterty jest jak stos binarny, lecz (z wyjątkiem jednej z możliwych) węzły nie liść ma d dzieci zamiast 2 dzieci. Jak byś stanowią d -ary sterty w tablicy? Jaka jest wysokość d -ary sterty n...
Mam problem, który można sprowadzić do problemu przydziału. (W poprzednim pytaniu dowiedziałem się, jak to zrobić.) Co oznacza, że mamy zestaw ZAZAA agentów i zestaw zadań, a także funkcję kosztu . Musimy znaleźć zadanie, aby całkowity koszt był minimalny.c ( i , j )T.T.Tc ( i , j...