Informatyka

6

Jak możemy założyć, że podstawowe operacje na liczbach wymagają stałego czasu?

Zwykle w algorytmach nie dbamy o porównywanie, dodawanie lub odejmowanie liczb - zakładamy, że działają one w czasie O ( 1 )O(1)O(1) . Na przykład zakładamy, że mówimy, że sortowanie na podstawie porównania to O ( n logn )O(nlog⁡n)O(n\log n) , ale gdy liczby są zbyt duże, aby zmieścić się …

73 algorithms complexity-theory algorithm-analysis time-complexity reference-question

9

Dlaczego dodawanie jest tak szybkie, jak operacje bitowe w nowoczesnych procesorach?

Wiem, że operacje bitowe są tak szybkie na nowoczesnych procesorach, ponieważ mogą działać równolegle na 32 lub 64 bitach, więc operacje bitowe zajmują tylko jeden cykl zegara. Jednak dodawanie jest złożoną operacją, która składa się z co najmniej jednej, a być może nawet kilkunastu operacji bitowych, więc naturalnie myślałem, że …

72 computer-architecture arithmetic circuits cpu digital-circuits

9

Jakie właściwości języka programowania uniemożliwiają kompilację?

Pytanie: „Niektóre właściwości języka programowania mogą wymagać, aby jedynym sposobem na napisanie w nim kodu jest interpretacja. Innymi słowy, kompilacja do natywnego kodu maszynowego tradycyjnego procesora nie jest możliwa. Jakie są te właściwości?” Kompilatory: zasady i praktyka Parag H. Dave i Himanshu B. Dave (2 maja 2012) Książka nie daje …

71 programming-languages compilers interpreters

4

(Kiedy) to wyszukiwanie tablicy skrótów O (1)?

Często mówi się, że wyszukiwanie tablicy skrótów działa w stałym czasie: obliczasz wartość skrótu, co daje indeks dla wyszukiwania tablicy. Jednak ignoruje to kolizje; w najgorszym przypadku każdy przedmiot ląduje w tym samym wiadrze, a czas wyszukiwania staje się liniowy ( ).Θ ( n )Θ(n)\Theta(n) Czy istnieją warunki dotyczące danych, …

70 algorithm-analysis data-structures runtime-analysis hash-tables

3

W jaki sposób komputery śledzą czas?

W jaki sposób komputery są w stanie podać prawidłową godzinę i datę za każdym razem? Ilekroć zamykam komputer (zamykam go), wszystkie połączenia i procesy w nim zatrzymują się. Jak to się dzieje, że kiedy ponownie otwieram komputer, podaje on dokładny właściwy czas? Czy komputer nie wyłącza się całkowicie po wyłączeniu? …

68 computer-architecture clocks

6

Dlaczego maszyna Turinga jest popularnym modelem obliczeniowym?

Jestem studentem CS. Rozumiem, jak Turing wymyślił swoją abstrakcyjną maszynę (modelującą osobę wykonującą obliczenia), ale wydaje mi się to niewygodną, nieelegacyjną abstrakcją. Dlaczego uważamy „taśmę” i maszynę piszącą symbole, zmieniającą stan, przesuwającą taśmę tam iz powrotem? Jakie jest podstawowe znaczenie? DFA jest elegancki - wydaje się, że dokładnie przechwytuje to, …

67 turing-machines computation-models

4

Jaka jest nowość w MapReduce?

Kilka lat temu MapReduce został okrzyknięty rewolucją programowania rozproszonego. Byli też krytycy, ale ogólnie był entuzjastyczny szum. Zostało nawet opatentowane! [1] Nazwa nawiązuje mapi reduceprogramowania funkcjonalnego, ale kiedy czytam (Wikipedia) Krok mapy: węzeł główny pobiera dane wejściowe, dzieli je na mniejsze podproblemy i rozdziela je na węzły robocze. Węzeł roboczy …

67 algorithms distributed-systems parallel-computing algorithm-design

2

Co to jest koindukcja?

Słyszałem o indukcji (strukturalnej). Pozwala budować struktury skończone z mniejszych i zapewnia zasady dowodowe dla uzasadnienia takich struktur. Pomysł jest wystarczająco jasny. A co z koindukcją? Jak to działa? Jak można powiedzieć coś rozstrzygającego o nieskończonej strukturze? Są (przynajmniej) dwa kąty, którymi należy się zająć, a mianowicie koindukcja jako sposób …

67 terminology logic proof-techniques formal-methods coinduction

1

Teoretyczne porównanie gramatyk LL i LR

Ludzie często mówią, że parsery LR (k) są silniejsze niż parsery LL (k) . Te stwierdzenia są przez większość czasu niejasne; w szczególności, czy powinniśmy porównać klasy dla ustalonego kkk lub unii dla całego kkk ? Jak więc naprawdę wygląda sytuacja? W szczególności jestem zainteresowany tym, jak pasuje LL (*). …

66 formal-languages formal-grammars parsers reference-question

6

Formalna weryfikacja programu w praktyce

Jako inżynier oprogramowania piszę dużo kodu dla produktów przemysłowych. Stosunkowo skomplikowane rzeczy z klasami, wątkami, trochę wysiłków projektowych, ale także pewne kompromisy w zakresie wydajności. Robię dużo testów i mam dość testowania, więc zainteresowałem się narzędziami do sprawdzania formalnego, takimi jak Coq, Isabelle ... Czy mogę użyć jednego z nich, …

66 programming-languages program-correctness software-verification

7

Czy ustawodawstwo NP jest kompletne?

Chciałbym wiedzieć, czy były prace związane z kodeksem prawnym złożoności. W szczególności, przypuśćmy, że mamy problem decyzyjny „Czy biorąc pod uwagę tę książkę prawniczą i ten szczególny zestaw okoliczności, pozwany jest winny?” Do jakiej klasy złożoności należy? Są wyniki, które dowiodły, że gra karciana Magic: the Gathering jest zarówno NP, …

64 complexity-theory np-complete decision-problem

14

Jak mam wytłumaczyć rodzicom, że uczę się języków programowania?

Obecnie kończę mgr informatyki. Interesuję się językami programowania, szczególnie systemami typu. Zainteresowałem się badaniami w tej dziedzinie i w następnym semestrze rozpocznę doktorat na ten temat. Oto prawdziwe pytanie: jak mogę wyjaśnić, co (chcę) zrobić osobom bez wcześniejszej wiedzy w dziedzinie informatyki lub dziedzin pokrewnych? Tytuł pochodzi od faktów, że …

64 programming-languages education typing research

10

Czy dynamiczny język, taki jak Ruby / Python, może osiągnąć wydajność podobną do C / C ++?

Zastanawiam się, czy można zbudować kompilatory dla dynamicznych języków, takich jak Ruby, aby mieć podobną i porównywalną wydajność do C / C ++? Z tego, co rozumiem na temat kompilatorów, weźmy na przykład Ruby, kompilowanie kodu Ruby nigdy nie będzie wydajne, ponieważ sposób, w jaki Ruby obsługuje odbicie, funkcje takie …

64 programming-languages compilers

12

Dlaczego kompilatory nie wstawiają automatycznie zwolnień?

W językach takich jak C programista powinien wstawiać połączenia za darmo. Dlaczego kompilator nie robi tego automatycznie? Ludzie robią to w rozsądnym czasie (ignorując błędy), więc nie jest to niemożliwe. EDYCJA: Dla przyszłego odniesienia, oto kolejna dyskusja, która ma ciekawy przykład.

63 compilers memory-management garbage-collection

3

Algorytm na miejscu do przeplatania tablicy

Otrzymujesz tablicę elementów2n2n2n a1,a2,…,an,b1,b2,…bna1,a2,…,an,b1,b2,…bna_1, a_2, \dots, a_n, b_1, b_2, \dots b_n Zadanie polega na przeplataniu tablicy przy użyciu algorytmu lokalnego, takiego jak tablica wynikowa b1,a1,b2,a2,…,bn,anb1,a1,b2,a2,…,bn,anb_1, a_1, b_2, a_2, \dots , b_n, a_n Gdyby nie istniał wymóg lokalny, moglibyśmy łatwo utworzyć nową tablicę i skopiować elementy, dając algorytm czasowy .O(n)O(n)\mathcal{O}(n) Z …

62 algorithms arrays permutations in-place