Informatyka

9

Czy są jakieś problemy, które stają się łatwiejsze wraz ze wzrostem wielkości?

To może być śmieszne pytanie, ale czy można mieć problem, który staje się łatwiejszy w miarę wzrostu wielkości nakładów? Wątpię, żeby jakieś praktyczne problemy były takie, ale może uda nam się wynaleźć zdegenerowany problem, który ma tę właściwość. Na przykład być może zaczyna się „rozwiązywać”, gdy robi się większy lub …

62 algorithms asymptotics

6

Dlaczego nie łączymy generatorów liczb losowych?

Istnieje wiele aplikacji, w których używany jest pseudolosowy generator liczb losowych. Dlatego ludzie wdrażają taki, który ich zdaniem jest świetny, aby później stwierdzić, że jest wadliwy. Coś takiego stało się ostatnio z generatorem liczb losowych Javascript. RandU też dużo wcześniej. Istnieją również problemy z niewłaściwym początkowym zaszczepieniem czegoś takiego jak …

60 pseudo-random-generators random-number-generator

10

Moc obliczeniowa człowieka: czy ludzie mogą rozwiązać problem zatrzymania na maszynach Turinga?

Wiemy, że problem zatrzymania (na maszynach Turinga) jest nierozstrzygalny dla maszyn Turinga. Czy są jakieś badania nad tym, jak dobrze ludzki umysł może poradzić sobie z tym problemem, być może wspomagane przez maszyny Turinga lub komputery ogólnego przeznaczenia? Uwaga : Oczywiście, w ścisłym tego słowa znaczeniu, zawsze możesz powiedzieć „nie”, …

60 computability turing-machines halting-problem human-computing

6

Przetwarzanie rozproszone a równoległe

Często słyszę ludzi mówiących o obliczeniach równoległych i obliczeniach rozproszonych , ale mam wrażenie, że nie ma wyraźnej granicy między tymi dwoma, a ludzie dość łatwo mylą to, podczas gdy uważam, że jest zupełnie inaczej: Obliczenia równoległe są ściślej powiązane z wielowątkowością lub tym, jak w pełni wykorzystać pojedynczy procesor. …

60 terminology distributed-systems parallel-computing

5

Czy zero jest dozwolone jako waga krawędzi na wykresie ważonym?

Próbuję napisać skrypt, który generuje losowe wykresy i muszę wiedzieć, czy krawędź na wykresie ważonym może mieć wartość 0. właściwie to ma sens, że 0 może być użyte jako waga krawędzi, ale pracowałem z wykresami w ciągu ostatnich kilku dni i nigdy nie widziałem takiego przykładu.

60 algorithms graph-theory graphs weighted-graphs

8

Algorytmiczna intuicja dla złożoności logarytmicznej

Wydaje mi się, że mam rozsądne pojęcie o złożoności takiej jak , Θ ( n ) i Θ ( n 2 ) .O(1)O(1)\mathcal{O}(1)Θ(n)Θ(n)\Theta(n)Θ(n2)Θ(n2)\Theta(n^2) Jeśli chodzi o listę, to ciągłe wyszukiwanie, więc po prostu dostaje się na czele listy. Θ ( n ) , gdzie będę chodzić całą listę, a Θ …

59 algorithms complexity-theory time-complexity intuition

3

Ekspresowe operacje logiczne typu boolowskiego w programowaniu liniowym całkowitym zero-jeden (ILP)

Mam całkowity program liniowy (ILP) z niektórymi zmiennymi które mają reprezentować wartości boolowskie. Wartości muszą być liczbami całkowitymi i zawierać 0 lub 1 ( ).xixix_ixixix_i0≤xi≤10≤xi≤10 \le x_i \le 1 Chcę wyrazić operacje boolowskie na tych zmiennych o wartości 0/1, używając ograniczeń liniowych. Jak mogę to zrobić? Mówiąc dokładniej, chcę ustawić …

58 linear-programming integer-programming

3

Typy zależne a typy wyrafinowania

Czy ktoś mógłby wyjaśnić różnicę między typami zależnymi a typami wyrafinowania? W moim rozumieniu typ uściślenia zawiera wszystkie wartości typu spełniającego predykat. Czy istnieje cecha typów zależnych, która je odróżnia? Jeśli to pomoże, natknąłem się na typy rafinowane za pośrednictwem projektu Liquid Haskell, a typy zależne za pośrednictwem Coq i …

57 terminology programming-languages type-theory functional-programming dependent-types

4

Dlaczego najlepiej używać liczby pierwszej jako modu w funkcji skrótu?

Jeśli mam listę kluczowych wartości od 1 do 100 i chcę je uporządkować w szeregu 11 segmentów, nauczono mnie tworzyć funkcję mod H=kmod 11H=kmod 11 H = k \bmod \ 11 Teraz wszystkie wartości zostaną umieszczone jeden po drugim w 9 rzędach. Na przykład w pierwszym segmencie będzie 0,11,22…0,11,22…0, 11, …

57 data-structures hash hash-tables primes

12

Czy bajt zawiera 8 bitów, czy 9?

Przeczytałem w tym instruktażowym samouczku programowania, że 8 bitów służy do danych, a 1 bit do parzystości, który jest następnie wykorzystywany do wykrywania błędu parzystości (spowodowanego przez awarię sprzętu lub zakłócenia elektryczne). Czy to prawda?

56 computer-architecture numeral-representations

9

Jakie byłyby rzeczywiste implikacje konstruktywnego dowodu ?

Rozumiem na wysokim poziomie problem i rozumiem, że gdyby absolutnie „udowodniono”, że jest to prawdą w dostarczonym rozwiązaniu, otworzyłoby to drzwi do rozwiązania wielu problemów w dziedzinie informatyki.P=NPP=NPP=NP Moje pytanie brzmi: jeśli ktoś opublikowałby niepodważalny, konstruktywny dowód , jakie byłyby natychmiastowe skutki takiego odkrycia? P=NPP=NPP=NP Nie proszę o opinie na …

56 complexity-theory p-vs-np

6

Jeśli wszyscy wierzą w P ≠ NP, dlaczego wszyscy sceptycznie podchodzą do prób udowodnienia P ≠ NP?

Wielu wydaje się wierzyć, że , ale wielu uważa również, że jest bardzo mało prawdopodobne, aby kiedykolwiek to udowodniono. Czy nie ma w tym żadnej niespójności? Jeśli uważasz, że taki dowód jest mało prawdopodobny, powinieneś również uwierzyć, że brakuje solidnych argumentów za P ≠ N P. Czy też istnieją dobre …

55 complexity-theory p-vs-np

6

Czy istnieją minimalne kryteria dla języka programowania Turinga?

Czy istnieje zestaw konstrukcji języka programowania w języku programowania, aby można go uznać za ukończony jako Turing? Z tego, co mogę powiedzieć z wikipedii , język musi obsługiwać rekursję lub, pozornie, musi być w stanie działać bez zatrzymywania się. Czy to już wszystko?

55 computability programming-languages turing-machines turing-completeness

8

Jaki jest najszybszy algorytm sortowania dla tablicy liczb całkowitych?

Podczas nauki w szkole średniej natknąłem się na wiele algorytmów sortowania. Jednak nigdy nie wiem, która jest najszybsza (dla losowej liczby całkowitej). Więc moje pytania to: Który jest najszybszym obecnie znanym algorytmem sortowania? Teoretycznie jest możliwe, że są jeszcze szybsze? Jaka jest najmniej złożoność sortowania?

55 algorithms time-complexity optimization sorting

9

Co to jest bezpieczny język programowania?

Coraz popularniejsze stają się bezpieczne języki programowania (PL). Zastanawiam się, jaka jest formalna definicja bezpiecznej PL. Na przykład C nie jest bezpieczny, ale Java jest bezpieczna. Podejrzewam, że właściwość „bezpieczna” powinna być stosowana do implementacji PL, a nie do samej PL. Jeśli tak, omówmy definicję bezpiecznej implementacji PL. Moje własne …

55 programming-languages