Jak ważna jest umiejętność programowania w TCS?

66

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?

Gopi
źródło
12
Powinieneś był coś zaprogramować, aby pisać sensowny, tj. Określony i odzwierciedlający środowisko pseudo-kod. Matematycy często tego nie robią. Ponadto, jeśli chcesz faktycznie wykorzystać opracowaną teorię, prawdopodobnie będziesz musiał coś zaimplementować. Jeśli chodzi o języki, prawdopodobnie lepiej jest nauczyć się czegoś funkcjonalnego. C jest dobry pod względem wydajności, ale trudny do uzasadnienia i pod wieloma względami bałagan. (Jak widać, YMMW)
Raphael
6
Zgadzam się z „Matematycy często tego nie robią”. Prostym testem na to, czy matematyk opisujący algorytm naprawdę naprawdę zaprogramował jest pytanie „Co dokładnie masz na myśli przez„ Biorąc pod uwagę X… ”?”.
Jeffε
4
Programowanie, co to jest? Twierdzenia to moje programy. Procedura gotowania różni się od sztuki gotowania. Niestety, od ponad 20 lat nie mogę odczytać żadnego kodu programu. Nienawidzę tego bałaganu „realizowanego na PC”. (Już ta notacja źle się robi). Euclid nie mógł zaprogramować. A jednak tworzył programy przez stulecia.
Stasys,
6
@StasysJukna: Euclid był naprawdę bardzo kiepskim programistą. Nie tylko nigdy nie wdrożył swoich algorytmów, nigdy nawet nie uruchomił ich ręcznie na umiarkowanie skomplikowanych testach.
Jeffε
3
@ Jɛ ff E: Tak, Euclid był kiepskim programistą, dokładnie to chciałem powiedzieć. My, w TCS, staramy się nie rozróżniać książek o gotowaniu i sztuki cockingowej. Euclid mógł. Mam wielki szacunek dla ludzi, którzy potrafią programować. Ale nie sądzę, że ta funkcja oznacza „jeden CAN w TCS”. Po prostu nie będzie bolało.
Stasys,

Odpowiedzi:

55

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.

Tsuyoshi Ito
źródło
2
@SureshVenkat: W rzeczywistości, jeśli programowanie jest fajne, pytanie „Jak ważne jest programowanie?” Może nie być bardzo trafne. Ale wtedy większość mojej odpowiedzi stanie się nieistotna. Jak smutno! :)
Tsuyoshi Ito,
Nie myślałem o twoim drugim sporze wcześniej, w rzeczy samej dobrym pomysłem wydaje się przetestowanie przypuszczenia za pomocą krótkiego programu! Jeśli chodzi o programowanie, może być zabawne, tak się wydaje, ale jeszcze nie widziałem tego przez cały długi weekend nauki =).
Gopi,
@Gopi: To powiedziawszy, wiele przypuszczeń nie pasuje do tego „testu z prostym programem”. Na przykład zwykle nie możemy przetestować zachowań asymptotycznych (przynajmniej za pomocą prostego programu). Ale kiedy masz jakieś przypuszczenia, które można przetestować, małe programowanie może być potężnym narzędziem. Co do zabawy, tak, rozumiem. Po prostu nie chciałem ignorować „zabawnego” punktu widzenia, wymieniając jedynie niektóre motywacje z punktu widzenia „użyteczności”.
Tsuyoshi Ito,
3
Notatki Knutha na temat klasy rozwiązywania problemów mają wspaniały przykład wzajemnej zależności między przypuszczeniami a kodem (patrz problem 1): www-cs-faculty.stanford.edu/~knuth/papers/cs1055.pdf (szczególnie podoba mi się wizerunek kogoś wpada do klasy z kupą wydruków)
Suresh Venkat,
47

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.

Sasho Nikolov
źródło
10
„Programowanie funkcjonalne przesłania problemy z projektowaniem algorytmów i czasem działania oraz kładzie nacisk na problemy z logiką i semantyką”. Walczące słowa :)
Suresh Venkat
3
„Programowanie funkcjonalne przesłania problemy z projektowaniem algorytmów i czasem działania oraz kładzie nacisk na problemy z logiką i semantyką”. Dlatego jest to dobry wybór, jeśli pracujesz po stronie logiki lub semantyki TCS. :)
Radu GRIGore
5
Ahem.
Jeffε
3
@Sasho: Wszystkie zwykłe techniki nadal działają w językach funkcjonalnych. Jedynym „problemem” jest to, że programowanie funkcjonalne zachęca do stylu programowania i projektowania struktury danych, z którymi zwykłe techniki analizy algorytmicznej nie są w stanie sobie poradzić. (Np. Jaka jest wielka-O składu funkcji? Operacja jest trywialna , ale całkowicie łamie założenia asymptotycznej złożoności - nie ma prostej numerycznej miary wielkości dla funkcjonalnego wejścia.)
Neel Krishnaswami
3
@SashoNikolov: Ilekroć prowadzę klasę struktur danych dla absolwentów, naprawdę bardzo chciałbym założyć, że każdy miał jakieś funkcjonalne doświadczenie w programowaniu. Zamiast spędzić trzy 90-minutowe wykłady w celu wyjaśnienia wytrwałości, mógłbym po prostu powiedzieć „Hej, zauważyłeś, że twoje struktury danych już TO robią?”
Jeffε
33

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ę.)

Peter Shor
źródło
2
Widzę prawdę w twoim trzecim akapicie :).
Gopi,
1
„Jednak dla większości ludzi nauka programowania nie jest szczególnie trudna” - moje doświadczenie nie zgadza się z tym, ale większość ludzi nie jest badaczami TCS.
Maks.
2
Wraz z pojawieniem się Sage, możliwa jest praca z przyjemnym, popularnym językiem, takim jak Python, przy jednoczesnym natychmiastowym dostępie bibliotek matematycznych w stylu Mathematica / Maple / Matlab.
András Salamon,
1
C ++ ma najbardziej zaawansowany system typu / metaprogramowania spośród wszystkich popularnych języków programowania ogólnego przeznaczenia, z wyjątkiem rodziny języków Lisp. Jeśli więc interesujesz się teorią typów, projektowaniem języka lub teorią kompilatora, lub szerzej - formalną semantyką, możesz się z nią zapoznać. Oprócz C ++ Java i C # są koniecznością, jeśli chcesz prowadzić badania w dziedzinie eksperymentalnej informatyki lub mieć nadzieję, że dostaniesz pracę jako programista lub inżynier oprogramowania w branży. Python powinien być nauczany w szkołach średnich: D
Antonio Valerio Miceli-Barone
4
@ AntonioValerioMiceli-Barone: Muszę się nie zgodzić, przynajmniej jeśli chodzi o teorię typów, projektowanie języka, semantykę formalną i ogólnie teorię programowania (PLT): C ++ nie jest językiem do nauki w tych dziedzinach; TT i semantyka formalna odnoszą się prawie wyłącznie do programowania funkcjonalnego, podczas gdy społeczność PL jest bardziej zróżnicowana, ale woli języki bardziej eleganckie niż C ++. Haskell to język „głównego nurtu” z najbardziej zaawansowanym systemem pisma, a następnie Scala (mniej zaawansowany, nieco bardziej główny nurt). C ++ ma ciekawe funkcje, ale jest zbyt niski dla współczesnego smaku.
Blaisorblade
33

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.

Suresh Venkat
źródło
Twoja odpowiedź może pomóc w pytaniu o wyniki empiryczne w TCS .
Gopi,
może: ale ten wątek już dawno wymarł :)
Suresh Venkat
Rzeczywiście, nie patrzyłem na datę, to było w ostatnim biuletynie, który otrzymałem, w sekcji „Największe hity z poprzednich tygodni” =).
Gopi,
18

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.

AL(X,Y)BL(Y,C)

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

Alessandro Cosentino
źródło
2
Nikt, kogo znam, nie używa słowa „do programowania” dla „programu liniowego” ani „programu półfinałowego”. Zamiast tego powiedziałbyś „zbudować / rozwiązać program liniowy”.
Peter Shor,
2
@PeterShor Point 3 nie był poważny
Alessandro Cosentino
3
I oczywiście powinieneś także nauczyć się programowania liniowego i programu półfinałowego ... obie przydatne umiejętności.
Peter Shor,
3
+1 za punkt 2, tak naprawdę uczono mnie trochę OCaml, gdy byłem studentem, mimo że korzystałem z niego tylko przez rok, przyzwyczaiłem się sprawdzać rodzaje moich dowodów.
Gopi
4
Programuję dynamicznie !
Jeffε
16

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).

Martin Berger
źródło
„Jeśli masz szczęście, będziesz musiał uczyć kursów, które są dość daleko od twojej specjalizacji.” Czy to szczęście…?
Tsuyoshi Ito,
3
@ Tsuyoshi: Cóż, to zmusza cię do zapoznania się z nowym obszarem tematycznym. W krótkim okresie oznacza to dużo pracy (która amortyzuje się na dłuższą metę, ponieważ prawdopodobnie nauczysz tego materiału więcej niż raz). Jednocześnie znacznie poszerza horyzonty intelektualne.
Martin Berger,
@TsuyoshiIto: Tak!
Jeffε 10.11.11
13

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ź.

Radu GRIGore
źródło
2
Wreszcie argument przeciwko programowaniu :).
Gopi,
1
@Gopi, myślę, że programowanie może być świetną zabawą i że lepsze zrozumienie, jakie zdobywasz, jest bardzo ważne. Inne odpowiedzi dają świetne przykłady tego, jak programowanie pomaga zrozumieć. Zachęcam więc do nauki programowania i nie poddawaj się, jeśli przedsięwzięcie nie wydaje się szybko spłacać.
Radu GRIGore,
6
Udowodnienie twierdzeń jest również dobrym sposobem na lepsze zrozumienie różnych pojęć, ale jest także niebezpiecznym zejściem czasu.
Jeffε
@ Jɛ ff E, moja opinia jest zachowana przez podstawienie [pseudokod-> dowód na papierze, kod-> dowód w asystencie dowodu].
Radu GRIGore,
12

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.

John Moeller
źródło
3
Wiem, jak programować i jestem absolutnie beznadziejny w wizualizacji. Podejrzewam również, że istnieją narzędzia, które pozwolą ci wizualizować rzeczy bez konieczności programowania; jeśli nie ma, powinno być, a może za kilka lat.
Peter Shor
@PeterShor: Ponieważ nie używasz C ++! (Tylko żartowałem)
Tsuyoshi Ito
1
@PeterShor: Nie mam na myśli żadnego konkretnego języka lub środowiska; MATLAB się tutaj liczy. Ale wiedza o programowaniu może dać ci wizualizacje, które w innym przypadku byłyby niezwykle niewygodne. Na przykład przestrzeń dwuwymiarowych macierzy o dodatniej wartości jest trójwymiarowa i chciałem wizualizować rodzinę konstrukcji w tej przestrzeni. Musiałem wymyślić transformację, a następnie zakodować ją, aby naprawdę zobaczyć moje obiekty.
John Moeller,
@John ... masz rację, nie sądzę, że mógłbyś to zrobić w inny sposób.
Peter Shor,
7

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.

Lew Reyzin
źródło
Tsuyoshi Ito napisał podobny argument w swojej odpowiedzi (drugi punkt :)).
Gopi
Ups, masz rację - tęskniłem.
Lew Reyzin
5

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.

znak
źródło
0

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.

Samuel Duclos
źródło
4
Nie wiem, jak bardzo odpowiadasz na pierwotne pytanie: nie pytałem „jak”, ale więcej „po co”.
Gopi,
0

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.

lgidwani
źródło
3
Czy wyjaśniłbyś, w jaki sposób ten artykuł jest powiązany z pytaniem, tj. Jak ważna jest znajomość programowania TCS ?
scaaahu
Nawet jeśli byłby to przykład wyniku teoretycznego, który skorzystał z programowania, nie odpowiedziałby na pierwotne pytanie?
Jeremy,
Pytanie dotyczy tego, czy teoretycy złożoności potrzebują znajomości kodowania. W artykule wspomnianym powyżej wyraźnie wykorzystano wyniki eksperymentów do uzupełnienia koncepcji teoretycznych; wymaga to kodowania. W każdym razie zajęło mi bardzo dużo czasu znalezienie projektu programistycznego, który jest tak blisko związany z centralną koncepcją informatyki teoretycznej. Mam nadzieję, że ten post może się przydać komuś, kto szuka podobnych wyników.
lgidwani