Informatyka reference-request

5

Istnieje wiele prób udowodnienia albo albo P ≠ N P , i oczywiście wiele osób myśli o tym pytaniu, mając pomysły na udowodnienie obu kierunków.P = N PP=NP\mathsf{P} = \mathsf{NP} P ≠ N PP≠NP\mathsf{P} \neq \mathsf{NP} Wiem, że istnieją metody, które okazały się nieskuteczne, i prawdopodobnie jest więcej takich, które …

96 complexity-theory reference-request history p-vs-np reference-question

4

Co to jest rekurencja ogona?

Znam ogólną koncepcję rekurencji. Zetknąłem się z koncepcją rekurencji ogona podczas studiowania algorytmu Quicksort. W tym filmie z algorytmem szybkiego sortowania z MIT o godzinie 18:30 profesor mówi, że jest to algorytm rekurencyjny ogona. Nie jest dla mnie jasne, co tak naprawdę oznacza rekurencja ogona. Czy ktoś może wyjaśnić tę …

52 algorithms reference-request recursion

6

Radzenie sobie z trudnością: problemy z NP-zupełnością

Załóżmy, że jestem programistą i mam problem NP-zupełny, który muszę rozwiązać. Jakie są dostępne metody radzenia sobie z problemami NPC? Czy istnieje ankieta lub coś podobnego na ten temat?

43 algorithms reference-request np-complete efficiency reference-question

6

Jakie są zastosowania grup, monoidów i pierścieni w obliczeniach baz danych?

Dlaczego firma taka jak Twitter byłaby zainteresowana koncepcjami algebraicznymi, takimi jak grupy, monoidy i pierścienie? Zobacz ich repozytorium na github: twitter / algebird . Mogłem tylko znaleźć: Implementacje Monoidów dla interesujących algorytmów aproksymacyjnych, takich jak filtr Bloom , HyperLogLog i CountMinSketch . Pozwalają ci myśleć o tych wyrafinowanych operacjach, takich …

38 reference-request discrete-mathematics database-theory applied-theory group-theory

3

W najgorszym przypadku w miejscu stabilny rodzaj?

Mam problem ze znalezieniem dobrych zasobów, które dają najgorszy przypadek w miejscu stabilnego algorytmu sortowania. Czy ktoś wie o dobrych zasobach?O ( n lnn )O(nln⁡n)O(n \ln n) Tylko przypomnienie, w miejscu oznacza, że wykorzystuje przekazaną tablicę, a algorytm sortujący może używać tylko stałej dodatkowej przestrzeni. Stabilny oznacza, że elementy z …

35 algorithms reference-request sorting in-place

2

Kwantowy rachunek lambda

Klasycznie istnieją 3 popularne sposoby myślenia o obliczeniach: maszyna Turinga, obwody i rachunek lambda (używam tego jako haczyka dla większości widoków funkcjonalnych). Wszystkie 3 były owocnymi sposobami myślenia o różnych typach problemów, a różne dziedziny stosują różne formuły z tego powodu. Kiedy jednak pracuję z obliczeniami kwantowymi, zawsze myślę tylko …

35 lambda-calculus quantum-computing reference-request computation-models

2

w sprawie „O okrucieństwie faktycznego nauczania informatyki”

Dijkstra w swoim eseju O okrucieństwie prawdziwego nauczania informatyki przedstawia następującą propozycję wprowadzenia kursu programowania: Z jednej strony uczymy czegoś, co wygląda na rachunek predykatu, ale robimy to zupełnie inaczej niż filozofowie. Aby wyszkolić początkującego programistę w zakresie manipulowania nieinterpretowanymi formułami, uczymy go bardziej jako algebry boolowskiej, zapoznając studenta ze …

33 reference-request programming-languages education didactics

1

Których algorytmów uczenia maszynowego można użyć do prognoz szeregów czasowych?

Obecnie bawię się prognozami szeregów czasowych (szczególnie na rynku Forex). Widziałem kilka artykułów naukowych na temat sieci stanów echa, które są stosowane do prognoz Forex. Czy istnieją inne dobre algorytmy uczenia maszynowego do tego celu? Interesujące byłoby również wydobycie „rentownych” wzorów z szeregów czasowych.

28 reference-request machine-learning artificial-intelligence

2

Co oznacza „prawdziwa współbieżność”?

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

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

1

Czy istnieje zapisany rachunek SKI?

Większość z nas zna zgodność między logiką kombinacyjną a rachunkiem lambda . Ale nigdy nie widziałem (może nie spojrzałem wystarczająco głęboko) odpowiednika „typowanych kombinatorów”, odpowiadającego po prostu typowanemu rachunku lambda. Czy coś takiego istnieje? Gdzie można znaleźć informacje na ten temat?

26 reference-request logic lambda-calculus type-theory combinatory-logic

5

Czy jest filtr przeciw Bloomowi?

Filtr Bloom pozwala efektywnie śledzić, czy różne wartości zostały już napotkał podczas przetwarzania. Gdy jest wiele elementów danych, filtr Bloom może spowodować znaczne oszczędności pamięci w tabeli skrótów. Główną cechą filtra Bloom, który dzieli z tabelą skrótów, jest to, że zawsze mówi „nie nowy”, jeśli element nie jest nowy, ale …

25 reference-request data-structures hash bloom-filters dictionaries

2

Czy istnieje czasem skuteczny algorytm do rozwiązania #SAT?

Niech będzie formułą logiczną składającą się ze zwykłych operatorów AND, OR i NOT oraz niektórych zmiennych. Chciałbym policzyć liczbę spełniającą zadania dla . To znaczy, chcę znaleźć liczbę różnych przypisań wartości prawdy do zmiennych dla których przyjmuje wartość prawdziwą. Na przykład formuła ma trzy zadowalające przypisania; ma cztery. To jest …

24 complexity-theory reference-request satisfiability

7

Rozpocząć naukę o teorii systemów rozproszonych?

Jaki jest najlepszy sposób, aby ktokolwiek mógł zrobić dobre wprowadzenie do teorii systemu rozproszonego, wszelkich książek lub referencji oraz tematów, które powinny zostać omówione w pierwszej kolejności, a także wymagania, aby rozpocząć naukę w tym temacie.

24 reference-request education distributed-systems

1

Rozróżnij procedurę decyzyjną w porównaniu do solvera SMT vs provera twierdzeń vs solvera z ograniczeniami

Te terminologie mylą mnie. Jak rozumiem Solver SAT: decyduje o spełnianiu logiki zdań (za pomocą DPLL lub wyszukiwania lokalnego). Procedura decyzyjna to procedura decydująca o spełnieniu pewnej rozstrzygalnej teorii pierwszego rzędu. Solver SMT to solver SAT + procedura decyzyjna. Przysłowie twierdzące wskazuje na coś takiego jak logika dynamiczna, np. Narzędzie …

24 algorithms terminology reference-request decision-problem

Pytania otagowane jako reference-request