Pytania otagowane jako reference-request

Pytania wymagające literatury na temat konkretnych, wąskich zagadnień.

2
Teoretyczne podstawy podziału i podboju
Przy projektowaniu algorytmów często stosuje się następujące techniki: Programowanie dynamiczne Chciwa strategia Dziel i rządź Podczas gdy w przypadku dwóch pierwszych metod istnieją dobrze znane podstawy teoretyczne, a mianowicie zasada optymalności Bellmana i teoria matroidów (odpowiednio greedoid), nie mogłem znaleźć takiej ogólnej struktury algorytmów opartych na D&C. Po pierwsze, zdaję …
4
Rezerwuj algorytmy poza Cormen
Skończyłem większość materiału w książce Cormen's Intro to Algorytmy i szukam książki o algorytmach, która obejmowałaby materiał poza książką Cormana. Czy są jakieś rekomendacje? UWAGA: Zapytałem o to przy przepełnieniu stosu, ale nie byłem zbyt zadowolony z odpowiedzi. UWAGA: Patrząc na większość komentarzy, myślę, że idealnie chciałbym znaleźć książkę, która …
3
Jak rygorystycznie sformułować problem obliczeniowy?
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 mają dość prosty sposób rygorystycznego określania, np. …
1
Bezblokowe, stałe struktury drzew współbieżnych w czasie aktualizacji?
Ostatnio czytałem trochę literatury i znalazłem dość interesujące struktury danych. Badałem różne metody skrócenia czasów aktualizacji do najgorszego przypadku [1-7].O(1)O(1)\mathcal{O}(1) Ostatnio zacząłem szukać struktur danych bez blokowania, aby wspierać efektywny równoczesny dostęp. Czy przy wdrażaniu struktur danych bez blokowania zastosowano jedną z tych najgorszych technik aktualizacji czasu ?O(1)O(1)\mathcal{O}(1) Pytam, ponieważ; …
1
Klasyfikacja trudnych do rozwiązania / możliwych do rozwiązania wariantów problemu satysfakcji
Ostatnio znalazłem w artykule [1] specjalną symetryczną wersję SAT o nazwie 2/2/4-SAT . Ale istnieje wiele wariantów kompletnych , na przykład: MONOTONE NAE-3SAT , MONOTONE 1-IN-3-SAT , ...NPNP\text{NP} Możliwe są inne warianty: - SAT , Planar-NAE- SAT , ...222SATSAT\text{SAT}SATSAT\text{SAT} Czy istnieją artykuły ankietowe (lub strony internetowe), które klasyfikują wszystkie (dziwne) …
4
Używasz ludzi jako komponentów do budowy komputera?
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 informatyki? W każdym razie, jeśli przekroczyłem granicę, …
3
Czy funkcje o wolniejszym wzroście niż odwrotny Ackermann pojawiają się w granicach środowiska wykonawczego?
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 algorytmów z czasami działania, które obejmują funkcje, które rosną zasadniczo wolniej niż …
1
Problemy, dla których algorytmy oparte na zawężaniu partycji działają szybciej niż w czasie logarytmicznym
Udoskonalenie partycji to technika, w której zaczynasz od skończonego zestawu obiektów i stopniowo dzielisz zestaw. Niektóre problemy, takie jak minimalizacja DFA, można rozwiązać dość skutecznie za pomocą zawężania partycji. Nie znam żadnych innych problemów, które zwykle rozwiązuje się za pomocą udoskonalenia partycji innych niż te wymienione na stronie Wikipedii. Spośród …
2
Czy drzewa cięte łączem są kiedykolwiek wykorzystywane w praktyce do obliczeń maksymalnego przepływu lub innych zastosowań?
Wiele algorytmów maksymalnego przepływu, które zwykle widzę zaimplementowanych, algorytm Dinica, push push i inne, mogą mieć asymptotyczny koszt czasu ulepszony dzięki zastosowaniu dynamicznych drzew (znanych również jako drzewa cięte łączem). Wciśnij etykietę w trybie lub O ( V 3 ) lub O ( V 2 √)O ( V2)mi)O(V.2)mi)O(V^2E)O ( V3))O(V.3))O(V^3)normalnie, …
1
Kto ukuł termin „uczenie maszynowe”?
Próbuję dowiedzieć się, kto stworzył termin „uczenie maszynowe”. Dodatkowe pytanie brzmi: skąd Arthur Samuel cytował określenie „uczenia maszynowego” w 1959 r. Jako: dziedzina nauki, która daje komputerom możliwość uczenia się bez wyraźnego programowania ? W Internecie można znaleźć wiele odniesień do tej definicji, ale nie udało mi się wyśledzić źródła. …
3
Deterministyczny algorytm czasu liniowego do sprawdzania, czy jedna tablica jest posortowaną wersją drugiej
Rozważ następujący problem: Dane wejściowe: dwie tablice i o długości , gdzie jest posortowane.B n BAAABBBnnnBBB Pytanie: czy i zawierają te same elementy (z ich wielokrotnością)?B.AAABBB Jaki jest najszybszy algorytm deterministyczny dla tego problemu? Czy można to rozwiązać szybciej niż ich sortowanie? Czy ten problem można rozwiązać w deterministycznym czasie …
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.