Jakie są kluczowe różnice między tymi trzema terminami: izomorfizm, automorfizm i homomorfizm w prostym języku laika i dlaczego robimy izomorfizm, automorfizm i
To mój pierwszy post po tym, jak od jakiegoś czasu jestem pasywnym użytkownikiem. Chciałbym zadać kilka pytań, jeśli mogę. Nie jestem matematykiem, ale moje pytanie dotyczy matematyki / informatyki. W szczególności problem P vs NP. Wiem, że jest to problem, którego elitarni specjaliści nie byli...
Wykonując rachunek psychiczny, możesz: Biorąc pod uwagę liczbę całkowitą k, zsumuj wszystkie cyfry (w podstawie 10), a jeśli wynikiem jest wielokrotność 3, to k jest wielokrotnością 3. Czy znasz algorytm działający podobnie, ale działający na cyfrach binarnych (bitach)? Najpierw...
Właśnie zacząłem czytać o teorii obliczeń. Jeśli porównamy, który ma większą moc (w przyjmowaniu ciągów), oba są takie same. Ale co z wydajnością? DFA będzie szybki w porównaniu do NFA, ponieważ ma tylko jedną przewagę wychodzącą i nie będzie dwuznaczności. Ale w przypadku NFA musimy sprawdzić...
Jestem w pewnym sensie nowy, ale bardzo zainteresowany dziedziną obliczeń i teorii złożoności, i chcę wyjaśnić moje rozumienie, w jaki sposób klasyfikować problemy i jak silnie problemy odnoszą się do maszyny używanej do ich rozwiązywania. Moje zrozumienie Standardowa maszyna Turinga - maszyna...
Załóżmy, że ma wykres o M ( G ) do (brak danych) zestawu doskonałych skojarzeń z G . Załóżmy, że ten zestaw nie jest pusty, to jak trudne jest jednorodne losowe pobieranie próbek z M ( G ) ? Co się stanie, jeśli nie mam nic przeciwko rozkładowi zbliżonemu do jednorodnego, ale niezupełnie...
Mam następujące pytanie, ale nie mam na to odpowiedzi. Byłbym wdzięczny, jeśli moja metoda jest poprawna: P: Podczas wyszukiwania wartości klucza 60 w drzewie wyszukiwania binarnego węzły zawierające wartości klucza 10, 20, 40, 50, 70, 80, 90 są przemieszczane, niekoniecznie w podanej kolejności....
Funkcja maksymalnych przesunięć bobra zajętego, , ma znane wartości dla n ≤ 4 . Czy istnieje jakiś podstawowy, strukturalny powód, dla którego jest nie do pomyślenia, abyśmy kiedykolwiek znaleźli S ( n ) dla n > 4 ? Czym tak różni się n = 4 niż n = 5 ? Lub n = 6 ? Gdzieś po drodze musi być jakaś...
Istnieje kosze The th bin zawierać kulki. Kulki ma kolory istnieją kulki koloru . Niech .i a i n a i i m = ∑ n i = 1 a innniiiaiaia_innnaiaia_iiiim=∑ni=1aim=∑i=1naim=\sum_{i=1}^n a_i Zamiana polega na wzięciu piłki z jednego kosza i zamianie z piłką z innego kosza. Chcemy minimalnej liczby zamian,...
Rozważmy następującą grę: jest kilku graczy i komputer. Każdy gracz wprowadza jedną dodatnią liczbę całkowitą i swoje imię (gracz nie zna liczb innych, tylko własne). Gdy wszyscy gracze wykonają ruchy, komputer generuje imię zwycięzcy - który podał najniższy unikalny numer. Jak myślisz, jaka jest...
Czy wyjście parsera musi być drzewem, czy może to być również ogólny wykres? Co więcej, czy istnieje jakiś język, który jest wiarygodny i używa ogólnej reprezentacji grafów zamiast drzew do ich
Czytałem o różnicach między serializacją a linearyzacją , które są kryteriami spójności dla replikowanych systemów, takich jak replikowane bazy danych. Nie wiem jednak, w jakich przypadkach konieczna byłaby linearyzowalność, nawet jeśli jest silniejsza niż serializowalność. Czy mógłbyś wymyślić...
Niech język będzie regularny.L⊆Σ∗L⊆Σ∗\mathcal{L} \subseteq \Sigma^* Rozkład na czynniki to maksymalna para zestawów słów z ( X , Y )LL\mathcal{L}(X,Y)(X,Y)(X,Y) X⋅Y⊆LX⋅Y⊆LX \cdot Y \subseteq \mathcal{L} X≠∅≠YX≠∅≠YX \neq \emptyset \neq Y , gdzie | .x ∈ X , y ∈ Y }X⋅Y={xyX⋅Y={xyX \cdot Y =...
Czy istnieje jakiś naturalny lub znaczący sposób na powiązanie lub połączenie grup matematycznych i języków formalnych CS lub jakieś inne podstawowe pojęcie CS, np. Maszyny Turinga? Szukam referencji / aplikacji. Zauważ jednak, że jestem świadomy związku między półgrupami a językami CS...
Próbuję zrozumieć, co należy rozumieć przez „deterministyczny” w wyrażeniach takich jak „deterministyczna gramatyka bezkontekstowa”. (W tej dziedzinie są bardziej deterministyczne „rzeczy”). Byłbym wdzięczny za przykład bardziej niż najbardziej wyszukane wyjaśnienie! Jeśli to możliwe. Moje główne...
Korzystanie z następującego rekurencyjnego algorytmu Fibonacciego: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) Jeśli wprowadzę cyfrę 5, aby znaleźć Fib (5), wiem, że to da wynik 5, ale jak zbadać złożoność tego algorytmu? Jak obliczyć wymagane...
Jaka jest złożoność MIN-2-XOR-SATMIN-2-XOR-SAT\text{MIN-2-XOR-SAT} i MAX-2-XOR-SATMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} ? Czy są w P? Czy są twarde NP? Aby sformalizować to dokładniej, pozwól Φ(x)=∧niCi,Φ(x)=∧jandoja,\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i, gdzie...
Szukam wydajnego algorytmu dla następującego problemu lub dowodu twardości NP. Niech będzie zbiorem, a A ⊆ P ( Σ ) zbiorem podzbiorów Σ . Znaleźć sekwencję wagowo ∈ Ď * o najmniejszej długości tak, że dla każdego L ∈ A , jest k ∈ N w taki sposób, { w k + I | 0 ≤ i < | L | } = L .ΣΣ\SigmaA ⊆ P(...
Czytałem wpis Wikipedii o złożoności Kołmogorowa ( dzięki temu pytaniu ), który stwierdza: Można wykazać, że złożoność Kołmogorowa dowolnego łańcucha nie może być większa niż kilka bajtów więcej niż długość samego łańcucha. Dlaczego miałbyś kiedykolwiek potrzebować czegoś więcej niż samego...
Programowanie funkcjonalne ma bardzo elegancki rachunek lambda i jego warianty jako teorię kopii zapasowej. Czy istnieje coś takiego dla OOP? Czym jest abstrakcja dla modelu