Informatyka

2

Często słyszę wyrażenia takie jak „semantyka prawdziwej współbieżności” i „równoważność prawdziwej współbieżności” bez żadnych odniesień. Co oznaczają te terminy i dlaczego są ważne? Jakie są przykłady prawdziwych odpowiedników współbieżności i jaka jest ich potrzeba? Np. W jakich przypadkach mają one większe zastosowanie niż więcej standardowych równoważników (bisimulacja, równoważność śladowa itp.)?

28 terminology reference-request concurrency

3

Dlaczego wybór sortuje się szybciej niż sortowanie bąbelkowe?

Na Wikipedii napisano, że „... sortowanie selekcji prawie zawsze przewyższa sortowanie bąbelkowe i sortowanie gnomów”. Czy ktoś może mi wyjaśnić, dlaczego sortowanie jest uważane za szybsze niż sortowanie bąbelkowe, mimo że oba mają: Złożoność najgorszego przypadku :O(n2)\mathcal O(n^2) Liczba porównań : O(n2)\mathcal O(n^2) Najlepsza złożoność czasu sprawy : Sortowanie bąbelkowe:O(n)\mathcal …

28 algorithms runtime-analysis efficiency sorting

1

Asymptotyka liczby słów w języku regularnym o zadanej długości

Dla języka regularnego , niech c n ( L ) będzie liczbą słów w L o długości n . Stosując kanoniczną postać Jordana (zastosowaną do niezanotowanej macierzy przejścia dla niektórych DFA dla L ), można wykazać, że dla wystarczająco dużych n , c n ( L ) = k ∑ …

28 formal-languages reference-request regular-languages asymptotics combinatorics

4

Jaka jest dokładnie różnica między uczeniem nadzorowanym i bez nadzoru?

Próbuję zrozumieć metody grupowania. Co myślę, że rozumiem: W uczeniu nadzorowanym dane kategorii / etykiet są przypisane przed obliczeniem. Tak więc etykiety, klasy lub kategorie są używane do „uczenia się” parametrów, które są naprawdę znaczące dla tych klastrów. W uczeniu bez nadzoru zbiory danych są przypisywane do segmentów, bez znanych …

28 machine-learning data-mining clustering

1

Czy istnieje struktura danych „ciąg znaków”, która obsługuje te operacje na łańcuchach?

Szukam struktury danych, która przechowuje zestaw ciągów znaków nad zestawem znaków , zdolną do wykonywania następujących operacji. Oznaczmy D ( S ) , jak w strukturze danych przechowującej zestaw łańcuchy S .ΣΣ\SigmaD(S)D(S)\mathcal{D}(S)SSS Add-Prefix-Setna : biorąc pod uwagę pewien zestaw T (prawdopodobnie pustych) ciągów, których rozmiar jest ograniczony stałą, a których …

28 data-structures time-complexity strings stacks

4

Czyste, intuicyjne wyprowadzenie kombinatora stałoprzecinkowego (kombinator Y)?

Kombinator stałoprzecinkowy FIX (znany również jako kombinator Y) w (niepoprawnym) rachunku lambda ( ) jest zdefiniowany jako:λλ\lambda FIX≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. x~x~y)) Rozumiem jego cel i doskonale mogę śledzić wykonanie …

28 computability logic programming-languages lambda-calculus combinatory-logic

1

Które kombinacje sekwencjonowania przed, po i w kolejności są wyjątkowe?

Znamy się na zamówieniu, post L(x) => [x] post N(x,l,r) => (post l) ++ (post r) ++ [x] i w przedsprzedaży pre L(x) => [x] pre N(x,l,r) => [x] ++ (pre l) ++ (pre r) oraz w kolejności przechodzenia lub. sekwencjonowanie. in L(x) => [x] in N(x,l,r) => (in l) …

28 algorithms binary-trees

4

Jak znaleźć supergwiazdę w czasie liniowym?

Rozważ skierowane wykresy. Nazywamy węzeł supergwiazdą wtedy i tylko wtedy, gdy nie można do niego dotrzeć z żadnego innego węzła, ale wszystkie inne węzły mają krawędź do . Formalnie:vvvv vvv \qquad \displaystyle v superstar :⟺outdeg(v)=0∧indeg(v)=n−1 superstar :⟺outdeg(v)=0∧indeg(v)=n−1 \text{ superstar } :\Longleftrightarrow \mathrm{outdeg}(v) = 0 \land \mathrm{indeg}(v) = n-1 z liczba …

28 algorithms graphs

3

Pomiar trudności wystąpień SAT

Biorąc pod uwagę instancję SAT, chciałbym móc oszacować, jak trudno będzie rozwiązać instancję. Jednym ze sposobów jest uruchamianie istniejących solverów, ale ten rodzaj pokonuje cel oszacowania trudności. Drugi sposób może polegać na szukaniu stosunku klauzul do zmiennych, jak ma to miejsce w przypadku przejść fazowych w losowo-SAT, ale jestem pewien, …

28 complexity-theory satisfiability heuristics

2

Liczenie drzew binarnych

(Jestem studentem z pewnym doświadczeniem matematycznym i chciałbym wiedzieć, jak policzyć liczbę określonego rodzaju drzew binarnych). Patrząc na stronę Wikipedii dotyczącą drzew binarnych , zauważyłem to twierdzenie, że liczba zakorzenionych drzew binarnych o rozmiarze będzie katalońską : C_n = \ dfrac {1} {n + 1} {2n \ wybierz n}nnnCn=1n+1(2nn)Cn=1n+1(2nn)C_n = …

28 combinatorics binary-trees discrete-mathematics

6

Generowanie kombinacji z zestawu par bez powtarzania elementów

Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n). Jeśli więc n wynosi 4, to mam następujące pary: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita …

28 algorithms graphics data-structures computational-geometry operating-systems process-scheduling algorithms sorting database-theory relational-algebra finite-model-theory logic automata linear-temporal-logic buchi-automata complexity-theory np-complete decision-problem machine-learning algorithms pattern-recognition logic formal-languages formal-grammars context-free

1

Różnica między semantyką operacyjną małego i dużego kroku

Jaka jest podstawowa różnica między semantyką operacyjną małego i dużego kroku? Trudno mi zrozumieć, co to jest i motywację do posiadania tych dwóch.

28 semantics operational-semantics small-step-semantics

7

Algorytm znajdowania średnicy drzewa za pomocą BFS / DFS. Dlaczego to działa?

To łącze zapewnia algorytm znajdowania średnicy drzewa bezkierunkowego za pomocą BFS / DFS . Zreasumowanie: Uruchom BFS na dowolnym węźle na wykresie, pamiętając węzeł wykryty jako ostatni. Uruchom BFS, pamiętając ostatnio wykryty węzeł v. d (u, v) to średnica drzewa. Dlaczego to działa? Strona 2 tego zawiera uzasadnienie, ale jest …

28 algorithms graphs search-algorithms trees graph-traversal

7

Jakie są najprostsze przykłady programów, których nie wiemy, czy się kończą?

Problem zatrzymania mówi, że nie ma algorytmu, który określi, czy dany program się zatrzyma. W rezultacie powinny istnieć programy, o których nie możemy powiedzieć, czy się kończą, czy nie. Jakie są najprostsze (najmniejsze) znane przykłady takich programów?

27 computability turing-machines halting-problem

2

Jak skonstruować redukcje między problemami, aby udowodnić, że problem jest NP-kompletny?

Biorę kurs złożoności i mam problem z wymyśleniem redukcji między problemami NPC. Jak znaleźć redukcje między problemami? Czy istnieje ogólna sztuczka, której mogę użyć? Jak podejść do problemu, który wymaga ode mnie udowodnienia, że jest nim NPC?

27 complexity-theory np-complete proof-techniques reductions