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ł zaimplementować pewne algorytmy do mojej pracy, ale czy mogę wtedy poczekać? A może jest coś więcej?

Jak ważna jest wiedza na temat kodowania w TCS (w dziedzinach, w których programowanie nie jest bezpośrednio zaangażowane): czy istnieją powody, dla których teoretycy CC (na przykład) mogą wiedzieć, jak pisać? Czy warto poświęcić dużo czasu na naukę kodowania? A jeśli tak, to czy istnieje kategoria (funkcjonalna, imperatywna, obiektowa ...) języka programowania, która byłaby bardziej odpowiednia?

Informatyka teoretyczna jest szeroką dziedziną, a znaczenie programowania zależy od tego, co robisz w TCS. Wymienię dwa sposoby, w jakie programowanie może ci pomóc, nie sugerując, że są to jedyne sposoby.

Po pierwsze, jeśli projektujesz algorytmy dla problemów o znaczeniu praktycznym, wdrożenie algorytmów i udostępnienie kodu innym może być dużym plusem. Na przykład problem wypukłego kadłuba powstaje w wielu dziedzinach, a ludzie używają pakietów oprogramowania, takich jak cdd Komei Fukuda i lrs Davida Avisa, aby rozwiązać ten problem. Gdyby opublikowali swoje algorytmy tylko w papierach, prawdopodobnie mniej osób skorzystałoby z ich algorytmów. Więcej użytkowników oznacza więcej opinii i prawdopodobnie także więcej możliwości współpracy, co jest nieocenione.

Po drugie, nawet jeśli nie pracujesz w algorytmach, pisanie kodu jednorazowego pomaga przetestować prostą hipotezę, gdy hipoteza jest odpowiednia do obliczeń numerycznych. Na przykład, jeśli zastanawiasz się, czy iloczyn trzech pozytywnie określonych macierzy zawsze ma dodatni ślad, łatwo jest napisać kod, aby przetestować go pod kątem losowych wyborów 2 × 2 lub 3 × 3 pozytywnie określonych macierzy i znaleźć kontrprzykład. Chociaż nie reklamujesz się, że napisałeś jakiś program do testowania przypuszczeń, programowanie może zaoszczędzić czas, który na próżno poświęciłby próbę udowodnienia fałszywego stwierdzenia.

Wybór języka programowania zależy od tego, co chcesz zrobić z programowaniem, i moim zdaniem może to być temat całej książki. Ale jeśli projektujesz algorytmy i chcesz zaimplementować swoje algorytmy, aby inni mogli korzystać z implementacji, ważnym czynnikiem jest dostępność. Chociaż można oczekiwać, że większość potencjalnych użytkowników kodu ma dostęp do kompilatora C, nie można oczekiwać, że te same osoby będą miały dostęp do kompilatora Haskell. W przypadku programów jednorazowych wybór jest bardziej oparty na dostępnych bibliotekach i obejmuje środowiska takie jak Matlab.

Nawiasem mówiąc, programowanie może być również zabawne.

Czuję się zmuszony zacytować Dorona Zeilbergera na ten temat:

Opinia 37 : Programowanie jest jeszcze przyjemniejsze niż sprawdzanie, a co ważniejsze, daje tyle samo, jeśli nie więcej, wglądu i zrozumienia.

Przeczytaj opinię, jest pełen klejnotów (a przy okazji jest on celowo prowokujący). Na przykład: „Najlepszym sposobem na zrozumienie czegoś jest nauczenie go. Ale jeszcze lepiej niż nauczenie ludzi, to nauczenie go na komputerze”.

Moje osobiste doświadczenie jest takie, że nawet przy pracy czysto teoretycznej będziesz potrzebować narzędzi obliczeniowych. Unikam wielu żmudnych rutynowych manipulacji algebraicznych za pomocą Mathematiki. Testuję moje na wpół uparte przypuszczenia, zmuszając brutalne małe instancje do Matlaba lub Pythona. Napisałem jeden artykuł, który jest czystą kombinatoryką, i na tym właśnie skorzystałem najbardziej, przeprowadzając obszerne eksperymenty komputerowe, aby zrozumieć, co się dzieje. Euler dokonał ogromnych tabel żmudnych obliczeń, aby uzyskać wgląd w problemy. Jesteśmy mu winni wykorzystanie naszych narzędzi do automatyzacji tego procesu, gdy zajmujemy się matematyką.

Poza tym, jeśli będziesz pracować nad algorytmami i strukturami danych, programowanie da niezastąpione spojrzenie na kwestie wydajności i użyteczności. Moja opinia tutaj różni się nieco od innych. Myślę, że nauka języka funkcjonalnego, aby poprawnie pisać dowody tego typu, to strata czasu (myślę, że to świetna rzecz, że ludzie, którzy mają doświadczenie z silnie napisanym językiem, prawdopodobnie mają tendencję do pisania bardziej starannie ustrukturyzowanych dowodów; po prostu nie myślę, że warto poświęcić czas na wykonanie tego ćwiczenia). Programowanie funkcjonalne przesłania problemy z projektowaniem algorytmów i czasem działania oraz kładzie nacisk na kwestie logiki i semantyki (i oczywiście nauczenie się programowania funkcjonalnego jest prawdopodobnie koniecznością i przyjdzie nieco naturalnie, jeśli jesteś zainteresowany semantyką logiki / PL). Podobnie, Myślę, że wchodzenie w szczegóły OO Java i C ++ również nie jest optymalnym sposobem spędzania czasu, ponieważ celem OO jest pisanie modułowego kodu wielokrotnego użytku. Jest to dobry sposób, jeśli stworzysz kod, z którego będą mogli korzystać inni. Ale jeśli chcesz uzyskać wgląd w wydajność i czas działania, jeśli zależy Ci na naprawdę wydajnych algorytmach i strukturach danych, proponuję zajrzeć do C. To pozwala ci pozostać blisko maszyny, jednocześnie zapewniając rozsądny poziom abstrakcji . W ten sposób możesz poczuć, co jest szybkie, a co wolne, co jest rozsądną strukturą danych itp. Ale jeśli chcesz uzyskać wgląd w wydajność i czas działania, jeśli zależy Ci na naprawdę wydajnych algorytmach i strukturach danych, proponuję zajrzeć do C. To pozwala ci pozostać blisko maszyny, jednocześnie zapewniając rozsądny poziom abstrakcji . W ten sposób możesz poczuć, co jest szybkie, a co wolne, co jest rozsądną strukturą danych itp. Ale jeśli chcesz uzyskać wgląd w wydajność i czas działania, jeśli zależy Ci na naprawdę wydajnych algorytmach i strukturach danych, proponuję zajrzeć do C. To pozwala ci pozostać blisko maszyny, jednocześnie zapewniając rozsądny poziom abstrakcji . W ten sposób możesz poczuć, co jest szybkie, a co wolne, co jest rozsądną strukturą danych itp.

Możesz odnieść sukces jako informatyk teoretyczny bez programowania. Dla kilku osób programowanie jest dość trudne, a jeśli jesteś jedną z nich, nie powinieneś rozpaczać i zmieniać pól.

Jednak dla większości absolwentów matematyki i informatyki nauka programowania nie jest szczególnie trudna i jest umiejętnością bardzo przydatną. Powinieneś nauczyć się języka programowania, a jeśli ci się spodoba, powinieneś spróbować wystarczająco dużo praktyki, aby stać się w nim dość biegłym. Następnie, gdy nadejdzie (i będzie) punkt, że napisanie programu będzie przydatne w twoich badaniach, będziesz w stanie to zrobić.

Jeśli nie nauczysz się programować teraz, jest całkiem prawdopodobne, że kiedy w końcu będziesz musiał napisać program, nie będziesz miał czasu na naukę, więc możesz go nie napisać, co może być mniej skuteczne Badania. Mimo, że nie jest to zbyt trudne, aby student zrobił to za ciebie, nie jest to zbyt trudne, ale jest wiele razy, kiedy jest to o wiele łatwiejsze i mniej czasochłonne, aby zrobić to samemu, niż wyjaśniać im problem.

Jakiego języka powinieneś się nauczyć? Poleciłbym język zorientowany obiektowo, ponieważ są one obecnie najczęściej używane i podejrzewam, że będzie to bardziej prawdziwe w przyszłości. Może Python lub Java - oba są językami zorientowanymi obiektowo i chociaż w praktyce są rzadziej używane niż C ++, mam wrażenie, że oba są znacznie łatwiejsze do nauczenia się. (Zastrzeżenie: Nie znam C ++, mimo że pracowałem w Bell Labs, więc może się mylę.)

Jest jeszcze jedna odpowiedź, której tak naprawdę nikt nie podniósł. Programowanie może prowadzić do interesującej teorii. Wiele ostatnich zmian w haszowaniu (zwłaszcza haszowanie tabelaryczne) nie jest motywowanych teoretycznymi obawami, ale faktem, że teoretycznie optymalne algorytmy nie są tak świetne w praktyce. Jest to oczywiście coś, czego nie wiesz, chyba że umiesz pisać kod.

Nawet w dziedzinie dokładnych algorytmów czasu wykładniczego motywacja wytwarza algorytmy, które faktycznie mogą działać. Solwery SAT są tego kanonicznym przykładem.

Krótko mówiąc, zdolność do kodowania pozwala dostrzec niedociągnięcia i słabości, które mogą wyglądać jak optymalne wyniki teoretyczne, co z kolei otwiera nowe kierunki badań teoretycznych.

Trzy punkty:

1) Istnieje podejście do matematyki zwane matematyką eksperymentalną (patrz także wikipedia: // Dowód wspomagany komputerowo ), w którym używasz programów komputerowych do badania wzorów i struktur obiektów w celu uzyskania analitycznych dowodów na te obiekty. W przypadku tego podejścia lepiej wiesz, jak programować. Możesz być pewien, że będziesz potrzebować takiego podejścia, aby udowodnić bardzo teoretyczne stwierdzenia. Uważam, że snobizm wobec programowania często okazuje się nie być tak naprawdę pomocny w badaniach TCS.

$A \in L(X,Y)$$B \in L(Y,C)$

3) Kiedy mówisz „programować”, czy masz na myśli także „ program liniowy ” czy „ program półfinałowy ”? :)

Dziękuję Gopi za to pytanie. Chciałbym rozszerzyć wiele interesujących odpowiedzi na inny wymiar, o którym jeszcze nie wspomniano.

Badania nie są jedyną rzeczą, którą robimy na uniwersytecie: jeśli chcesz pozostać w środowisku akademickim, w końcu będziesz musiał uczyć. Jeśli masz szczęście, będziesz musiał uczyć kursów, które są dość daleko od twojego obszaru specjalizacji. Całkiem prawdopodobne, że otrzymasz kursy z dużym komponentem programistycznym. W tym przypadku nawet umiarkowana umiejętność programowania znacznie pomaga: będziesz znacznie lepszym nauczycielem, jeśli umiesz programować. Przede wszystkim będziesz czuć się bardziej komfortowo z materiałem, będziesz w stanie lepiej odpowiadać na pytania uczniów i rozumiesz trudności, jakie uczniowie mają z nauką programowania, ponieważ sam doświadczyłeś tego procesu uczenia się. Ponadto możesz produkować lepsze materiały dydaktyczne. Na przykład możesz samodzielnie przetestować ćwiczenia z programowania przed przekazaniem ich studentom,

Istnieje dodatkowy pragmatyczny wymiar: nauczanie obejmuje różne powtarzające się zadania, które wykwalifikowany programista może często zautomatyzować, na przykład szybkie utworzenie strony internetowej, z której studenci mogą korzystać w celu przesłania zajęć, i ich automatyczne ocenianie (zgodnie z liczbą zautomatyzowanych testów, które kod przechodzi).

Programowanie jest dobrym sposobem na lepsze zrozumienie różnych pojęć, ale jest także niebezpiecznym zejściem czasu.

Typowym argumentem przeciwko programowaniu jest to, że sprawia, że ​​spędzasz czas z nieistotnymi szczegółami; typowym argumentem przy programowaniu jest to, że uświadamiasz sobie, że szczegóły, które uważałeś za nieistotne, są w rzeczywistości ważne. Dobra znajomość programowania to przede wszystkim umiejętność szybkiego radzenia sobie z nieistotnymi częściami. Stawanie się dobrym zajmuje dużo czasu.

Jeśli chodzi o język programowania do nauki: „wszystkie z nich” to moja odpowiedź.

Spóźniam się na przyjęcie i wszystkie są świetne odpowiedzi, ale mam inny powód:

Wyobrażanie sobie.

Tak, często będziesz pracować z rzeczami, które nie mogą być wizualizowane, ale często będziesz pracować z rzeczami, które mogą. Znajomość programowania jest niezbędna do tego zadania, a wizualizacja może dać ci wgląd w problem.

Krótka uwaga: wiedza na temat programowania daje mi dodatkowe narzędzie w badaniach teoretycznych. Kiedy mam algorytm, który moim zdaniem zadziała, jeśli jest to dość łatwe, mogę go zakodować i sprawdzić, czy rzeczywiście działa. Jeśli mój pomysł (nawet) nie działa w praktyce, mało prawdopodobne jest, że zadziała teoretycznie, a takie podejście często oszczędza mi spędzania ogromnej ilości czasu na próbach udowodnienia czegoś, co jest fałszywe.

Nikt tutaj nie zajął się praktycznymi kwestiami, dlaczego ktoś studiujący TCS powinien uczyć się programowania.

Jeśli planujesz zrobić doktorat z TCS na wydziale informatyki, istnieje duża szansa, że ​​będziesz musiał wziąć udział w kursach innych niż teoria, a te prawie na pewno będą bardzo intensywne w programowaniu. W zależności od programu, w którym uczestniczysz, być może będziesz potrzebować wiedzy z przedmiotów innych niż teoria, aby zdać egzamin kwalifikacyjny.

Po zakończeniu doktoratu większość ofert pracy dla TCS znajduje się w środowisku akademickim. Jeśli pracujesz w środowisku akademickim, będziesz oczekiwać, że będziesz uczył, i możesz oczekiwać, że będziesz uczył wstępnej klasy CS, która będzie bardziej programować niż teorię. Nawet jeśli uczysz teorię dla studentów, jak powiedzmy Algorytmy, możesz spodziewać się, że twoi uczniowie będą wiedzieć więcej o programowaniu niż teorii i bez wiedzy tego, co wiedzą twoi uczniowie, będzie ci trudno wypełnić luki w ich zrozumieniu . Wzdrygam się na myśl, że studentami CS uczą osoby, które nie znają programowania!

Jeśli nie przejmujesz się tymi praktycznymi obawami, prawdopodobnie możesz to zrobić, przeprowadzając badania, nie wiedząc nic o programowaniu. Na pewno masz dużo towarzystwa w społeczności TCS, ale przebieg będzie się różnić w zależności od dokładnego obszaru teorii, w którym pracujesz. Na przykład, jeśli wykonujesz czystą teorię złożoności obliczeniowej, udowadniając dolne granice klas, których nikt nie ma kiedykolwiek o tym słyszałeś, to prawdopodobnie programowanie Ci nie przyda się. Ale jeśli robisz coś bardziej algorytmicznego, to czuję, że umiejętność napisania dobrego, czystego, działającego kodu wzmocni twoją intuicję, jeśli nic więcej.

Polecam naukę języka C (nie C ++). Podnieś kopię K&R i przeczytaj ją od początku do końca. C nie ma wielu fantazyjnych cech współczesnych języków, ale ma prostą, ale elegancką składnię i semantykę, których powinieneś być w stanie nauczyć się w całości. Jednak nawet jeśli rozumiesz cały język, nadal musisz ćwiczyć pisanie dobrego, eleganckiego, wolnego od błędów kodu w C. Niemniej jednak, jeśli potrafisz opanować kodowanie w C, będziesz w stanie opanować każdy napotkany język programowania. Co więcej, dyscyplina ta pomoże ci myśleć, jak myśli sprzęt, co będzie korzystne przy projektowaniu algorytmów.

Pomysły takie jak wskaźniki są bardzo ważne dla każdego, kto zajmuje się projektowaniem algorytmów, ale niestety języki takie jak Java i Python zasłaniają je przed tobą, dlatego nie polecam ich jako pierwszego języka osobom z matematyki. OOP jest ważniejszy dla ludzi, którzy muszą utrzymywać ogromne projekty oprogramowania, a nie dla tych, którzy projektują algorytmy.

Sugeruję, abyś nie czekał na rozpoczęcie kursu, ponieważ informatyka na dowolnym poziomie obejmuje wdrażanie algorytmów za pomocą komputera w celu osiągnięcia / weryfikacji / rozwiązania dowolnej teorii, z którą będziesz musiał się zmierzyć podczas całego kursu, zwłaszcza na twoim poziomie.

Najpierw musiałem programować w klasie 10 (liceum) i już wiedziałem, jak korzystać z wiersza poleceń, a to naprawdę pomogło (ma to pokazać, jak „podstawowe” umiejętności programowania są rozważane w CS).

Zaskoczenie twoich rówieśników jest uzasadnione, ponieważ pseudokod i algorytmy są jednymi z pierwszych rzeczy, których trzeba się nauczyć, aby programować.

Nie możesz się jednak całkowicie zagubić na nadchodzącym kursie, ponieważ możesz wykorzystać swoje szersze umiejętności matematyczne (na własną rękę), aby pominąć programowanie obiektowe, aby nadrobić zaległości w szybszym nauce funkcjonalnego języka programowania.

• Programowanie funkcjonalne jest BARDZO zorientowane na matematykę, uważane za trudniejsze do nauczenia się z powodu potrzebnego tła matematycznego, uważane za bardzo potężne (w „prosty”, matematyczny sposób rozwiązywania trudnych problemów za pomocą eleganckich i „czystych” środków).
• Orientacja obiektowa jest dobra, gdy nie chcesz zrozumieć podstawowych algorytmów i zasad implementacji i po prostu chcesz „ponownie wykorzystać” już istniejące obiekty.

Myślę, że możesz poradzić sobie z Haskellem (zwykle nie jest to pierwszy język), ponieważ jest on czysto matematyczny, funkcjonalny i może zrobić w zasadzie wszystko, co chcesz. Uczenie się Haskell postawiłoby cię na poziomie, na którym nie musiałbyś więcej się uczyć, aby nadążyć, a nawet postawiłoby cię w sytuacji kontroli i władzy nad swoim kursem. Jeśli interesują Cię statystyki, nauka R jest zaletą, ale nie tak bardzo, jak Haskell. Widziałem doniesienia matematyków, którzy stwierdzili, jak bardzo byli zaskoczeni bliskością matematyki i tym, jak przyjęła ich sposób myślenia.

Ponadto wyzwaniem, którym warto się zająć (aby szybko przyzwyczaić się do środowiska programistycznego), byłoby zainstalowanie systemu Linux i korzystanie z niego (wystarczy Ubuntu Linux). Zaufaj mi, wiele się nauczysz, grając z nim ...

Te porady są najlepszym znanym mi sposobem szybkiego nadrobienia zaległości dla matematyka w dziedzinie informatyki. Poza tym społeczność Open Source jest bardzo przyjazna i pomocna, a jeśli utkniesz, IRC jest najbardziej bezpośrednim sposobem na rozmowę na dowolny temat za pośrednictwem wyspecjalizowanych kanałów (połączenie na FreeNode). Pamiętaj: zadawanie pytań to jedyny sposób rozwiązywania problemów, czy to dla ciebie, forum, wyszukiwarki, czy na czacie.

Przykładem implementacji interaktywnego systemu proofingu w C ++ jest następujący artykuł: Optymalne czasowo interaktywne dowody oceny obwodu, autorstwa Justina Thalera. Jest dostępny na stronie http://people.seas.harvard.edu/~jthaler/ . Wydaje się, że jest to krok w kierunku opracowania praktycznego wdrożenia interaktywnych systemów dowodu ogólnego zastosowania.

Podobne artykuły i powiązane kody źródłowe pojawiają się na wyżej wspomnianej stronie internetowej.