Pytania otagowane jako intuition

Pytania, które proszą o pomoc w budowaniu intuicji dla formalnych lub złożonych koncepcji.

2
Dlaczego uważamy, że PSPACE ≠ EXPTIME?
Mam problem z intuicyjnym zrozumieniem, dlaczego ogólnie uważa się, że PSPACE różni się od EXPTIME. Jeśli PSPACE jest zbiorem problemów możliwych do rozwiązania w wielomianu kosmicznym w wielkości wejściowej fa( n )f(n)f(n) , to w jaki sposób może istnieć klasa problemów, które doświadczają większego wybuchu czasu wykładniczego i nie wykorzystują …
7
Czy istnieje bardziej intuicyjny dowód nierozstrzygalności problemu zatrzymania niż przekątna?
Rozumiem dowód nierozstrzygalności problemu zatrzymania (podany na przykład w podręczniku Papadimitriou), oparty na przekątnej. Chociaż dowód jest przekonujący (rozumiem każdy jego krok), nie jest dla mnie intuicyjny w tym sensie, że nie widzę, jak ktoś by go wyprowadził, zaczynając od samego problemu. W książce dowód wygląda następująco: „załóżmy, że MHMHM_H …
2
Ogólna zasada, aby wiedzieć, czy problem może być NP-zupełny
To pytanie zostało zainspirowane komentarzem na StackOverflow . Oprócz znajomości problemów NP-zupełnych z książki Garey Johnson i wielu innych; czy istnieje ogólna zasada, aby wiedzieć, czy problem wygląda jak NP-zupełny? Nie szukam czegoś rygorystycznego, ale czegoś, co działa w większości przypadków. Oczywiście za każdym razem, gdy musimy udowodnić, że problem …
7
Jakie są cechy algorytmu złożoności czasowej
Czasami łatwo jest określić złożoność czasową algorytmu, dokładnie go badając. Algorytmy z dwiema zagnieżdżonymi pętlami są oczywiście . Algorytmy zbadania wszystkich możliwych kombinacji grup dwie wartości są oczywiście .N.NN N 2 N.N.2)N2N^2N.NN2)N.2N2^N Nie wiem jednak, jak „rozpoznać” algorytm o złożoności . Przykładem jest rekurencyjna implementacja scalania. Jakie są wspólne cechy …
4
Strategie utknięcia w zrozumieniu TCS
Jestem studentem kończącym kurs teorii teorii i mam poważne problemy z tworzeniem treści, gdy tylko o to poproszę. Potrafię śledzić podręcznik (Wstęp do teorii obliczeń Michaela Sipsera) i wykłady; jednak kiedy poproszono mnie o udowodnienie czegoś lub sformułowanie formalnego opisu konkretnej bazy TM, po prostu dusiłem się. Co mogę zrobić …
2
Co zyskujemy, mając „typy zależne”?
Myślałem, że dobrze rozumiem pisanie zależne (DT), ale odpowiedź na to pytanie: /cstheory/30651/why-was-there-a-need-for-martin-l%C3% Teoria typu B6f do tworzenia-intuicyjnego typu kazała mi myśleć inaczej. Po przeczytaniu DT i próbie zrozumienia, czym one są, zastanawiam się, co zyskujemy dzięki temu pojęciu DT? Wydają się być bardziej elastyczne i wydajne niż zwykły rachunek …
3
Dlaczego większe rozmiary wejściowe oznaczają trudniejsze instancje?
Poniżej załóżmy, że pracujemy z maszyną Turinga z nieskończoną taśmą. Wyjaśniając komuś pojęcie złożoności czasowej i dlaczego mierzy się ją względem wielkości wejściowej instancji, natknąłem się na następujące twierdzenie: [..] Na przykład naturalne jest, że potrzeba więcej kroków, aby pomnożyć dwie liczby całkowite przez 100 000 bitów, niż, powiedzmy, pomnożenie …
1
Wnioskowanie o rodzajach uściślenia
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if …
11 programming-languages  logic  type-theory  type-inference  machine-learning  data-mining  clustering  order-theory  reference-request  information-theory  entropy  algorithms  algorithm-analysis  space-complexity  lower-bounds  formal-languages  computability  formal-grammars  context-free  parsing  complexity-theory  time-complexity  terminology  turing-machines  nondeterminism  programming-languages  semantics  operational-semantics  complexity-theory  time-complexity  complexity-theory  reference-request  turing-machines  machine-models  simulation  graphs  probability-theory  data-structures  terminology  distributed-systems  hash-tables  history  terminology  programming-languages  meta-programming  terminology  formal-grammars  compilers  algorithms  search-algorithms  formal-languages  regular-languages  complexity-theory  satisfiability  sat-solvers  factoring  algorithms  randomized-algorithms  streaming-algorithm  in-place  algorithms  numerical-analysis  regular-languages  automata  finite-automata  regular-expressions  algorithms  data-structures  efficiency  coding-theory  algorithms  graph-theory  reference-request  education  books  formal-languages  context-free  proof-techniques  algorithms  graph-theory  greedy-algorithms  matroids  complexity-theory  graph-theory  np-complete  intuition  complexity-theory  np-complete  traveling-salesman  algorithms  graphs  probabilistic-algorithms  weighted-graphs  data-structures  time-complexity  priority-queues  computability  turing-machines  automata  pushdown-automata  algorithms  graphs  binary-trees  algorithms  algorithm-analysis  spanning-trees  terminology  asymptotics  landau-notation  algorithms  graph-theory  network-flow  terminology  computability  undecidability  rice-theorem  algorithms  data-structures  computational-geometry 
1
Turing Recognizable => enumerable
Dostaję dowód przejścia z modułu wyliczającego do maszyny Turinga (kontynuuj działanie modułu wyliczającego i zobacz, czy pasuje on do danych wejściowych), ale nie widzę, jak działa inny sposób. Zgodnie z moimi notatkami i książką (Wprowadzenie do teorii obliczeń - Sipser), aby pobrać moduł wyliczający Turinga z maszyny Turinga, w zasadzie …
3
Intuicja splotu w przetwarzaniu obrazu
Przeczytałem wiele dokumentów na temat splotu w przetwarzaniu obrazu i większość z nich mówi o jego formule, kilku dodatkowych parametrach. Nikt nie wyjaśnia intuicji i prawdziwego znaczenia robienia splotu na obrazie. Na przykład intuicja wyprowadzania na wykresie sprawia, że ​​jest on na przykład bardziej liniowy. Myślę, że szybkie podsumowanie definicji …
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.