Matematyka dla TCS major

Zobacz powiązane pytanie.

Sprawdź także wymagania dotyczące kursu w szkole , a także podobne pytania z zakresu teoretycznej informatyki (np. To czy tamto ). Kusi mnie, aby zamknąć to tutaj jako duplikat; jest również dość zlokalizowany.

Weź CAŁĄ matematykę!

@JeffE Weź ... całą matematykę?

Cała matematyka w Zestawie narzędzi teoretycznych .

Zdecydowanie nie zgadzam się z tym ogólnym stwierdzeniem. W rzeczywistości ogromna większość dziedzin matematyki nie jest pomocna w informatyce teoretycznej. Powiedz analizę funkcjonalną, teorię zbiorów (np. Wymuszanie), topologię, geometrię algebraiczną (nie, GCT się nie liczy), równania różniczkowe, a lista może być długa. Najważniejszym przedmiotem matematycznym jest teoria prawdopodobieństwa (nawet to zależy od rodzaju wykonywanego TCS). Poza tym pewna bardzo podstawowa wiedza w niektórych obszarach, np. Teoria grup.

@Yuval, myślę, że to trochę krótkowzroczność. Kto myślał, że transformaty Fouriera mogą być tak przydatne dla TCS (przed chwałą, którą osiągnął, gdy jest używany na PCP itp.) ) .. Myślę, że wiele innych metod może być używanych w TCS i na pewno w CS w ogóle. To prawda, nie wszystkie metody są równie ważne, i miałem nadzieję, że ten wątek stanie się listą metod / aplikacji, w których najbardziej ważne metody uzyskałyby najwyższe głosy.

Transformaty Fouriera są bardzo elementarnymi pojęciami. Nie musisz rozumieć jądra Fejer w TCS. Jeśli chodzi o SDP, pochodzą one z badań operacyjnych (lub optymalizacji wypukłej, jeśli wolisz). To prawda, że ​​niektóre rzeczy mogą być przydatne. Na przykład moje pochodzenie w C jest bardzo przydatne, a Virginia Williams uznała swoje pochodzenie w Klonie za bardzo przydatne. Jeśli chodzi o twoją karierę, bardzo przydatne jest pisanie i wystąpienie publiczne. Wszystkie te są prawdopodobnie bardziej przydatne niż kurs kombinatorycznej teorii zbiorów. Dlaczego nie powiedzieć ludziom, aby studiowali te przedmioty zamiast przypadkowych kursów matematycznych?

@YuvalFilmus Nie rozumiem: zasada niezmienności MMO jest ścisłym uogólnieniem Berry-Esseen. Nie zgadzam się również z twoim większym punktem. Wiele TCS może wykorzystywać prawdopodobieństwo aż do granicy Chernoffa. Ale JL-lemat, koncentracja miary, powiedzmy ARV, twierdzenie Dvoretzky'ego o ściśniętym wyczuciu, nierówność Grothendiecka w przybliżeniu normy cięcia są tylko bardzo udanymi przykładami przydatności FA w TCS. tak, główny nurt tych dwóch dziedzin jest inny - ale przecięcia wykraczają poza „pierwsze 10 stron” i sprawiają, że nauka matematyki jest tego warta.

ponadto, chociaż nasze aplikacje zwykle pozwalają nam trzymać się (wariantów) wyników, które można opisać i często udowodnić w elementarny sposób, większy kontekst zapewnia intuicję (CLT jest na przykład świetną heurystą). a ponieważ trudno jest powiedzieć, co jest przydatne, dopóki nie będziesz musiał z niego skorzystać, nie miałbym nic przeciwko wzięciu kursów matematyki oprócz czytania grup w TCS, które pomogą Ci dowiedzieć się, co już jest przydatne. Niedawno znalazłem wynik FA (który prawie nigdy nie jest używany w TCS afaik), który jest kluczem do problemu, nad którym pracowałem