Informatyka

7

Mam prawdziwe dane, których używam do symulowanej gry karcianej. Interesują mnie tylko szeregi kart, a nie ich kolory. Jest to jednak standardowa talia 525252 kart, dlatego w talii są możliwe tylko 444 z każdej rangi. Talia jest dobrze tasowana dla każdej ręki, a następnie wysyłam całą talię do pliku. Tak …

19 data-compression

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 …

19 algorithm-analysis time-complexity intuition

2

Jak udowodnić, że mnożenia macierzy dwóch macierzy 2x2 nie można wykonać w mniej niż 7 multiplikacjach?

W mnożeniu macierzy Strassena stwierdzamy jeden dziwny (przynajmniej dla mnie) fakt, że mnożenie macierzy dwóch 2 x 2 wymaga mnożenia 7. Pytanie: Jak udowodnić, że niemożliwe jest pomnożenie dwóch macierzy 2 x 2 w 6 pomnożeniach? Należy pamiętać, że macierze są ponad liczbami całkowitymi.

19 algorithms complexity-theory lower-bounds

4

Złożoność czasowa algorytmu: czy ważne jest określenie podstawy logarytmu?

Ponieważ między podstawami logarytmów jest tylko stała, to czy nie jest po prostu dobrze pisać f(n)=Ω(logn)fa(n)=Ω(log⁡n)f(n) = \Omega(\log{n}) , w przeciwieństwie do Ω(log2n)Ω(log2)⁡n)\Omega(\log_2{n}) , czy cokolwiek to może być podstawa?

19 algorithms time-complexity

6

Czy zatrzymanie problemu jest obliczalne dla poszczególnych danych wejściowych / założeń

Z mojego rozumienia dowodu, że problemu zatrzymania nie można obliczyć, problemu tego nie da się obliczyć, ponieważ jeśli mamy program P (x), który oblicza, czy program x zatrzymuje się, czy nie, mamy paradoks, gdy P podaje się jako dane wejściowe do to samo P, mając: P (P), próbując zdecydować, czy …

19 halting-problem

1

Dlaczego programowanie funkcjonalne nie badało dynamicznych drzew?

Drzewa dynamiczne odgrywają ważną rolę w rozwiązywaniu problemów, takich jak przepływy sieciowe, wykresy dynamiczne, problemy kombinatoryczne („Drzewa dynamiczne w praktyce” Tarjana i Wernecka) oraz ostatnio łączone słowniki („Prosty słownik łączący” Adama Karczmarza), Przez drzewa dynamiczne odwołuję się do definicji podanej w dokumencie Sleator & Tarjan zatytułowanym „Struktura danych dla drzew …

19 data-structures trees functional-programming

1

Czy można zadecydować o równości języka dla gramatyk liniowych bezkontekstowych?

Rozważmy dwa gramatyk bezkontekstowych i i zadać następujące pytanie: Czy , czyli są dwa równoważne gramatyki?sol1sol1G_1sol2)sol2)G_2L ( G1) = L ( G2))L.(sol1)=L.(sol2))L(G_1) = L(G_2) Ogólnie problem ten jest nierozstrzygalny. Jednakże, jeśli zarówno i są liniowe lewej (lub prawej) Gramatyki liniowe, to problem jest rozstrzygalne, ponieważ obie opisują gramatyk regularnych języków.sol1sol1G_1sol2)sol2)G_2 …

19 formal-languages context-free formal-grammars

4

Czy dowód sprzeczności może działać bez prawa wykluczonego środka?

Niedawno myślałem o ważności dowodu sprzeczności. Przez kilka ostatnich dni czytałem o intuicyjnej logice i twierdzeniach Godela, aby sprawdzić, czy dostarczyłyby mi odpowiedzi na moje pytania. W tej chwili wciąż mam pytania (być może związane z nowym materiałem, który czytam) i liczyłem na kilka odpowiedzi ( OSTRZEŻENIE : masz zamiar …

19 logic first-order-logic propositional-logic incompleteness

3

Jaki jest najbardziej wydajny algorytm sortowania w stałej przestrzeni?

Szukam algorytmu sortowania dla tablic int, który nie przydziela żadnych bajtów innych niż rozmiar tablicy i jest ograniczony do dwóch instrukcji: SWAP: zamień następny indeks na bieżący; MOVE: przesuwa kursor do indeksu +1 lub -1; Oznacza to, że nie można zamieniać niesąsiadujących indeksów ani zamieniać indeksu 100po zamianie indeksu 10. …

19 algorithms sorting in-place

2

Zbiory podstawowe dla rachunku kombinatorycznego

Dobrze wiadomo, że kombinatory S i K tworzą zestaw podstawowy dla rachunku kombinatorycznego, w tym sensie, że wszystkie inne kombinatory można wyrazić za ich pomocą. Istnieje również podstawa Curry'ego B, C, K, W, która ma tę samą właściwość. Musi istnieć nieskończona liczba takich baz, ale nie znam żadnych innych. Wiem, …

19 lambda-calculus combinatory-logic

6

Dlaczego niezatwierdzone transakcje muszą być cofane w kolejności wstecznej?

Mam dziennik bazy danych, w którym niektóre transakcje wygrywają (są zatwierdzane przed awarią), a niektóre tracą (jeszcze nie zatwierdzone). W klasie nauczyliśmy się, że działania przegranych muszą zostać cofnięte. Czy jest jakiś powód, aby robić to wstecz? Czy ktoś może podać prosty przykład dziennika, w którym cofanie w przód dawałoby …

19 concurrency databases

12

Struktura danych lub algorytm do szybkiego znajdowania różnic między łańcuchami

Mam tablicę 100 000 ciągów o długości . Chcę porównać każdy ciąg z każdym innym, aby zobaczyć, czy dwa ciągi różnią się o 1 znak. W tej chwili, gdy dodam każdy ciąg do tablicy, sprawdzam go względem każdego łańcucha już w tablicy, który ma złożoność czasową .kkkn(n−1)2kn(n−1)2k\frac{n(n-1)}{2} k Czy istnieje …

19 algorithms data-structures program-optimization comparison

6

Czy każdy trudny problem NP jest obliczalny?

Czy wymagane jest, aby problem trudny do przeprowadzenia w NP był obliczalny? Nie sądzę, ale nie jestem pewien.

19 complexity-theory computability np-hard

5

Jak długo trwa rekurencja Collatz?

Mam następujący kod Python. def collatz(n): if n <= 1: return True elif (n%2==0): return collatz(n/2) else: return collatz(3*n+1) Jaki jest czas działania tego algorytmu? Próbować: Jeśli oznacza czas działania funkcji . Więc myślę, że mam { T ( n ) = 1 dla n ≤ 1 T ( n …

19 algorithm-analysis runtime-analysis recurrence-relation

1

Kto ukuł termin „uczenie maszynowe”?

Próbuję dowiedzieć się, kto stworzył termin „uczenie maszynowe”. Dodatkowe pytanie brzmi: skąd Arthur Samuel cytował określenie „uczenia maszynowego” w 1959 r. Jako: dziedzina nauki, która daje komputerom możliwość uczenia się bez wyraźnego programowania ? W Internecie można znaleźć wiele odniesień do tej definicji, ale nie udało mi się wyśledzić źródła. …

19 terminology reference-request machine-learning history