Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

6
Co nowego w czysto funkcjonalnych strukturach danych od czasu Okasaki?
Od czasu książki Chrisa Okasakiego z 1998 r. „Czysto funkcjonalne struktury danych”, nie widziałem zbyt wielu nowych ekscytujących czysto funkcjonalnych struktur danych; Mogę wymienić tylko kilka: IntMap (również wynaleziony przez Okasaki w 1998 r., Ale nieobecny w tej książce) Drzewa palcowe (i ich uogólnienie na monoidy) Istnieje również kilka interesujących …
30
Jakie artykuły każdy powinien przeczytać?
To pytanie jest (zainspirowane) / (wstydliwie skradzione) podobnym pytaniem w MathOverflow , ale spodziewam się, że odpowiedzi tutaj będą zupełnie inne. Wszyscy mamy ulubione artykuły z naszych własnych obszarów teorii. Od czasu do czasu pojawia się artykuł tak zdumiewający (np. Ważny, przekonujący, zwodniczo prosty itp.), Że chce się nim dzielić …
30
Algorytmy z książki.
Paul Erdos mówił o „Księdze”, w której Bóg przechowuje najbardziej elegancki dowód każdego twierdzenia matematycznego. To nawet zainspirowało książkę (która, jak sądzę, jest teraz w czwartym wydaniu): Dowody z książki . Gdyby Bóg miał podobną książkę na temat algorytmów, jaki według ciebie algorytm byłby kandydatem (kandydatami)? Jeśli to możliwe, proszę …
29
Wdrożone podstawowe algorytmy
Aby zademonstrować znaczenie algorytmów (np. Dla studentów i profesorów, którzy nie zajmują się teorią lub nawet pochodzą z zupełnie innych dziedzin), czasem warto mieć pod ręką listę przykładów, w których podstawowe algorytmy zostały zastosowane w celach komercyjnych, rządowych, lub powszechnie używane oprogramowanie / sprzęt. Szukam takich przykładów, które spełniają następujące …
11
Jakie oświecenie powinienem osiągnąć po przestudiowaniu automatów skończonych?
Przeglądam teorię obliczeń dla zabawy i to pytanie nęka mnie od dłuższego czasu (zabawne, że nie pomyślałem o tym, gdy nauczyłem się teorii automatu w mojej szkole licencjackiej). Więc „dlaczego” dokładnie badamy deterministyczne i niedeterministyczne automaty skończone (DFA / NFA)? Oto kilka odpowiedzi, które wymyśliłem po monologowaniu, ale wciąż nie …
30
Jakie książki każdy powinien przeczytać?
[ Oś czasu ] To pytanie ma ten sam duch, co artykuły powinny przeczytać wszyscy i jakie filmy wszyscy powinni oglądać . Prosi o niezwykłe książki z różnych dziedzin informatyki teoretycznej. Książki mogą być zorientowane na matematykę, ale mogą się okazać przydatne dla informatyków. Przykłady: Prawdopodobieństwo Nierówności Logika Teoria grafów …
2
Problem z Super Mario Galaxy
Załóżmy, że Mario chodzi po powierzchni planety. Jeśli zacznie chodzić ze znanego miejsca, w ustalonym kierunku, na określoną odległość, jak szybko możemy ustalić, gdzie się zatrzyma? Bardziej formalnie, załóżmy, że otrzymujemy wypukły politop w 3-przestrzeni, punkt początkowy na powierzchni , wektor kierunku (w płaszczyźnie pewnej ścianki zawierającej ) i odległość …
30
Jakie filmy wszyscy powinni oglądać?
Uniwersytet Stanforda ma teraz kanał na Youtube , z bezpłatnym dostępem do filmów HD z pełnymi kursami na wszystko, od systemów dynamicznych po splątanie kwantowe. Więcej konferencji i warsztatów nagrywa swoje rozmowy wideo. Jakie są filmy online, o których Twoim zdaniem każdy powinien wiedzieć? Posadzę to kilkoma odpowiedziami na prezentacje, …
28
Problemy między P a NPC
Rozkładanie na czynniki i izomorfizm wykresów są problemami w NP, o których nie wiadomo, że są w P ani w NP-kompletne. Jakie są inne (wystarczająco różne) naturalne problemy, które dzielą tę właściwość? Sztuczne przykłady pochodzące bezpośrednio z dowodu twierdzenia Ladnera się nie liczą. Czy którykolwiek z tych przykładów może być …
13
Porady dotyczące dobrych praktyk badawczych
Po przeczytaniu pytania Daniela Apona zacząłem myśleć, że przydałoby się (szczególnie młodym naukowcom i absolwentom, takim jak ja), zadać szersze i bardziej ogólne pytanie, abyśmy mogli wyciągnąć wnioski z doświadczenia starszych naukowców. Oto pytanie: Jakie praktyki uważasz za najbardziej przydatne w swoich badaniach? Nie chcę ograniczać się do żadnej konkretnej …
11
Jak trudne jest tasowanie sznurka?
Losowanie dwóch ciągów znaków polega na przeplataniu znaków w nowy ciąg znaków, utrzymując porządek znaków każdego łańcucha. Na przykład, MISSISSIPPIjest losowanie MISIPPi SSISI. Nazwijmy kwadrat ciągów, jeśli jest to tasowanie dwóch identycznych ciągów. Na przykład ABCABDCDjest kwadratowy, ponieważ jest to przetasowanie ABCDi ABCD, ale ciąg ABCDDCBAnie jest kwadratowy. Czy istnieje …
15
Jakie notatki z wykładu powinien przeczytać każdy?
Było kilka pytań o tym samym schemacie jak ten: Jakie gazety każdy powinien przeczytać Jakie książki każdy powinien przeczytać Jakie są najnowsze książki TCS, których wersje robocze są dostępne online jakie filmy wszyscy powinni oglądać Nie chciałem publikować jeszcze jednego, ale notatki z wykładów na temat algorytmów Jeffa Ericksona zmieniły …
17
Przykłady ceny abstrakcji?
Informatyka teoretyczna dostarczyła kilka przykładów „ceny abstrakcji”. Dwa najbardziej znaczące dotyczą eliminacji i sortowania Gaussa. Mianowicie: Wiadomo, że eliminacja Gaussa jest optymalna do, powiedzmy, obliczenia wyznacznika, jeśli ograniczysz operacje do wierszy i kolumn jako całości [1]. Oczywiście algorytm Strassena nie przestrzega tego ograniczenia i jest asymptotycznie lepszy niż eliminacja Gaussa. …
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.