Pytania wymagające literatury na temat konkretnych, wąskich zagadnień.
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...
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...
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
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...
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(nlnn)O(n \ln n) Tylko przypomnienie, w miejscu oznacza, że wykorzystuje przekazaną tablicę, a algorytm sortujący może używać tylko...
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...
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ę...
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”...
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 ∑ i = 1 P i ( n ) λ n i , gdzie P i...
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ą...
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...
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...
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...
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...
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
W skrócie: w jaki sposób kategoryzowane są systemy typów w kontekście akademickim; w szczególności, gdzie mogę znaleźć renomowane źródła, które wyraźnie rozróżniają różne systemy typów? W pewnym sensie trudność związana z tym pytaniem nie polega na tym, że nie mogę znaleźć odpowiedzi, ale raczej...
Przy projektowaniu algorytmów często stosuje się następujące techniki: Programowanie dynamiczne Chciwa strategia Dziel i rządź Podczas gdy w przypadku dwóch pierwszych metod istnieją dobrze znane podstawy teoretyczne, a mianowicie zasada optymalności Bellmana i teoria matroidów (odpowiednio...
Jaka jest dobra książka informacyjna dla początkujących dla młodego dorosłego, powiedzmy, 15-latka? Chcę zacząć w CS, ale nie mam pojęcia, od czego zacząć. Mam ograniczone doświadczenie w
Skończyłem większość materiału w książce Cormen's Intro to Algorytmy i szukam książki o algorytmach, która obejmowałaby materiał poza książką Cormana. Czy są jakieś rekomendacje? UWAGA: Zapytałem o to przy przepełnieniu stosu, ale nie byłem zbyt zadowolony z odpowiedzi. UWAGA: Patrząc na...
Udoskonalenie partycji to technika, w której zaczynasz od skończonego zestawu obiektów i stopniowo dzielisz zestaw. Niektóre problemy, takie jak minimalizacja DFA, można rozwiązać dość skutecznie za pomocą zawężania partycji. Nie znam żadnych innych problemów, które zwykle rozwiązuje się za pomocą...