Teoretyczne informatyka

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

3
Dlaczego analiza Fouriera funkcji boolowskich „działa”?
Przez lata przyzwyczaiłem się do tego, że wiele twierdzeń TCS zostało udowodnionych przy użyciu dyskretnej analizy Fouriera. Transformacja Walsha-Fouriera (Hadamarda) jest przydatna w praktycznie każdym podpolu TCS, w tym w testowaniu właściwości, pseudolosowości, złożoności komunikacji i obliczeniach kwantowych. Podczas gdy czułem się dobrze, stosując analizę Fouriera funkcji boolowskich jako bardzo …
10
Czy pozostały jakieś otwarte problemy związane z DFA?
Po przestudiowaniu deterministycznych automatów skończonych (DFA) w undergrad poczułem, że są one bardzo dobrze rozumiane. Moje pytanie brzmi, czy jest coś, czego wciąż nie rozumiemy. Nie mam na myśli uogólnień DFA, ale oryginalne niezmodyfikowane DFA, które badamy w studiach licencjackich. To jest niejasne pytanie, ale mam nadzieję, że masz pomysł. …
7
Jak zestrzelić swoje dowody
Jakie są ogólne wytyczne dotyczące sprawdzania twoich dowodów? Uważam, że jest to ważne dla absolwentów takich jak ja. Wiem już, co musimy zrobić, aby coś udowodnić, ale zawsze musisz wszystko sprawdzić przed wysłaniem. Nawet do twojego własnego doradcy. Opracowałem sobie strategie metodą prób i błędów i otrzymałem wiele porad od …
8
Jaka klasa złożoności jest najbardziej związana z tym, co ludzki umysł może szybko osiągnąć?
Zastanawiam się nad tym pytaniem. Kiedy ludzie opisują problem P vs. NP, często porównują NP klasy do kreatywności. Zauważają, że skomponowanie symfonii jakości Mozarta (analogicznej do zadania NP) wydaje się znacznie trudniejsze niż sprawdzenie, czy już skomponowana symfonia ma jakość Mozarta (analogiczną do zadania P). Ale czy NP to naprawdę …
4
Dowody na to, że mnożenie macierzy można przeprowadzić w czasie kwadratowym?
Powszechnie przypuszcza się, że , optymalny wykładnik mnożenia macierzy, w rzeczywistości jest równy 2. Moje pytanie jest proste:ωω\omega Jakie mamy powody, by sądzić, że ?ω=2ω=2\omega = 2 Mam świadomość szybkich algorytmów, takich jak Coppersmith-Winograd, ale nie wiem, dlaczego można je uznać za dowód na .ω=2ω=2\omega = 2 Naiwnie wydaje mi …
6
Jak znaleźć pracę
Jestem nowy na stronie. Na mathoverflow byłoby to wiki społeczności, ale nie widzę, jak to tutaj ustawić. Nie pytanie badawcze, ale miejmy nadzieję, że zainteresuje profesjonalnych teoretycznych informatyków. Teoretycznie jestem studentem drugiego roku i zastanawiałem się, jaką radę ma społeczność w kwestii tego, co powinienem teraz robić, aby osiągnąć karierę …
10
Jeden stos, dwie kolejki
tło Kilka lat temu, kiedy byłem studentem, otrzymaliśmy zadanie domowe z analizy zamortyzowanej. Nie udało mi się rozwiązać jednego z problemów. Poprosiłem o to w teorii porównawczej , ale nie uzyskałem zadowalającego rezultatu. Pamiętam kurs, który TA nalegał na coś, czego nie mógł udowodnić, i powiedział, że zapomniał dowodu i …
15
Czasopisma z otwartym dostępem
Wraz z pojawieniem się Internetu (i zdrowego rozsądku) rośnie zapotrzebowanie na badania o otwartym dostępie. Kilku badaczy (w tym ja) uważa za frustrujące, że opublikowane artykuły naukowe recenzowane są za ścianami płatnymi. Szukam czasopism i konferencji (związanych z informatyką teoretyczną, teorią grafów, kombinatoryką, optymalizacją kombinatoryczną), które udostępniłyby wszystkim akceptowanym publikacjom …
13
Otwarte problemy na granicach TCS
W wątku Główne nierozwiązane problemy w informatyce teoretycznej? Iddo Tzameret napisał następujący doskonały komentarz: Myślę, że powinniśmy rozróżnić między głównymi otwartymi problemami, które są postrzegane jako podstawowe problemy, takie jak P≠NPP≠NP P\neq NP , i głównymi otwartymi problemami, które będą stanowić przełom techniczny, jeśli zostaną rozwiązane, ale niekoniecznie tak fundamentalne, …
5
Nadrzędne powody, dla których problemy występują w P lub BPP
Niedawno, rozmawiając z fizykiem, twierdziłem, że z mojego doświadczenia, kiedy problem, który naiwnie wydaje się, że powinien on zająć wykładniczy czas, okazuje się niekoniecznie w P lub BPP, „nadrzędny powód”, dla którego redukcja może być zazwyczaj zidentyfikowany --- i prawie zawsze powód ten należy do listy kilkunastu „zwykłych podejrzanych” (na …
10
Sprawdzalne stwierdzenia na temat algorytmów genetycznych
Algorytmy genetyczne nie cieszą się dużą popularnością w świecie teorii, ale są one dość dobrze stosowaną metodą metaheurystyczną (przez metaheurystyczny mam na myśli technikę, która ogólnie stosuje się w wielu problemach, takich jak wyżarzanie, opadanie gradientu i tym podobne). W rzeczywistości technika podobna do GA jest dość skuteczna w przypadku …
4
Dlaczego 2SAT w P?
Natknąłem się na algorytm wielomianowy, który rozwiązuje 2SAT. Uważam za zaskakujące, że 2SAT znajduje się w P, gdzie wszystkie (lub wiele innych) instancji SAT są NP-Complete. Co wyróżnia ten problem? Co sprawia, że ​​jest to takie proste (NL-Complete - nawet łatwiejsze niż P)?
14
Gdzie i jak komputery pomogły udowodnić twierdzenie?
Celem tego pytania jest zebranie przykładów z teoretycznej informatyki, w której pomocne było systematyczne korzystanie z komputerów budując przypuszczenie, które prowadzi do twierdzenia, fałszowanie przypuszczeń lub podejścia dowodowego, konstruowanie / weryfikacja (części) dowodu. Jeśli masz konkretny przykład, opisz, jak to zrobiono. Być może pomoże to innym w bardziej efektywnym korzystaniu …
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.