Informatyka

4

Zastanawiam się, czy istnieje standardowy sposób pomiaru „sortowania” tablicy? Czy tablicę z medianą liczby możliwych inwersji można uznać za maksymalnie nieposortowaną? Rozumiem przez to, że jest to w zasadzie tak daleko, jak to możliwe, od sortowania lub odwrotnego sortowania.

34 algorithms algorithm-analysis sorting arrays

5

Co oznacza bycie kompletnym Turinga?

Widzę, że większość definicji tego, co ma być Turing-zupełne, jest do pewnego stopnia tautologiczna. Na przykład, jeśli Google „co oznacza bycie kompletnym Turinga”, otrzymuje: Komputer jest kompletny, jeśli może rozwiązać każdy problem, który maszyna Turinga może ... Chociaż jest bardzo dobrze określone, czy różne systemy są Turinga kompletne, czy nie, …

34 turing-machines turing-completeness

4

Czy występują problemy z NP, nie w P i nie w NP Complete?

Czy są jakieś znane problemy w (a nie w ), które nie są ukończone? Rozumiem, że nie ma obecnie znanych problemów, ale nie zostało to wykluczone. NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP} Jeśli występuje problem, który to (a nie ), ale nie , czy byłby to wynik braku istniejącego izomorfizmu między instancjami tego problemu zestaw? …

34 complexity-theory np-complete p-vs-np

2

w sprawie „O okrucieństwie faktycznego nauczania informatyki”

Dijkstra w swoim eseju O okrucieństwie prawdziwego nauczania informatyki przedstawia następującą propozycję wprowadzenia kursu programowania: Z jednej strony uczymy czegoś, co wygląda na rachunek predykatu, ale robimy to zupełnie inaczej niż filozofowie. Aby wyszkolić początkującego programistę w zakresie manipulowania nieinterpretowanymi formułami, uczymy go bardziej jako algebry boolowskiej, zapoznając studenta ze …

33 reference-request programming-languages education didactics

2

Jaka jest różnica między wątkami na poziomie użytkownika a wątkami na poziomie jądra?

Po przeczytaniu kilku źródeł wciąż nie rozumiem wątków na poziomie użytkownika i jądra. W szczególności: Wątki mogą istnieć zarówno na poziomie użytkownika, jak i jądra Jaka jest różnica między poziomem użytkownika a poziomem jądra?

33 operating-systems terminology concurrency os-kernel

2

Czy istnieje różnica między programowaniem dynamicznym od góry do dołu i od dołu do góry?

Czy istnieje fundamentalna różnica między programowaniem dynamicznym od góry do dołu i od dołu do góry? W szczególności, czy istnieje problem, który można rozwiązać oddolnie, ale nie odgórnie? Czy też podejście oddolne jest jedynie odwijaniem nawrotu w podejściu odgórnym?

33 algorithms dynamic-programming

1

Czy trudno jest wypełnić pojemniki minimalnymi ruchami?

Jest koszy i rodzajów piłek. th bin ma etykiet na , jest to oczekiwana liczba kulek typu .nnnmmmiiiai,jai,ja_{i,j}1≤j≤m1≤j≤m1\leq j\leq mjjj Zaczynasz od kul typu . Każda kula typu ma masę i chce umieścić kulki w pojemnikach tak, aby bin miał masę . Rozmieszczenie kulek, które utrzymują poprzednie warunki, nazywa się …

33 complexity-theory np-hard integer-programming

2

Czy istnieją ulepszenia w algorytmie Dany Angluin do uczenia się regularnych zestawów

W swojej zasadniczej pracy z 1987 roku Dana Angluin przedstawia algorytm wielomianowy do nauki DFA na podstawie zapytań członkowskich i teorii (kontrprzykłady do proponowanego DFA). Pokazuje, że jeśli próbujesz nauczyć się minimalnego DFA ze stanami , a twój największy przykład ma długość , to musisz wykonać kwerendy członkostwa i co …

33 algorithms learning-theory machine-learning

2

Jak asymptotycznie źle jest naiwne tasowanie?

Powszechnie wiadomo, że ten „naiwny” algorytm tasowania tablicy poprzez zamianę każdego elementu na inny losowo wybrany nie działa poprawnie: for (i=0..n-1) swap(A[i], A[random(n)]); W szczególności, ponieważ w każdym z nnn powtórzeń, jeden z nnn wyboru jest (z jednolitego prawdopodobieństwa) jest nnnnn^n możliwych ścieżek „” do obliczeń; ponieważ liczba możliwych permutacji …

33 algorithms algorithm-analysis asymptotics probability-theory randomness

4

Jaka jest dokładnie różnica semantyczna między zestawem a typem?

EDYCJA: Zadałem teraz podobne pytanie dotyczące różnicy między kategoriami i zestawami. Za każdym razem czytam o teorii typów (co prawda jest raczej nieformalny), naprawdę nie mogę zrozumieć, jak różni się od teorii mnogości, konkretnie . Rozumiem, że istnieje konceptualna różnica między powiedzeniem „x należy do zbioru X” a „x jest …

33 type-theory sets

4

Na czym polega programowanie dynamiczne?

Z góry przepraszam, jeśli to pytanie brzmi głupio ... O ile wiem, budowanie algorytmu przy użyciu programowania dynamicznego działa w ten sposób: wyrazić problem jako relację nawrotu; wdrożyć relację powtarzalności albo poprzez zapamiętywanie, albo poprzez podejście oddolne. O ile wiem, powiedziałem wszystko o programowaniu dynamicznym. Mam na myśli: programowanie dynamiczne …

33 algorithms dynamic-programming algorithm-design

4

Jak O i Ω odnoszą się do najgorszego i najlepszego przypadku?

Dzisiaj omawialiśmy na wykładzie bardzo prosty algorytm znajdowania elementu w posortowanej tablicy za pomocą wyszukiwania binarnego . Poproszono nas o określenie jego asymptotycznej złożoności dla szeregu nnn elementów. Mój pomysł polegał na tym, że jest to wyraźnie O ( logn )O(log⁡n)O(\log n) lub O ( log2)n )O(log2⁡n)O(\log_2 n) aby być …

33 algorithm-analysis asymptotics landau-notation reference-question

2

Zwykłe języki planarne

W mojej klasie uczeń zapytał, czy wszystkie skończone automaty można narysować bez przekraczania krawędzi (wydaje się, że zrobiły to wszystkie moje przykłady). Oczywiście odpowiedź jest przecząca, oczywisty automat dla języka ma strukturę K_5 , kompletny wykres na pięciu węzłach . Yuval pokazał podobną strukturę dla pokrewnego języka.{x ∈ { a …

32 regular-languages finite-automata planar-graphs

3

Czy sprzęt / implementacja wpłynie na złożoność algorytmów czas / przestrzeń?

Nie jestem nawet studentem CS, więc może to być głupie pytanie, ale proszę o wyrozumiałość ... W erze komputerów wstępnych możemy zaimplementować strukturę danych tablicowych z czymś w rodzaju tablicy szuflad. Ponieważ jeden zlokalizować szuflady z odpowiadającym indeksu przed ekstrakcji wartość z niej złożoność czas odnośnika tablicy jest , przy …

32 algorithms algorithm-analysis data-structures runtime-analysis

5

Jak komputery pamiętają, gdzie przechowują rzeczy?

Kiedy komputer przechowuje zmienną, kiedy program musi uzyskać wartość zmiennej, skąd komputer wie, gdzie szukać w pamięci wartości tej zmiennej?

32 compilers memory-access variable-binding