Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

2
Pokoloruj drzewo binarne, aby było czerwono-czarnym drzewem
Częstym pytaniem w rozmowie kwalifikacyjnej jest podanie algorytmu określającego, czy dane drzewo binarne ma zrównoważoną wysokość (definicja drzewa AVL). Zastanawiałem się, czy możemy zrobić coś podobnego z czerwono-czarnymi drzewami. Biorąc pod uwagę dowolne bezbarwne drzewo binarne (z węzłami NULL), czy istnieje „szybki” algorytm, który może określić, czy możemy pokolorować (i …
2
Gęsty NP pełny język oznacza P = NP
Mówimy, że język jest gęsty, jeśli istnieje wielomian taki, że dla wszystkichInnymi słowy, dla dowolnej długości istnieje tylko wielomianowo wiele słów o długości , które nie są wJ⊆Σ∗jot⊆Σ∗J \subseteq \Sigma^{*}ppp|Jc∩Σn|≤p(n)|jotdo∩Σn|≤p(n) |J^c \cap \Sigma^n| \leq p(n)n∈N.n∈N..n \in \mathbb{N}.nnnnnnJ.jot.J. Problem, który obecnie badam, wymaga przedstawienia następujących informacji Jeśli istnieje gęsty język , …
1
Ciekawa przestrzeń metryczna związana z maszynami Turinga
W tym pytaniu rozważamy tylko maszyny Turinga, które zatrzymują się na wszystkich wejściach. Jeśli to przez oznaczamy maszynę Turinga, której kod tok∈Nk∈Nk \in \mathbb{N}TkTkT_kkkk . Rozważ następującą funkcję s(x,y)=min{k∣|L(Tk)∩{x,y}|=1}s(x,y)=min{k∣|L(Tk)∩{x,y}|=1}s(x,y) = \min\{k \mid |L(T_k) \cap \{x,y\}| = 1\} Innymi słowy, jest kodem najmniejszej maszyny Turinga, która rozpoznaje dokładnie jeden z ciągówMożemy …
1
Uniwersalna symulacja maszyn Turinga
Niech będzie stałą funkcją konstruowaną w czasie.fff Klasyczny uniwersalny wynik symulacji dla TM (Hennie i Stearns, 1966) stwierdza, że ​​istnieje TM z dwiema taśmami, takaUUU opis TM i⟨M⟩⟨M⟩\langle M \rangle ciąg wejściowy ,xxx uruchamia kroki i zwraca odpowiedź na . I może być dowolną funkcją w .g(|x|)g(|x|)g(|x|)MMMxxxgggω(f(n)lgf(n))ω(f(n)lg⁡f(n))\omega(f(n)\lg f(n)) Moje pytania …
2
Czy sieci neuronowe muszą zawsze się zbieżne?
Wprowadzenie Krok pierwszy Napisałem standardową sieć neuronową z propozycją wsteczną i aby ją przetestować, zdecydowałem się na mapowanie XOR. Jest to sieć 2-2-1 (z funkcją aktywacji tanh) X1 M1 O1 X2 M2 B1 B2 Do celów testowych ręcznie skonfigurowałem górny środkowy neuron (M1), aby był bramką AND, a dolny neuron …
1
Brutalna siła złożoności algorytmu triangulacji Delaunaya
W książce „Geometria obliczeniowa: algorytmy i zastosowania” autorstwa Mark de Berg i wsp. Istnieje bardzo prosty algorytm brutalnej siły do ​​obliczania triangulacji Delaunaya. Algorytm wykorzystuje pojęcie niedozwolonych krawędzi - krawędzi, które mogą nie pojawić się w prawidłowej triangulacji Delaunaya i muszą zostać zastąpione innymi krawędziami. Na każdym kroku algorytm po …
1
Algorytm politime i polyspace do wyznaczania wiodącego przecięcia n dyskretnych funkcji monotonicznych
Some frontmatter: Jestem informatykiem rekreacyjnym i zatrudnionym inżynierem oprogramowania. Więc przepraszam, jeśli to podpowiedź wydaje się być trochę poza lewym polem - rutynowo gram z matematycznymi symulacjami i otwieram problemy, gdy nie mam nic lepszego do roboty. Podczas zabawy hipotezą Riemanna ustaliłem, że pierwszą lukę można zredukować do relacji powtarzalności …
2
Środowisko uruchomieniowe optymalnego algorytmu chciwości
|P|=n|P|=n|P| = nkkkkkknnnC={c1,c2,…,ck}C={c1,c2,…,ck}C = \{ c_1,c_2,\ldots,c_k\}kkkDcost(C)=maximinjD(pi,cj)cost(C)=maximinjD(pi,cj)\text{cost}(C) = \max_i \min_j D(p_i, c_j)DDDoznacza odległość euklidesową między punktem wejściowym a punktem środkowym . Każdy punkt przypisuje się do najbliższego centrum gromady grupującego wierzchołki w różnych skupisk.c j kpipip_icjcjc_jkkk Problem znany jest jako (dyskretny) problem klastrowania i jest to -hard. Można to pokazać z …
1
Czy asymptotyczne dolne granice są istotne dla kryptografii?
Ogólnie uważa się, że asymptotyczna dolna granica, taka jak twardość wykładnicza, sugeruje, że problem jest „z natury trudny”. Uważa się, że szyfrowanie „z natury trudne do złamania” jest bezpieczne. Jednak asymptotyczna dolna granica nie wyklucza możliwości, że ogromna, ale skończona klasa wystąpień problemów jest łatwa (np. Wszystkie wystąpienia o rozmiarze …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.