Informatyka

6

Sortowanie funkcji według asymptotycznego wzrostu

Załóżmy, że mam na przykład listę funkcji nloglog( n ), 2n, n ! , n3), n lnn , …nlog⁡log⁡(n),2)n,n!,n3),nln⁡n,…\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots Jak sortować je asymptotycznie, tj. Według relacji zdefiniowanej przez fa≤Osol⟺fa∈ O ( g)fa≤Osol⟺fa∈O(sol)\qquad f \leq_O g \iff f \in O(g) , zakładając, …

35 asymptotics landau-notation reference-question

2

Dlaczego log w dużym O wyszukiwania binarnego nie jest bazą 2?

Jestem nowy w zrozumieniu algorytmów informatycznych. Rozumiem proces wyszukiwania binarnego, ale mam niewielkie nieporozumienie z jego wydajnością. W rozmiarze elementów znalezienie danego elementu wymagałoby średnio kroków. Biorąc podstawę 2 logarytmu obu stron daje . Czy więc średnia liczba kroków dla algorytmu wyszukiwania binarnego nie byłaby ?s=2ns=2ns = 2^nnnnlog2(s)=nlog2⁡(s)=n\log_2(s) = nlog2(s)log2⁡(s)\log_2(s) …

35 algorithms runtime-analysis binary-search

4

Dlaczego programowanie liniowe w P, a programowanie liczb całkowitych jest trudne?

Programowanie liniowe (LP) jest w P, a programowanie liczb całkowitych (IP) jest trudne dla NP. Ponieważ jednak komputery mogą manipulować liczbami z ograniczoną precyzją, w praktyce komputer używa liczb całkowitych do programowania liniowego. Z tego powodu, czy LP i IP nie powinny należeć do tej samej klasy złożoności?

35 complexity-theory polynomial-time

2

Czego Idris nie może zrobić, rezygnując z kompletności Turinga?

Wiem, że Idris ma typy zależne, ale nie jest kompletny. Czego nie może zrobić, rezygnując z kompletności Turinga i czy wiąże się to z posiadaniem typów zależnych? Wydaje mi się, że jest to dość specyficzne pytanie, ale nie wiem zbyt wiele o typach zależnych i pokrewnych systemach typów.

35 computability programming-languages type-theory dependent-types

6

Czy są jakieś nieskończone automaty?

W teorii automatów wszyscy od samego początku czytamy automaty jako automaty skończone. Chcę wiedzieć, dlaczego automaty są skończone? Dla jasności, co to jest w skończonym automacie - alfabet, język, ciągi znaków wyrażeń regularnych, czy co? Czy istnieją (teoretycznie) jakieś nieskończone automaty?

35 automata finite-automata

3

W najgorszym przypadku w miejscu stabilny rodzaj?

Mam problem ze znalezieniem dobrych zasobów, które dają najgorszy przypadek w miejscu stabilnego algorytmu sortowania. Czy ktoś wie o dobrych zasobach?O ( n lnn )O(nln⁡n)O(n \ln n) Tylko przypomnienie, w miejscu oznacza, że wykorzystuje przekazaną tablicę, a algorytm sortujący może używać tylko stałej dodatkowej przestrzeni. Stabilny oznacza, że elementy z …

35 algorithms reference-request sorting in-place

2

Kwantowy rachunek lambda

Klasycznie istnieją 3 popularne sposoby myślenia o obliczeniach: maszyna Turinga, obwody i rachunek lambda (używam tego jako haczyka dla większości widoków funkcjonalnych). Wszystkie 3 były owocnymi sposobami myślenia o różnych typach problemów, a różne dziedziny stosują różne formuły z tego powodu. Kiedy jednak pracuję z obliczeniami kwantowymi, zawsze myślę tylko …

35 lambda-calculus quantum-computing reference-request computation-models

6

Czy algorytmy kompresji bezstratnej zmniejszają entropię?

Według Wikipedii : Entropia Shannona mierzy informacje zawarte w wiadomości, a nie część wiadomości, która jest określona (lub przewidywalna). Przykłady tych ostatnich obejmują nadmiarowość w strukturze języka lub właściwości statystyczne związane z częstotliwościami występowania par liter lub słów, trojaczków itp. Zatem entropia jest miarą ilości informacji zawartych w wiadomości. Kodery …

35 information-theory data-compression entropy

10

Języki programowania wizualnego

Większość z nas uczyła się programowania przy użyciu „tekstowych” języków programowania, takich jak Basic, C / C ++ i Java. Uważam, że myślenie wizualne jest bardziej naturalne i wydajne dla ludzi. Programowanie wizualne pozwala programistom pisać programy, manipulując elementami graficznymi. Myślę, że użycie programowania wizualnego powinno poprawić jakość kodu i …

35 programming-languages

13

Kryteria wyboru języka dla pierwszego kursu programowania

Jako edukator CS na poziomie uniwersyteckim często pojawia się kwestia, którego języka programowania uczyć w pierwszym kursie programowania. Do wyboru są tysiące języków i wiele gorączek religijnych (lub gorączek) wspierających jeden obóz językowy nad drugim. Wszystkie te subiektywne uprzedzenia dotyczące każdego języka programowania bardzo utrudniają nauczycielowi wybór jednego z nich. …

35 programming-languages education

1

Czy otrzymujesz DFS, jeśli zmienisz kolejkę na stos w implementacji BFS?

Oto standardowy pseudokod pierwszego wyszukiwania szerokości: { seen(x) is false for all x at this point } push(q, x0) seen(x0) := true while (!empty(q)) x := pop(q) visit(x) for each y reachable from x by one edge if not seen(y) push(q, y) seen(y) := true Tutaj pushi popzakłada się, że …

35 algorithms graphs

2

Czy istnieje zadanie, które można rozwiązać w czasie wielomianowym, ale którego nie da się zweryfikować w czasie wielomianowym?

Mój kolega i ja właśnie uderzyliśmy w notatki jednego z naszych profesorów. Notatki stwierdzają, że istnieją zadania, które można rozwiązać w czasie wielomianowym (są w klasie PF), ale NIE są możliwe do zweryfikowania w czasie wielomianowym (NIE są w klasie NPF). Aby rozwinąć te klasy: Otrzymujemy trochę danych wejściowych X …

34 complexity-theory np

3

Algorytm znajdujący liczbę prostych ścieżek od do w

Ktoś może zaproponować mi liniowy algorytmu czasu, który wprowadzany jest skierowany acykliczny wykres a dwa wierzchołki i i powraca liczbę prostych odcinków z na w . Mam algorytm, w którym uruchomię DFS (Głębokie pierwsze wyszukiwanie), ale jeśli DFS znajdzie to nie zmieni koloru (z białego na szary) żadnego z węzłów, …

34 algorithms graphs

9

Jakie znaczenie mają języki kontekstowe (typ 1)?

Widząc, że w hierarchii Chomsky'ego języki Type 3 mogą być rozpoznawane przez maszynę stanową bez pamięci zewnętrznej (tj. Skończonego automatu), Type 2 przez maszynę stanową z pojedynczym stosem (tj. Automat push-down) i typ 0 przez automat stanowy z dwoma stosami (lub równoważnie taśmą, jak w przypadku maszyn Turinga), jak języki …

34 formal-languages applied-theory computability automata formal-grammars

7

W jaki sposób komputer określa, czy liczba jest mniejsza czy większa od innej?

To może brzmieć jak głupie pytanie, ale jestem naprawdę ciekawy, skąd komputer wie, że ? Ponadto, skąd komputer wie, że kolejność liczb całkowitych wynosi a alfabet to A, B, C, D, ...? Czy jest to gdzieś zapisane w sprzęcie, czy też system operacyjny zapewnia tego rodzaju informacje?1<21<21<21,2,3,4,5,…1,2,3,4,5,…1,2,3,4,5,\ldots

34 computer-architecture reference-question