Często wchodzę w interakcje z ludźmi, którzy chcą poprosić o algorytm dla problemu obliczeniowego (lub jego złożoności), ale nie wyrażają go w sposób rygorystyczny dla nas (informatyków) do zrozumienia. Odsyłanie ich do książek takich jak CLRS nie jest pomocne, ponieważ tamtejsze przykłady zwykle...
W książce Andrew W. Appela, Modern Compiler Implementation in ML , mówi w rozdziale 17, że teoria obliczalności pokazuje, że zawsze będzie możliwe wynalezienie nowych transformacji optymalizacyjnych i udowadnia, że w pełni optymalizujący kompilator rozwiąże problem zatrzymania: Program Q, który...
Konkretnie: 1) Bezpośrednio odwzorowana pamięć podręczna z 4096 blokami / liniami, w których każdy blok ma 8 32-bitowych słów. Ile bitów potrzeba na pola znaczników i indeksów, przyjmując adres 32-bitowy? 2) To samo pytanie co 1), ale dla w pełni asocjacyjnej pamięci podręcznej ? Popraw mnie,...
Niektóre skomplikowane algorytmy ( szukanie związku ) mają prawie stałą odwrotną funkcję Ackermanna, która pojawia się w asymptotycznej złożoności czasowej, i są optymalne w najgorszym przypadku, jeśli prawie stały odwrotny termin Ackermanna jest ignorowany. Czy istnieją przykłady znanych...
W większości implementacji algorytmów genetycznych nacisk kładziony jest na krzyżowanie i mutację. Ale w jakiś sposób większość z nich pomija diploidalną (dominującą / recesywną) naturę genów. O ile moje (ograniczone) rozumienie dominuje / recesywna natura genów jest bardzo ważnym czynnikiem...
Ok, zanim zacznę, zdaję sobie sprawę, że jest to na marginesie tematu (przeczytałem Pomoc dotyczącą pytań na tej stronie), szczególnie, że nie jest to rzeczywisty problem. Jednak: Nie mogę znaleźć niczego istotnego w Google Z purystycznego punktu widzenia z pewnością musi należeć do...
Wiem, czym jest obliczenie w jakimś niejasnym sensie (tak robią komputery), ale chciałbym bardziej rygorystyczną definicję. Dictionary.comDefinicje obliczeń, obliczeń, obliczeń i obliczeń są okrągłe, więc to nie pomaga. Wikipediadefiniuje obliczenia jako „każdy rodzaj obliczeń zgodny z dobrze...
To jest ogólne pytanie. A jeśli ktoś chce sprecyzować tę implementację, wolę rzeczy związane z Uniksem. Ale najpierw trzeba znać następujące problemy w ogólności: Czytam, że pojedynczy proces może mieć wiele wątków. Wiele wątków tego samego procesu dzieli się między nimi. Chcę wiedzieć, co dzielą,...
Często słyszę, że polimorfizm szeregowy jest lepszym podejściem niż podliczanie, ale mam trudności ze znalezieniem czegokolwiek porównującego je szczegółowo. Szczególnie interesuje mnie perspektywa użytkownika systemu. Natrafiłem na ten post na blogu, ale pozostawia mi więcej pytań niż wcześniej....
Właśnie poza zainteresowaniem próbowałem rozwiązać problem z kategorii „Ostatnie” projektu Euler ( sekwencja sumy cyfr ). Ale nie jestem w stanie wymyślić sposobu skutecznego rozwiązania problemu. Problem jest następujący (w oryginalnej sekwencji pytań ma dwie na początku, ale nie zmienia...
Porównując parę uporządkowaną (x, y) z parą nieuporządkowaną {x, y} (zestaw), a następnie teoretycznie, różnica wynosi tylko jeden bit, ponieważ to, czy x jest pierwsze, czy y wymaga dokładnie jednego bitu do przedstawienia. Więc jeśli otrzymamy zestaw {x, y}, gdzie x, y to dwie różne 32-bitowe...
Artykuł zatytułowany The Derivative of a Regular Type to Type One-Hole Contexts pokazuje, że „zamek błyskawiczny” typu - jego konteksty z jedną dziurą - są zgodne z regułami różnicowania w algebrze typów. Mamy: ∂xx∂x0∂x1∂x( S+ T)∂x( S× T)↦ 1↦ 0↦ 0↦ ∂xS.+ ∂xT.↦ ∂xS.× T+ S×...
Szukam struktury danych, która wypchnie jej najstarszy / ostatni element, jeśli wstawiony zostanie nowy element. Na przykład niech Dreprezentuje strukturę. Dzawiera 3 elementy Number Dwartości domyślnych tego typu będą inicjowane do 1, 2i 3. D=[1,2,3]D=[1,2,3]D = [1, 2, 3] Jeśli Numberto zawiera...
Operator różnicy zbiorów (np. EXCEPTW niektórych wariantach SQL) jest jednym z wielu podstawowych operatorów algebry relacyjnej. Istnieją jednak bazy danych, które nie obsługują bezpośrednio operatora różnicy setów, ale które obsługują LEFT JOIN(rodzaj połączenia zewnętrznego), aw praktyce można...
Wiele odniesień do systemów operacyjnych mówi, że w przypadku wielozadaniowości kooperacyjnej (w przeciwieństwie do zapobiegawczej) proces utrzymuje procesor do momentu, aż jawnie się dobrowolnie zawiesi. Jeśli uruchomiony proces wykonuje żądanie we / wy, którego nie można natychmiast zaspokoić...
Zaczynam osobiste badanie bibliograficzne algorytmów sprawdzania typu i chcę uzyskać wskazówki. Jakie są najczęściej stosowane algorytmy sprawdzania typu, strategie i techniki ogólne? Szczególnie interesują mnie złożone algorytmy sprawdzania typu, które zostały zaimplementowane w powszechnie...
Od jakiegoś czasu pracuję nad programowaniem dynamicznym. Kanonicznym sposobem oceny dynamicznej rekurencji programowania jest utworzenie tabeli wszystkich niezbędnych wartości i wypełnienie jej wiersz po wierszu. Zobacz na przykład Cormen, Leiserson i in .: „Wprowadzenie do algorytmów” . Skupiam...
W książce Sipsera „Wprowadzenie do teorii obliczeń” na stronie 286 zmniejszono z 3SAT do problemu ścieżki Hamiltona. Czy istnieje prostsza redukcja? Mówiąc prościej, mam na myśli redukcję, która byłaby łatwiejsza do zrozumienia (dla studentów). Czy istnieje redukcja wykorzystująca liniową...
Jestem studentem kończącym kurs teorii teorii i mam poważne problemy z tworzeniem treści, gdy tylko o to poproszę. Potrafię śledzić podręcznik (Wstęp do teorii obliczeń Michaela Sipsera) i wykłady; jednak kiedy poproszono mnie o udowodnienie czegoś lub sformułowanie formalnego opisu konkretnej bazy...
Nasz profesor poprosił nas o przemyślenie funkcji w OCaml, która ma ten typ 'a -> 'b tj. funkcja jednego argumentu, który może być czymkolwiek, i który może zwrócić coś innego. Myślałem o użyciu raisefunkcji, która ignoruje jej argument: let f x = raise Exit Ale profesor powiedział, że...