Teoretyczne informatyka

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

16
Trudno wyglądające problemy algorytmiczne ułatwiane przez twierdzenia
Szukam ładnych przykładów, w których występuje następujące zjawisko: (1) Problem algorytmiczny wygląda na trudny, jeśli chcesz go rozwiązać, korzystając z definicji i używając tylko standardowych wyników. (2) Z drugiej strony staje się łatwe, jeśli znasz jakieś (nie tak standardowe) twierdzenia. Ma to na celu zilustrowanie uczniom, że uczenie się większej …
2
Jak opublikować artykuł?
Będąc inżynierem oprogramowania przez większą część mojego życia, nie mam absolutnie pojęcia, jak zacząć od opublikowania „akademickiego” rodzaju pracy. Podczas moich ostatnich badań znalazłem interesujący algorytm dla zadania, które rozwiązałem (związane z niektórymi obliczeniami na rynkach finansowych). Nie jest to świetny wynik, ale myślę, że może być interesujący dla osób …
8
Jaka jest minimalna liczba bitów wymagana do przechowywania układanki sudoku?
Uwaga: chodzi o standardową łamigłówkę sudoku 9x9. Rozwiązanie musi obsługiwać tylko rozwiązane, legalne zagadki . Dlatego rozwiązanie nie musi obsługiwać pustych komórek i może polegać na właściwościach rozwiązanej łamigłówki sudoku. Zastanawiałem się nad tym, ale nie mogłem wymyślić odpowiedzi, z której byłbym zadowolony. Naiwne rozwiązanie wykorzystywałoby jeden bajt na każdą …
5
Szybka redukcja z RSA do SAT
Wpis na blogu Scotta Aaronsona przedstawił dziś listę interesujących otwartych problemów / zadań w złożoności. Jeden zwrócił moją uwagę: Zbuduj bibliotekę publiczną instancji 3SAT z jak najmniejszą liczbą zmiennych i klauzul, które mogłyby mieć godne uwagi konsekwencje, jeśli zostaną rozwiązane. (Na przykład, instancje kodujące wyzwania faktoringu RSA.) Zbadaj wydajność najlepszych …
1
Typy indukcyjne dla dużych policzalnych notacji porządkowych.
Chcę budować notacje dla dużych policzalnych porządków w „naturalny sposób”. Przez „naturalny sposób” rozumiem, że biorąc pod uwagę typ danych indukcyjnych X, równość ta powinna być zwykłą rekurencyjną równością (ta sama, deriving Eqktórą wytworzyłby Haskell), a kolejność powinna być zwykłym rekurencyjnym porządkiem leksykograficznym (tym samym, co deriving Ordw Haskell dałby …
4
Dowody uzyskane jedynie za pomocą teorii grafów spektralnych
Coraz bardziej interesuję się teorią wykresów spektralnych, co wydaje mi się fascynujące, i zacząłem zbierać kilka dokumentów, które muszę jeszcze przeczytać dokładniej niż dotychczas. Jestem jednak ciekawy stwierdzenia, które pojawiło się w kilku źródłach (na przykład tam ), które mówi w istocie, że niektóre wyniki teorii grafów zostały udowodnione przy …
17
Przykłady, w których wgląd w geometrię był przydatny do rozwiązania czegoś całkowicie niegeometrycznego
Jedną z miłych rzeczy w ewolucji we wszechświecie o trzech wymiarach przestrzennych jest to, że rozwinęliśmy umiejętności rozwiązywania problemów dotyczące obiektów w przestrzeni. Tak więc na przykład możemy myśleć o tryplecie liczb jako o punkcie 3-d, a zatem obliczenia o tripletach liczb jako o obliczeniach o punktach w 3-d, które …
1
Czy istnieje rozsądny zautomatyzowany system dowodowy dla twierdzeń TCS?
Załóżmy, że chciałem sformalizować dowód Turinga dotyczący problemu zatrzymania, aby maszyna mogła to sprawdzić. Niektóre ze znanych automatycznych systemów dowodzenia twierdzeń obejmują Mizar, Coq i HOL4. Pobrałem i eksperymentowałem z Coq, ale nie ma biblioteki dla maszyn Turinga. Sam pomyślałem o kodowaniu jednego, ale brakowało tego samouczka, a język był …
3
Prezentacja w toku (slajdy są już dostępne)
Prezentacja teraz podana. Slajdy dostępne poniżej. Prezentacja prac w toku jest czymś, co wszyscy powinniśmy zrobić, aby uzyskać wczesną informację zwrotną i pomóc w krystalizacji naszych pomysłów. Niestety, wielu doktorantów potrzebuje pomocy w przezwyciężeniu trudności związanych z prezentowaniem wczesnych badań, nawet jeśli dotyczy to tylko ich własnej grupy badawczej. Będę …
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.