Informatyka

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

3
Kiedy minimalne drzewo rozpinające dla wykresu nie jest unikalne
Biorąc pod uwagę ważony, niekierowany wykres G: Które warunki muszą być spełnione, aby istniało wiele drzew minimalnych obejmujących G? Wiem, że MST jest wyjątkowy, gdy wszystkie wagi są różne, ale nie można odwrócić tego stwierdzenia. Jeśli na wykresie jest wiele krawędzi o tej samej masie, może istnieć wiele MST, ale …
4
Minimalna liczba porównań potrzebnych do posortowania (uporządkowania) 5 elementów
Znajdź najmniejszą liczbę porównań potrzebną do posortowania (uporządkowania) pięciu elementów i opracuj algorytm, który sortuje te elementy przy użyciu tej liczby porównań. Rozwiązanie : Jest ich 5! = 120 możliwych wyników. Dlatego drzewo binarne do procedury sortowania będzie miało co najmniej 7 poziomów. Rzeczywiście, ≥ 120 oznacza≥ 7. Ale 7 …
4
Czy nie ma algorytmu sortowania ze wszystkimi konkretnymi pożądanymi właściwościami?
Na stronie internetowej Sorting Algorytmy wysunięto następujące oświadczenie: Idealny algorytm sortowania miałby następujące właściwości: Stabilny: nie zmienia się kolejności klawiszy równych. Działa w miejscu, wymagając dodatkowej przestrzeni.O ( 1 )O(1)O(1) Porównania klawiszy w najgorszym przypadku .O ( n ⋅ lg( n ) )O(n⋅lg⁡(n))O(n\cdot\lg(n)) Zamiany najgorszym przypadku .O ( n )O(n)O(n) …
3
Algorytm minimalizujący pole powierzchni, przy danej objętości
Rozważ następujące zadanie algorytmiczne: Dane wejściowe: dodatnia liczba całkowita wraz z podstawową faktoryzacją Znajdź: dodatnie liczby całkowite które minimalizują , z zastrzeżeniem ograniczenia, żennnx,y,zx,y,zx,y,zxy+yz+xzxy+yz+xzxy+yz+xzxyz=nxyz=nxyz=n Jaka jest złożoność tego problemu? Czy istnieje algorytm czasu wielomianowego? Czy to trudne NP? Ten problem zasadniczo pyta: ze wszystkich prostokątnych brył, których objętość wynosi i …
7
Jeden element, który różni się dwiema tablicami. Jak znaleźć to skutecznie?
Przygotowuję się do wywiadu na temat programowania i naprawdę nie mogę znaleźć najbardziej skutecznego sposobu rozwiązania tego problemu. Załóżmy, że mamy dwie tablice składające się z liczb nieposortowanych. Tablica 2 zawiera liczbę, której nie ma tablica 1. Obie tablice mają losowo rozmieszczone liczby, niekoniecznie w tej samej kolejności lub przy …
5
Kompresja danych przy użyciu liczb pierwszych
Niedawno natknąłem się na następujący interesujący artykuł, który twierdzi, że skutecznie kompresuje losowe zestawy danych o zawsze ponad 50%, niezależnie od rodzaju i formatu danych. Zasadniczo używa liczb pierwszych do unikalnego skonstruowania reprezentacji 4-bajtowych fragmentów danych, które są łatwe do zdekompresowania, biorąc pod uwagę, że każda liczba jest unikalnym produktem …
1
Jakie są najsilniejsze znane typy systemów, dla których można wnioskować?
Powszechnie wiadomo, że wnioskowanie typu Hindleya-Milnera (prosty typ calculus z polimorfizmem) ma rozstrzygające wnioskowanie: można zrekonstruować typy zasad dla dowolnych programów bez adnotacji.λλ\lambda Dodanie klas typu Haskell wydaje się zachowywać tę rozstrzygalność, ale dalsze dodawanie sprawia, że ​​wnioskowanie bez adnotacji jest nierozstrzygalne (rodziny typów, GADT, typy zależne, typy Rank-N, System …
11
Dlaczego
Chciałbym wiedzieć, czy istnieje zasada, aby to udowodnić. Na przykład, jeśli użyję prawa dystrybucyjnego, dostanę tylko (A∨A)∧(A∨¬B)(ZA∨ZA)∧(ZA∨¬b)(A \lor A) \land (A \lor \neg B) .
2
Czy wyrażenie obliczeniowe jest takie samo jak monada?
To pytanie zostało przeniesione z Przepełnienia stosu, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 5 lat temu . Wciąż uczę się programowania funkcjonalnego (z f #) i ostatnio zacząłem czytać o wyrażeniach obliczeniowych. Nadal nie rozumiem w pełni tego pojęcia, a jedną rzeczą, która nie daje …
5
Dlaczego języki funkcjonalne Turing są kompletne?
Być może moje ograniczone rozumienie tematu jest nieprawidłowe, ale rozumiem do tej pory: Programowanie funkcjonalne oparte jest na rachunku Lambda Calculus opracowanym przez Alonzo Church. Programowanie imperatywne oparte jest na modelu maszyny Turinga, stworzonym przez Alana Turinga, ucznia Churcha. Rachunek Lambda jest tak potężny i zdolny jak Maszyna Turinga, co …
3
Dlaczego problemy związane z NP są tak różne pod względem ich przybliżenia?
Chciałbym rozpocząć pytanie od stwierdzenia, że ​​jestem programistą i nie mam dużego doświadczenia w teorii złożoności. Jedną z rzeczy, które zauważyłem, jest to, że o ile wiele problemów jest NP-zupełnych, o tyle w przypadku problemów z optymalizacją niektóre są znacznie trudniejsze do oszacowania niż inne. Dobrym przykładem jest TSP. Chociaż …
3
Konwertowanie problemów matematycznych na instancje SAT
Chcę zmienić problem matematyczny, który mam, w logiczny problem satysfakcji (SAT), a następnie rozwiązać go za pomocą SAT Solvera. Zastanawiam się, czy ktoś zna instrukcję, przewodnik lub cokolwiek, co pomoże mi przekonwertować mój problem na instancję SAT. Chcę też rozwiązać ten problem w czasie lepszym niż wykładniczy. Mam nadzieję, że …
2
Teoretyczne podstawy podziału i podboju
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 greedoid), nie mogłem znaleźć takiej ogólnej struktury algorytmów opartych na D&C. Po pierwsze, zdaję …
4
Zautomatyzowana optymalizacja mnożenia wektora macierzy 0-1
Pytanie: Czy istnieje ustalona procedura lub teoria generowania kodu, która skutecznie stosuje mnożenie macierzy-wektora, gdy matryca jest gęsta i wypełniona tylko zerami i zerami? Najlepiej byłoby, gdyby zoptymalizowany kod systematycznie wykorzystywał wcześniej obliczone informacje w celu ograniczenia powielania pracy. Innymi słowy, mam macierz MMM i chcę wykonać pewne wstępne obliczenia …
1
Jak pokazać, że L = L (G)?
Określanie języków formalnych poprzez nadawanie gramatyki formalnej jest częstym zadaniem: potrzebujemy gramatyki nie tylko do opisu języków, ale także do ich analizy, a nawet do właściwej nauki . We wszystkich przypadkach ważne jest, aby gramatyka była poprawna , czyli generowała dokładnie pożądane słowa. Często możemy dyskutować na wysokim szczeblu, dlaczego …
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.