Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

7
Dlaczego A oznacza, że ​​B jest prawdziwe, jeśli A jest fałszywe, a B jest fałszywe?
Wydaje mi się, że „implikacja” w języku angielskim nie oznacza tego samego, co operator logiczny „implikuje”, podobnie jak słowo „LUB” w większości przypadków oznacza „Wyłączne OR” w naszym codziennym użyciu języka. Weźmy dwa przykłady: Jeśli dzisiaj jest poniedziałek, jutro jest wtorek. To prawda . Ale jeśli powiemy: Jeśli słońce jest …
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 …
5
Dlaczego osoby o niskiej sprawności mają szansę przeżyć do następnego pokolenia?
Obecnie czytam i obserwuję algorytm genetyczny i uważam go za bardzo interesujący (nie miałem okazji go studiować, gdy byłem na uniwersytecie). Rozumiem, że mutacje oparte są na prawdopodobieństwie (losowość jest źródłem ewolucji), ale nie rozumiem, dlaczego przetrwanie. Z tego, co rozumiem, osoba która ma sprawność fizyczną tak jak dla innej …
3
Pobieranie najkrótszej ścieżki dynamicznego wykresu
Obecnie badam najkrótsze ścieżki na ukierunkowanych wykresach. Istnieje wiele wydajnych algorytmów do znajdowania najkrótszej ścieżki w sieci, takich jak dijkstra lub bellman-ford. Ale co, jeśli wykres jest dynamiczny? Mówiąc dynamiczny, mam na myśli to, że możemy wstawiać lub usuwać wierzchołki podczas wykonywania programu. Próbuję znaleźć skuteczny algorytm do aktualizowania najkrótszych …
2
Wydajny algorytm do „sumowania” zestawu sum
Biorąc pod uwagę zbiór wielu liczb naturalnych X, rozważ zestaw wszystkich możliwych sum: sums(X)={∑i∈Ai|A⊆X}sums(X)={∑i∈Ai|A⊆X}\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\} Na przykład podczas gdy .sumy ( { 1 , 1 } ) = { 0 , 1 , 2 }sums({1,5})={0,1,5,6}sums({1,5})={0,1,5,6}\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}sums({1,1})={0,1,2}sums({1,1})={0,1,2}\textrm{sums}(\left\{1,1\right\}) = …
1
Sortowanie jako program liniowy
Zaskakująca liczba problemów ma dość naturalne ograniczenia w programowaniu liniowym (LP). Przykłady, takie jak przepływy sieciowe, dopasowanie dwustronne, gry o sumie zerowej, najkrótsze ścieżki, forma regresji liniowej, a nawet ocena obwodu, patrz rozdział 7 w [1]! Ponieważ ocena obwodu ogranicza się do programowania liniowego, każdy problem w musi mieć sformułowanie …
3
Jakie są funkcje etapowe (koncepcyjnie)?
W niedawnym artykule CACM [1] autorzy przedstawiają implementację funkcji etapowych . Używają tego terminu, jakby był dobrze znany, i żadne z odniesień nie wygląda jak oczywiste wprowadzenie. Podają krótkie wyjaśnienie (zmieniono moje wyróżnienie i numer referencyjny; w oryginale jest 22) W kontekście generowania programu, programowanie wieloetapowe (MSP, w skrócie inscenizacja), …
1
Jak udowodnić poprawność algorytmu losowego?
Mam dwa sposoby tworzenia listy przedmiotów w losowej kolejności i chciałbym ustalić, czy są one równie uczciwe (obiektywne). Pierwszą metodą, której używam, jest skonstruowanie całej listy elementów, a następnie wykonanie losowania (powiedzmy losowanie Fisher-Yates). Druga metoda jest raczej metodą iteracyjną, która utrzymuje losowość listy przy każdym wstawieniu. W pseudokodzie funkcja …
4
Czy zajęty bóbr to najszybciej rosnąca funkcja znana człowiekowi?
To pytanie zostało przeniesione z Teoretycznej wymiany stosów komputerowych, ponieważ można na nie odpowiedzieć w ramach wymiany stosów komputerowych. Migrował 7 lat temu . Właśnie miałem to interesujące pytanie. Jaka jest najszybciej rosnąca funkcja znana człowiekowi? Czy to zajęty bóbr ? Znamy funkcje takie jak x2)x2)x^2 , ale ta funkcja …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.