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...
To moje pierwsze pytanie na tej stronie. Biorę kurs magisterski z teorii obliczeń. Jak wytłumaczysz problem P = NP 10-letniemu dziecku i dlaczego ma on taką nagrodę pieniężną? Twoje zdanie? Zaktualizuję pytanie, gdy moja głowa się o tym
Hierarchia Chomsky'ego (–Schützenberger) jest używana w podręcznikach teoretycznej informatyki, ale oczywiście obejmuje tylko bardzo niewielką część języków formalnych (REG, CFL, CSL, RE) w porównaniu z pełnym diagramem złożoności Zoo . Czy hierarchia odgrywa już jakąkolwiek rolę w bieżących...
Mój dział często prosi mnie o wygłaszanie wykładów dla uczniów liceum na temat bardziej matematycznych elementów informatyki. Dokładam wszelkich starań, aby wybierać z TCS tematy, które mogą wzbudzić ich zainteresowanie (co dotyczy głównie problemu Halting), ale chętnie usłyszę pomysły / sukcesy /...
Zawsze istnieje sposób na zastosowanie w tematach związanych z informatyką teoretyczną. Jednak podręczniki i kursy licencjackie zwykle nie wyjaśniają, dlaczego teoria automatów jest ważnym tematem i czy nadal ma zastosowania w praktyce. Dlatego studenci mogą mieć problemy ze zrozumieniem znaczenia...
To pytanie jest skierowane do osób, które przypisują problemy: nauczycieli, asystentów studentów, opiekunów itp. Zdarzyło mi się to kilka razy w mojej 12-letniej karierze profesora: pośpiesznie przypisałem jakiś problem z tekstu, myśląc, że „wygląda dobrze”. Później zrozumiał, że nie mogę tego...
Kiedy postępujemy zgodnie ze standardowymi podręcznikami lub tradycją, większość z nas uczy następującej definicji notacji Big-Oh w pierwszych kilku wykładach klasy algorytmów: Być może podajemy nawet całą listę ze wszystkimi jej
Zgadywanie nie jest częstym pytaniem, ale zastanawianie się, czy ktokolwiek widział materiał, który został wyraźnie stworzony, aby przemówić do odbiorców w znaczący
Prowadzę kurs zaawansowanych algorytmów i chciałbym uwzględnić niektóre tematy związane z uczeniem maszynowym, które zainteresują moich studentów. W związku z tym chciałbym usłyszeć opinie ludzi na temat najbardziej interesujących / największych wyników algorytmicznych w uczeniu maszynowym....
Właśnie nauczyłem losowego algorytmu skrótu Karger-Stein w mojej klasie algorytmów dla absolwentów. To prawdziwy klejnot algorytmiczny , więc nie mogę tego nie uczyć, ale zawsze denerwuje mnie, ponieważ nie znam innych zastosowań głównej techniki. (Trudno więc przypisać pracę domową, która...
Mam trudności z nauczeniem pojęcia funkcji obliczalnych. Próbowałem rozwinąć pojęcie, dlaczego badacze tacy jak Hilbert / Ackermann / Godel / Turing / Church / ... wymyślili pojęcie „obliczalności”. Uczniowie natychmiast zapytali: „co oznacza obliczalność?” i nie mogę odpowiedzieć, dopóki nie...
Obecnie prowadzę mały kurs (cztery dwugodzinne wykłady na poziomie magisterskim) na temat metod logicznych w zakresie bezpieczeństwa , chociaż tytuł Formalne metody w zakresie bezpieczeństwa może być bardziej trafny. Obejmuje krótko następujące tematy (wraz z powiązanymi metodami...
W przyszłym semestrze będę prowadził standardowe studia licencjackie z języków i automatów i wolałbym korzystać z legalnego bezpłatnego lub taniego tekstu. Jakieś sugestie? Uwielbiam tekst Sipser, ale najnowsze wydanie kosztuje 196 USD, co trudno powiedzieć z prostą miną w dobie bezpłatnych...
Mam rozsądne wykształcenie matematyczne, ale nigdy nie czułem się w 100% swobodnie z abstrakcyjną algebrą (matematyka grup, pierścieni, pól itp.). Myślę, że było to częściowo tak, jak potrzebowałem, aby zobaczyć aplikacje, a wszystkie, które mogłem znaleźć, dotyczyły fizyki, a nie CS. Ponieważ moim...
Zaproponowano mi nauczenie nowatorskiego programu szkoły średniej TCS, który wymaga opracowania programu nauczania. Bardzo chciałbym usłyszeć opinie i sugestie dotyczące tego. Po pierwsze, czy ktoś wie o szkołach średnich, w których program TCS był nauczany z powodzeniem (lub bez...
Istnieje wiele algorytmów i struktur danych, które wykorzystują ideę, że otrzymuje minimalną wartość przy k = \ sqrt n . Typowe przykłady to k = √max{k,n/k}max{k,n/k}\max \left\{k, n/k\right\}k=n−−√k=nk=\sqrt n algorytm gigantycznego kroku dziecka do obliczania logarytmu dyskretnego w...
Szukam przykładów wyników, które są sprzeczne z intuicją ludzi podczas ogólnej dyskusji publiczności. Wyniki, które na pytanie ekspertów niebędących ekspertami „co podpowiada ci intuicja?”, Prawie wszystko byłoby błędne. Oświadczenie o wynikach powinno być łatwe do wyjaśnienia studentom w cs /...
Jestem dość sprawnym inżynierem oprogramowania, ale niewiele wiem teorii. Chcę dowiedzieć się więcej teorii. Szczególne tematy, którymi się interesuję, to: złożoność obliczeniowa, języki formalne i teoria typów. Ale nie wiem, jak zacząć uczyć się o tych dziedzinach. Jakie zasoby poleciłbyś...
Za każdym razem, gdy uczę kompletności NP, uczniowie pytają „czy są jakieś problemy, o których wiadomo, że nie należą do NP?” Jak byś odpowiedział? Zazwyczaj daję im nierozstrzygalny problem jako przykład, ale często nie wychodzi to dobrze: (a) jeśli daję im problem z zatrzymaniem, myślą, że to...
Załóżmy, że spotykasz się z programistami, którzy odbyli profesjonalne kursy programowania (/ self-think), ale nie studiowali matematyki na poziomie uniwersyteckim. Aby pokazać im piękno TCS, chciałbym zebrać kilka fajnych wyników / otwartych pytań pochodzących z TCS, które można łatwo...