Informatyka

4

Czy sensowne jest posiadanie zarówno koncepcji „zerowej”, jak i „być może”?

Podczas tworzenia klienta interfejsu API sieci Web w języku C # napotkałem problem dotyczący nullwartości, która reprezentowałaby dwie różne rzeczy: nic , np. foomoże mieć lub może nie miećbar nieznany : domyślnie odpowiedź API zawiera tylko podzbiór właściwości, musisz wskazać, które dodatkowe właściwości chcesz. Tak nieznany oznacza, że właściwość nie …

11 programming-languages language-design

2

Najbliższa para punktów między dwoma zestawami, w 2D

Mam dwa zestawy punktów w płaszczyźnie dwuwymiarowej. Chcę znaleźć najbliższą parę punktów s , t taką, że s ∈ S , t ∈ T , a odległość euklidesowa między s , t jest tak mała, jak to możliwe. Jak skutecznie można to zrobić? Czy można tego dokonać w czasie O …

11 algorithms computational-geometry

1

Narzędzie do prototypowania semantyki języka programowania

Czy jest jakieś narzędzie do prototypowania semantyki języka programowania i systemu typów, a także umożliwia pewnego rodzaju sprawdzanie modelu standardowych właściwości, takich jak poprawność typu? Pytam o to, ponieważ czytam książkę o stopie i zapewnia on dokładnie taką funkcjonalność, jakiej chcę, ale dla modeli wyrażonych za pomocą logiki relacyjnej. Zdaję …

11 reference-request programming-languages semantics model-checking

1

Jak podzielić zestaw na określoną liczbę rozłącznych podzbiorów pod pewnymi warunkami?

Dostaję zestaw , liczbę całkowitą s \ leqslant k i nieujemne liczby całkowite a_ {ij} . Mój problem polega na znalezieniu s podzbiory rozłączne S_j z \ {1, \ ldots, k \} takie, że:A≜{1,…,k}A≜{1,…,k}A\triangleq\{1,\ldots,k\}s⩽ks⩽ks\leqslant kaijaija_{ij}sssSjSjS_j{1,…,k}{1,…,k}\{1,\ldots,k\} ⋃sj=1Sj=A⋃j=1sSj=A\bigcup_{j=1}^s S_j=A ; i |Sj|⩽aij|Sj|⩽aij|S_j|\leqslant a_{ij} dla wszystkich i∈Sji∈Sji\in S_j i j=1,…,sj=1,…,sj=1,\ldots,s . Jak rozwiązać …

11 complexity-theory integer-programming

3

Automatyczne downcasting na podstawie typu

W Javie musisz jawnie rzutować, aby sprowadzić zmienną public class Fruit{} // parent class public class Apple extends Fruit{} // child class public static void main(String args[]) { // An implicit upcast Fruit parent = new Apple(); // An explicit downcast to Apple Apple child = (Apple)parent; } Czy istnieje …

11 object-oriented type-inference language-design

1

W jaki sposób nazwa „Isabelle” (przysłowiowa twierdzenie) ma swoją nazwę?

Tytuł mówi wszystko, ale jestem ciekawy, ponieważ nie jest oczywiste, jak to się stało, że nazwano go „Isabelle”. Czy to imię pochodzi od osoby? Niektórych wyszukiwań w Google nie mogłem się dowiedzieć.

11 history automated-theorem-proving isabelle

1

Dlaczego NP jest w EXPTIME?

Czy istnieje prosty sposób, aby dowiedzieć się, dlaczego NP jest w WYGODZIE? Wydaje mi się a priori możliwe, że może istnieć problem, który wymaga czasu nadwykładniczego do rozwiązania, ale którego rozwiązanie można zweryfikować w czasie wielomianowym.

11 complexity-theory complexity-classes

1

Indeksowanie w bazie danych wzorców - rozwiązanie Corf Optimal Rubik's Cube

Jako zabawny projekt pracowałem nad implementacją C # Richarda Korfa - Znalezienie optymalnych rozwiązań dla kostki Rubika przy użyciu baz danych wzorców. https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf Właściwie to działa, staram się tylko ulepszyć swoje rozwiązanie. Jedną rzeczą, na którą Korf patrzy w swoim artykule, jest to, jak przechowuje i indeksuje bazy danych wzorców. …

11 algorithms permutations

4

Dlaczego musimy wymieniać abstrakcję na szybkość?

Dlaczego języki wysokiego poziomu najwyraźniej nigdy nie osiągają języków niższego poziomu pod względem szybkości? Przykładami języków wysokiego poziomu są Python, Haskell i Java. Języki niskiego poziomu byłyby trudniejsze do zdefiniowania, ale powiedzmy C. Porównania można znaleźć w całym Internecie i wszyscy zgadzają się, że C jest znacznie szybszy, czasami nawet …

11 programming-languages performance

1

Znalezienie minimalnego pokrycia podzbioru skończonego produktu kartezjańskiego według produktów kartezjańskich

Biorąc pod uwagę podzbiór iloczynu kartezjańskiego dwóch skończonych zestawów, chciałbym znaleźć jego minimalną osłonę przez zestawy, które same są produktami kartezjańskimi.I×JI×JI \times J Na przykład, biorąc pod uwagę iloczyn między i , mogę obserwować podzbiór i spróbuj pokryć go minimalną liczbą produktów kartezjańskich.I={A,B,C}I={A,B,C}I=\{A,B,C\}J={1,2,3}J={1,2,3}J=\{1,2,3\}{(A,2),(B,3),(B,2)}{(A,2),(B,3),(B,2)}\{(A,2), (B,3), (B,2)\} to zrobić na dwa sposoby: …

11 algorithms set-cover

3

Czy jest jakiś dowód, że komputery kwantowe są bardziej wydajne niż komputery klasyczne?

Algorytm Shora jest często używany jako argument. Może rozwiązać problem faktoryzacji szybciej niż jakikolwiek znany algorytm dla klasycznych komputerów. Jednak nie mamy dowodu, że klasyczne komputery nie mogą również efektywnie uwzględniać liczb całkowitych. Czy istnieje jakiś faktyczny dowód, że komputery kwantowe mogą rozwiązać niektóre problemy szybciej niż klasyczne komputery?

11 algorithms efficiency quantum-computing

1

Twardość NP pokrycia kawałkami prostokątnymi (Google Hash Code 2015 Round Round)

Kodeks Hash 2015 Okrągły testowania Google ( oświadczenie problemem ) poprosił o następującym problemem: dane wejściowe: siatka z zaznaczonymi kwadratami, próg , maksymalny obszarT ∈ N A ∈ NM.M.MT.∈ N.T.∈N.T \in \mathbb{N}A ∈ NZA∈N.A \in \mathbb{N} Wydajność: największa powierzchnia całkowita zestawu rozłącznych prostokątów o współrzędnych całkowitą w tak, że każdy …

11 complexity-theory reductions np-hard

3

Jaka jest różnica między abstrakcyjnymi typami danych a obiektami?

Odpowiedź na Programmers.SE charakteryzuje esej Cook ( Przedmioty nie są ADTS ) wypowiedź Obiekty zachowują się jak funkcja charakterystyczna względem wartości typu, a nie jak algebra. Obiekty używają abstrakcji proceduralnej zamiast abstrakcji typu ADT zwykle mają unikalną implementację w programie. Gdy w danym języku są moduły, możliwe jest posiadanie wielu …

11 programming-languages object-oriented abstract-data-types

2

Dlaczego najmniej ważny punkt (LFP) jest ważny w analizie programu?

Próbuję uzyskać ogólny obraz znaczenia najmniej ustalonego punktu (LFP) w analizie programu. Na przykład abstrakcyjna interpretacja wydaje się wykorzystywać istnienie LFP. Wiele prac badawczych na temat analizy programów również koncentruje się w dużej mierze na znalezieniu najmniej ustalonego punktu. Mówiąc dokładniej, ten artykuł w wikipedii: Twierdzenie Knaster-Tarski wspomina, że LFP …

11 programming-languages finite-model-theory fixed-point

1

Jak szybko możemy obliczyć rozmiar maksymalnego dopasowania na nieważonym grafie dwustronnym?

Czy istnieje sposób na obliczenie wielkości maksymalnego dopasowania na nieważonym grafie dwustronnym bardziej efektywnie (np. Szybciej) niż obliczenie maksymalnego dopasowania? Jest to dalekie ujęcie, ale często interesującym problemem jest unikanie takich niepotrzebnych obliczeń. Motywacja Problem, który próbuję rozwiązać, to match-2, w którym oba zestawy mają różne rozmiary. Muszę ustalić, czy …

11 algorithms graphs optimization matching bipartite-matching