Informatyka

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

6
Wydajna kompresja prostych danych binarnych
Mam plik zawierający uporządkowane liczby binarne od do 2 n - 1 :0002)n- 12n−12^n - 1 0000000000 0000000001 0000000010 0000000011 0000000100 ... 1111111111 7z nie skompresował tego pliku bardzo wydajnie (dla n = 20 22 MB zostało skompresowanych do 300 kB). Czy istnieją algorytmy, które potrafią rozpoznać bardzo prostą strukturę …
2
Jak znaleźć żonę w supermarkecie?
Jeśli w labiryncie zagubiły się dwie osoby, czy istnieje algorytm, którego oboje mogą użyć do znalezienia siebie nawzajem bez uprzedniego uzgodnienia, jakiego algorytmu będą używać? Myślę, że ten algorytm ma pewne cechy: Każda osoba musi być w stanie wyprowadzić ją za pomocą logiki, która nie przyjmuje żadnych założeń na temat …
3
Problemy z NP-zupełnością nie „oczywiście” w NP
Wielu przyszło na myśl, że we wszystkich dowodach kompletności , które przeczytałem (które pamiętam), zawsze trywialne jest pokazanie, że problem jest w i pokazanie, że jest to -hard jest ... trudną częścią. Jakie problemy zakończone to te, których weryfikatory czasu wielomianowego są wysoce nietrywialne?NP NP NPNPNP\textbf{NP}NPNP\textbf{NP}NPNP\textbf{NP}NPNP\textbf{NP}
2
Sprzedawanie bloków czasu
Biorąc pod uwagę nnn przedziałów czasowych, które kkk ludzie chcą kupić. Osoba iii ma wartość h ( i , j ) ≥ 0h(i,j)≥0h(i,j)\geq 0 dla każdej szczeliny czasowej jjj . Każda osoba może kupić tylko jeden kolejny blok czasu, który może być pusty. Czy istnieje algorytm wielomianowy do obliczania maksymalnej …
6
Czy istnieje fizyczna analogia do maszyny Turinga?
Ostatnio w mojej klasie CS zapoznałem się z Maszyną Turinga. Po zajęciach spędziłem ponad 2 godziny, próbując dowiedzieć się, jaki jest związek między taśmą a maszyną. Byłem całkowicie nieświadomy istnienia taśm komputerowych lub tego, jak taśmy i maszyny współdziałały do ​​dziś. Nadal nie rozumiem, dlaczego maszyna odczytuje taśmy, ale skaner …
5
Praktyczne znaczenie maszyn Turinga?
Jestem inżynierem elektrykiem i 26 lat temu miałem tylko jeden kurs CS na studiach. Jednak jestem również oddanym użytkownikiem Mathematica. Mam wrażenie, że maszyny Turinga są bardzo ważne w informatyce. Czy znaczenie ma tylko w teorii informatyki? Jeśli istnieją praktyczne implikacje / zastosowania, jakie są niektóre z nich?
4
Złożoność czasowa znalezienia średnicy wykresu
Jaka jest złożoność czasowa znalezienia średnicy wykresu ?G = ( V, E)sol=(V.,mi)G=(V,E) O ( | V|2))O(|V.|2)){O}(|V|^2) O ( | V|2)+ | V.| ⋅ | mi| )O(|V.|2)+|V.|⋅|mi|){O}(|V|^2+|V| \cdot |E|) O ( | V|2)⋅ | mi| )O(|V.|2)⋅|mi|){O}(|V|^2\cdot |E|) O ( | V| ⋅ | mi|2))O(|V.|⋅|mi|2)){O}(|V|\cdot |E|^2) Średnica wykresu solsolG jest maksymalnym zbiorem …
12
Dlaczego nadmierne dopasowanie jest złe?
Przebadałem to wiele i mówią, że zbyt złe dopasowanie do uczenia maszynowego jest złe, ale nasze neurony stają się bardzo silne i znajdują najlepsze działania / zmysły, które omijamy lub których unikamy, a ponadto można je zmniejszać / zwiększać od złych / dobry przez złe lub dobre wyzwalacze, co oznacza, …
9
Czy języki programowania stają się bardziej podobne do języków naturalnych?
To pytanie zostało przeniesione z Software Stack Stack Exchange, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 6 lat temu . Czy możemy uczyć się języków programowania w kontekście językoznawstwa? Czy języki programowania ewoluują naturalnie w podobny sposób jak języki naturalne? Chociaż pełna racjonalność i spójność matematyczna …
2
Pokaż, jak wykonać FFT ręcznie
Załóżmy, że masz dwa wielomiany: 3+x3+x3 + x i .2x2+22x2+22x^2 + 2 Próbuję zrozumieć, w jaki sposób FFT pomaga nam pomnożyć te dwa wielomiany. Nie mogę jednak znaleźć żadnych wypracowanych przykładów. Czy ktoś może mi pokazać, jak algorytm FFT pomnożyłby te dwa wielomiany. (Uwaga: nie ma nic specjalnego w tych …
1
Czy regex golf NP-Complete?
Jak widać na ostatnim pasku XKCD i najnowszym poście na bloguwedług Petera Norviga (i opowiadania Slashdota z tym ostatnim) „regex golf” (który można by lepiej nazwać problemem separacji wyrażeń regularnych) jest zagadką polegającą na zdefiniowaniu najkrótszego możliwego wyrażenia regularnego, które akceptuje każde słowo w zestawie A i nie ma słowa …
7
Dlaczego potrzebujemy języka asemblera?
Przeważnie piszemy program w języku wysokiego poziomu. Podczas nauki natknąłem się na język asemblera. Asembler konwertuje język asemblera na język maszynowy, a kompilator robi to samo z językiem wysokiego poziomu. Odkryłem, że język asemblera zawiera instrukcje takie jak move r1 r3, move 5 itp. I raczej trudno się go uczyć. …
7
Dlaczego paradygmat niszczyciela obiektów w językach zbieranych przez śmieci jest nieobecny?
Poszukuję wglądu w decyzje dotyczące projektowania języka w zbieraniu śmieci. Może ekspert językowy mógłby mnie oświecić? Pochodzę z języka C ++, więc ten obszar jest dla mnie zaskakujący. Wydaje się, że prawie wszystkie współczesne języki odśmiecania z obsługą obiektów OOPy, takie jak Ruby, JavaScript / ES6 / ES7, Actionscript, Lua …
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.