Teoretyczne informatyka

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

9
Potężne algorytmy zbyt skomplikowane do wdrożenia
Jakie są algorytmy legalnej użyteczności, które są po prostu zbyt skomplikowane, aby je zaimplementować? Wyjaśnię: nie szukam algorytmów takich jak obecny asymptotyczny algorytm optymalnego mnożenia macierzy (Coppersmith-Winograd), który jest rozsądny do wdrożenia, ale ma stałą, która czyni go bezużytecznym w praktyce. Szukam algorytmów, które mogłyby mieć praktyczną wartość, ale są …
13
Zastosowania struktur algebraicznych w informatyce teoretycznej
Jestem praktykiem oprogramowania i piszę ankietę na temat struktur algebraicznych do badań osobistych i staram się przedstawić przykłady wykorzystania tych struktur w informatyce teoretycznej (oraz, w mniejszym stopniu, w innych dziedzinach informatyki) . W ramach teorii grup natknąłem się na monoidy syntaktyczne dla języków formalnych oraz monoidy śledzenia i historii …
7
Jakie interesujące twierdzenia w TCS opierają się na Axiom of Choice? (Lub alternatywnie, aksjomat determinacji?)
Matematycy czasem martwią się o aksjomat wyboru (AC) i aksjomat determinacji (AD). Aksjomat wyboru : Biorąc pod uwagę dowolny zbiór z niepustych zestawach jest funkcja , które, biorąc pod uwagę zestaw w , zwraca element z .CC{\cal C}fffSSSCC{\cal C}SSS Aksjomat Determinacji : Niech będzie zbiorem nieskończenie długich ciągów bitów. Alice …
7
Czy problemy związane z są z natury mniej podatne na rozwiązanie niż problemy z ?
Obecnie rozwiązanie NPNPNP pełnego NP lub PSPACEPSPACEPSPACE jest niewykonalne w ogólnym przypadku dużych nakładów. Jednak oba można rozwiązać w czasie wykładniczym i przestrzeni wielomianowej. Skoro nie jesteśmy w stanie zbudować niedeterministycznych lub „szczęśliwych” komputerów, czy ma to dla nas jakąkolwiek różnicę, jeśli problemem jest NPNPNP lub PSPACEPSPACEPSPACE -kompletny?
12
Jak ważna jest umiejętność programowania w TCS?
Pochodząc z matematyki, tak naprawdę nigdy nie nauczyłem się kodować. Zaczynam doktorat z TCS i wiele osób było zaskoczonych tym, jak mało wiedziałem o programowaniu (i ogólnie o komputerze). Mogę pisać algorytmy w pseudo-kodzie, ale tak naprawdę nie znam żadnego języka programowania. Mogę sobie wyobrazić, że pewnego dnia będę musiał …
1
Więcej na temat PH w PP?
Ostatnie pytanie za pytaniem, czy Huck Bennett PH klasa została zawarta w PP klasy, otrzymał nieco sprzecznych odpowiedzi (wszystko prawda, wydaje się). Z jednej strony podano przeciwnie kilka wyników wyroczni, z drugiej Scott zasugerował, że odpowiedź jest prawdopodobnie pozytywna, ponieważ twierdzenie Tody pokazuje, że PH jest w BP.PP, wariancie probabilistycznym …
11
Powszechne fałszywe przekonania w informatyce teoretycznej
EDYCJA PRZY 10/12/08: Spróbuję zmodyfikować pytanie, aby zainteresować większą liczbą osób dzieleniem się opiniami. POTRZEBUJEMY twoich datków! Ten post jest inspirowany jednym z MO: Przykłady powszechnych fałszywych przekonań w matematyce . Wielkie listy czasami generują ogromną liczbę odpowiedzi, których jakości trudno jest kontrolować, ale po sukcesie powiązanego postu na MO …
3
Jak sędziować artykuł?
Zaktualizowano poniżej Wszyscy znamy kluczowe znaczenie wzajemnej oceny. Jest to główna forma kontroli jakości i informacji zwrotnej na temat badań. Jednak dla początkującego badacza (takiego jak ja) może to być czasem mylący system / proces. W związku z tym istnieje kilka traktatów na temat naukowego procesu sędziowania, które zawierają wskazówki. …
5
Geneza pojęcia treewidth
Moje dzisiejsze pytanie jest (jak zwykle) trochę głupie; ale prosiłbym cię o pomyślne rozważenie. Chciałem wiedzieć o genezie i / lub motywacji leżącej u podstaw koncepcji treewidth. Z pewnością rozumiem, że jest on stosowany w algorytmach FPT, ale nie sądzę, że to był powód, dla którego zdefiniowano to pojęcie. Pisałem …
14
Zastosowania topologii w informatyce
Chciałbym napisać ankietę na temat zastosowań topologii w informatyce. Planuję opisać historię pomysłów topologicznych w dziedzinie informatyki, a także zwrócić uwagę na kilka aktualnych osiągnięć. Byłoby niezwykle pomocne, gdyby ktokolwiek mógł udzielić informacji na temat któregokolwiek z poniższych pytań. Czy są jakieś prace lub notatki opisujące chronologię wykorzystania topologii w …
30
Małe kroki dla lepszych konferencji TCS?
Często, gdy bierzemy udział w konferencjach TCS, zauważamy kilka drobiazgów, którymi chcielibyśmy się zająć organizatorzy konferencji. A kiedy organizujemy konferencje, już o tym zapomnieliśmy. Stąd pytanie: jakie małe kroki moglibyśmy łatwo podjąć, aby usprawnić konferencje TCS ? Mam nadzieję, że to pytanie może stać się zasobem, który moglibyśmy dwukrotnie sprawdzić …
17
Zastosowania TCS w matematyce klasycznej?
W TCS często używamy potężnych wyników i pomysłów z matematyki klasycznej (algebry, topologii, analizy, geometrii itp.). Jakie są przykłady sytuacji, w której sytuacja się odwróciła? Oto niektóre, o których wiem (a także, aby dać smak wyników, o które pytam): Sześcienne pianki (Guy Kindler, Ryan O'Donnell, Anup Rao i Avi Wigderson: …
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.