Informatyka counting

5

Moja matka bierze udział w kursie internetowym, aby zostać bibliotekarką, w tym kursie obejmują wyszukiwania boolowskie, dzięki czemu mogą skutecznie przeszukiwać bazy danych, jednak pojawiło się pytanie brzmiące mniej więcej tak: Wyszukiwanie „x OR y” spowoduje 105 000 trafień, podczas gdy wyszukiwanie tylko x da 80 000 trafień, a wyszukiwanie …

29 sets counting

2

Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?

Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void określa, że funkcja …

28 type-theory c logic modal-logic coq equality coinduction artificial-intelligence computer-architecture compilers asymptotics formal-languages asymptotics landau-notation asymptotics turing-machines optimization decision-problem rice-theorem algorithms arithmetic floating-point automata finite-automata data-structures search-trees balanced-search-trees complexity-theory asymptotics amortized-analysis complexity-theory graphs np-complete reductions np-hard algorithms string-metrics computability artificial-intelligence halting-problem turing-machines computation-models graph-theory terminology complexity-theory decision-problem polynomial-time algorithms algorithm-analysis optimization runtime-analysis loops turing-machines computation-models recurrence-relation master-theorem complexity-theory asymptotics parallel-computing landau-notation terminology optimization decision-problem complexity-theory polynomial-time counting coding-theory permutations encoding-scheme error-correcting-codes machine-learning natural-language-processing algorithms graphs social-networks network-analysis relational-algebra constraint-satisfaction polymorphisms algorithms graphs trees

1

Dlaczego wariant liczenia problemu trudnej decyzji nie jest automatycznie trudny?

Dobrze wiadomo, że 2-SAT znajduje się w P. Jednak wydaje się dość interesujące, że zliczanie liczby rozwiązań dla danej formuły 2-SAT, tj. # 2-SAT jest # P-trudne. Oznacza to, że mamy przykład problemu, dla którego decyzja jest łatwa, ale liczenie jest trudne. Ale rozważ arbitralny problem NP-zupełny (powiedzmy 3-COL). Czy …

14 complexity-theory counting

2

Czy #

Niech będzie jakimś problemem liczenia, o którym wiadomo, że to # -Complete .ΠΠ\PiP.P.P Czy to oznacza, że jest -hard (czyli nie PTA dla istnieje problem chyba że )?ΠΠ\PiA P.XZAP.XAPXP.= NP.P.=N.P.P=NP

11 complexity-theory complexity-classes approximation counting

2

Liczenie wysp w macierzach boolowskich

Biorąc pod uwagę n×mn×mn \times m Macierz boolowska XX\mathrm X, pozwolić 000 pozycje reprezentują morze i 111wpisy reprezentują ziemię. Zdefiniuj wyspę jako sąsiadującą pionowo lub poziomo (ale nie po przekątnej)111 wpisy. Pierwotne pytanie polegało na zliczeniu liczby wysp w danej matrycy. Autor opisał rozwiązanie rekurencyjne (O(nm)O(nm)\mathcal{O}(nm) pamięć). Ale bezskutecznie próbowałem …

9 algorithms matrices counting streaming-algorithm

Pytania otagowane jako counting