Opis teoretycznego informatyki na stole?

Często jestem pytany, co robi teoretyczny informatyk. Byłoby wspaniale mieć kilka miłych odpowiedzi na to pytanie. Zwykle wracam do technicznego żargonu, a oczy ludzi zwykle w tym momencie się błyszczą.

Co robi teoretyczny informatyk w kategoriach zrozumiałych dla osób niebędących informatykami?

Dobra odpowiedź powinna być zgryźliwa, dokładna w duchu, bez brzmienia niejasnego lub banalnego. W przypadku punktów bonusowych odpowiedź powinna wskazywać, dlaczego teoretyczny informatyk nie jest ani matematykiem, ani informatykiem.

To pytanie jest inspirowane pytaniem MO https://mathoverflow.net/questions/3559/colloquial-catchy-statements-encoding-serious-mathematics, chociaż intencja jest inna.

Moja odpowiedź brzmi: „Studiuję, dlaczego niektóre obliczenia są trudne do wykonania”. Jako przykład zazwyczaj porównuję dodawanie i mnożenie przy użyciu standardowych metod szkolnych. Są to obliczenia, które wszyscy wykonali i każdy docenia wartość szybkiego wykonywania. Wszyscy zgadzają się, że w przypadku dużych liczb mnożenie jest znacznie trudniejsze niż dodawanie. W rzeczywistości większość ludzi sugeruje, że metoda szkoły podstawowej jest tak szybka, jak to tylko możliwe. Pytam ich dlaczego. Skąd wiedzą, że nie ma innego sposobu na pomnożenie, który byłby tak prosty jak dodawanie?

Prawie wszyscy w tym momencie przynajmniej doceniają trudność udowodnienia dolnych granic (moje szczególne zainteresowanie), mimo że nie użyłem tego terminu. W zależności od tła i zainteresowania odbiorców mogę wspomnieć, że ktoś znalazł sposób na pomnożenie, który jest znacznie szybszy niż metoda szkoły podstawowej (po prostu słowo „algorytm” ma tendencję do rzucania szkliwa na oczy), ale wciąż wolniej niż dodawanie.

Daję ludziom konkretny przykład. W szczególności często motywuję teorię złożoności tym samym bardzo ilustracyjnym (ale prostym) problemem. Pytam publiczność, w jaki sposób poinstruują małe dziecko, aby odkryło, czy jego imię znajduje się na alfabetycznie uporządkowanej liście nazwisk (i mówię, że dziecko potrzebuje 3 sekundy na porównanie jednego imienia z drugim). Często zdarza się, że osoba / grupa zaproponuje naiwne, liniowe podejście. Zmuszam rozmowę do przejścia do algorytmu logarytmicznego (mógłbym użyć innego słowa niż logarytm) albo przez poproszenie osoby o coś lepszego, albo przez sam o tym wspominając. Pokazuję im, jak podwojenie wielkości listy dodaje dziecku trzy sekundy pracy dzięki nowemu podejściu. Porównuję to bezpośrednio z wersją liniową, która teraz będzie wydawać się całkowicie głupia.

Oczywiście sprowadzam go z powrotem na ziemię. Mówię im, że dane dziecko to na ogół komputer, ale może to być dziecko, a właściwie każdy. To, że zadajemy pytania, tak naprawdę nie dotyczy komputerów, ale więcej miejsca, czasu i informacji potrzebnych do rozwiązania problemów. Motywuję analizę złożoności przez analogię do dwóch różnych metod rozwiązania tego samego problemu.

Kiedy mam ich uwagę - wydobywam ciężkie uderzenia. Pytam ich: „czy możesz udowodnić, że rozwiązanie logarytmiczne jest najlepsze, co możesz kiedykolwiek zrobić, czy możesz znaleźć coś lepszego?” i pytam ich: „czy są jakieś problemy, których żaden proces (algorytm) nie może rozwiązać?” Byłem zaskoczony, jak ludzie próbują rozwiązać te pytania, gdy nie mają doświadczenia w TCS.

Podoba mi się ten post Scotta Aaronsona , który wyjaśnia teorię złożoności jako teologię ilościową. Oto fragment:

Teoria złożoności obliczeniowej naprawdę, naprawdę, naprawdę nie dotyczy komputerów. Komputery odgrywają tę samą rolę w złożoności, jaką zegary, pociągi i windy odgrywają w teorii względności. Są świetnym sposobem na zilustrowanie punktu, prawdopodobnie były niezbędne do odkrycia punktu, ale nie o to chodzi.

Najlepsza definicja teorii złożoności, jaką mogę sobie wyobrazić, to teologia ilościowa: matematyczne badanie hipotetycznych superinteligentnych istot, takich jak bogowie. Obawy dotyczą:

• Jeśli istniał Bóg lub bogowie, jak mogliby się objawić śmiertelnikom? (IP = PSPACE lub MIP = NEXP w przypadku politeistycznym).

• Którzy bogowie są potężniejsi niż inni bogowie? (P ^NP vs. PP, SZK vs. QMA, BQP ^NP vs. NP ^BQP itp.)

• Czy wspaniałomyślny Bóg może obdarzyć śmiertelnika swoją wszechwiedzą? (EXP vs. P / poli.)

• Czy można ufać wyroczniom? (Czy można ufać wyroczniom?)

I oczywiście:

• Czy śmiertelnicy mogliby kiedykolwiek stać się podobni do boga? (P vs. NP, BQP vs. NP.)

Przykładowa odpowiedź, którą zdecydowanie można poprawić:

Informatycy teoretyczni badają obliczenia w kategoriach matematycznych. Mogą naprawić Twój komputer, a matematycy mogą obliczyć twoje podatki.

Myślę, że Dijkstra podała doskonałą (nie) odpowiedź na te pytania (zawsze dobre źródło, do którego można się zwrócić po chrupiące i absolutne wypowiedzi :)).

Informatyka to nie tylko komputery, ale astronomia to teleskopy. - EW Dijkstra

Bardzo podoba mi się wprowadzenie do problemu partycjonowania jak podano Brian Hayes danego tutaj .

Używa problemu podzielenia zestawu dzieci na zespoły o równej całkowitej zdolności (zakładając, że można oszacować zdolność każdego dziecka za pomocą liczby), a także wyjaśnia chciwy algorytm zwykle używany przez dzieci do rozwiązania tego problemu.

Jest to bardzo prosty problem do zrozumienia, łatwo jest zrozumieć algorytm, zaskakujący, że jest (najprawdopodobniej) bardzo trudny ogólnie i zawstydzający, że wciąż nie jesteśmy w stanie udowodnić ostatniego kawałka.

Zwykle odpowiadam w następujący sposób: staram się dowiedzieć, co można zrobić z komputerem. Nie jest całkowicie dokładne, ale jest dość blisko i zwykle ludzie pytają coś w stylu „Co masz na myśli?” i mogę odnieść się do czegoś konkretnego, takiego jak TSP. Chociaż zmieniam sformułowanie podróżującego sprzedawcę jako, powiedzmy, problem podskakiwania przy barach, problem pośrednika w obrocie nieruchomościami, problem zbyt wielu spraw do załatwienia, za mało czasu lub cokolwiek, co wydaje się właściwe.

Na przykład: „Cóż, powiedzmy, że musisz kupować buty, artykuły spożywcze i ubrania, podnieść ciasto, uzyskać fryzurę i wykonać kilka innych spraw przed kolacją. Byłoby wspaniale, gdybyś mógł umieścić wszystkie te rzeczy do GPS i może ci powiedzieć, w jakiej kolejności wykonywać wszystkie twoje sprawy do godziny 4. Ale jeśli lista spraw jest wystarczająco długa, nie jest nawet możliwe, aby dowiedzieć się, czy mogę to zrobić w ogóle o 4 , a tym bardziej w jakiej kolejności musisz je wykonać w rozsądnym czasie. Chcę wiedzieć, czy można szybko rozwiązać ten problem za pomocą komputera. ”

Jakie są najlepsze sposoby rozwiązywania problemów i jakie problemy są zbyt trudne do rozwiązania? W językach europejskich jest słowo - w tym angielski! -- "Informatyka." Nauka informacji. W USA nazywamy to informatyką teoretyczną z powodu silnego przemysłu komputerowego, ale pomyślmy przez chwilę o rozwiązywaniu problemów bez komputerów. Rozważ ludzkie ciało. Rozwiązuje problemy w niemal cudowny sposób. Światło wpada do naszych oczu i widzimy rzeczy, które rozpoznajemy . Dźwięk dociera do naszych uszu i słyszymy słowa, które rozumiemy . Są to problemy informacyjne, które rozwiązujemy łatwo, tysiące razy dziennie, z którymi wciąż zmagają się najlepsze komputery na świecie.

Miliony lat zajęło proces ewolucji, aby rozwiązać te problemy, stosując strategię prób i błędów i eliminując pecha. Wyobraź sobie, co moglibyśmy osiągnąć, gdybyśmy przyjęli bardziej racjonalne podejście i zainwestowali tyle ludzkiej kreatywności w tę nową naukę rozwiązywania problemów, ile zainwestowaliśmy w geometrię, teologię lub rachunek różniczkowy. To, co robię, to niewielka część tej inwestycji.

W odpowiedzi na pytanie laika: „Czym się zajmujesz?” Często odpowiadałem: „Spędzam dużo czasu, wpatrując się w kosmos, zastanawiając się, jak zrealizować science fiction”. Następnie podaję konkretny przykład projektu, wyjaśniony w kilku zdaniach.

Informatyka teoretyczna to informatyka, czym matematyka była dla fizyki.

Zazwyczaj udzielam następującej odpowiedzi, aczkolwiek skoncentrowanej na teorii złożoności: „Studiuję granice pod względem przestrzeni i czasu, aby rozwiązać problem. Problemy obejmują znalezienie najkrótszej ścieżki na mapie lub wygraną w szachy”.

Zwykle podam problem faktoringowy jako przykład; Najpierw proszę o liczbę dzielącą 15; zazwyczaj ludzie mogą odpowiedzieć na 3, 5 i dobrze się bawić, zastanawiając się, czy 1 i 15 są poprawną odpowiedzią. Następnie podaję ogromną liczbę (więcej niż 10 cyfr) i pytam, czy mogą mi powiedzieć, jakie są dzielniki; i wyjaśniam, że nawet dla informatyków jest to naprawdę trudne pytanie.

Następnie, jeśli mam czas, staram się wyjaśnić, że chodzi o to, aby dowiedzieć się, jak rozwiązać ten problem, lub udowodnić, że zawsze zajmie to dużo czasu (pojęcie, które dokładnie umiemy zdefiniować). A potem kilka słów o kryptografii, aby wyjaśnić, dlaczego jest używana, i słowo o tym, ile czasu zajmuje zespołowi naukowców złamanie klucza liczby setkami cyfr (unikam mówienia o bitach, ponieważ ludzie wydają się lepiej wiedzieć co to jest cyfra)

Zadane pytanie jest naprawdę trudne, ponieważ większość ludzi nie ma pojęcia, co robią informatycy. To bardzo różni się od innych dyscyplin.

Lubię używać następującej analogii: (T) CS jest dla komputerów tym, czym fizyka jest dla odtwarzaczy CD (tj. Lasera). To faktycznie działa całkiem dobrze, ponieważ większość ludzi ma pojęcie o tym, czym zajmuje się fizyk, czy to poprawne, czy nie.

Bardziej szczegółowe przykłady obejmują rzeczy, z którymi większość ludzi może się odnosić

• Dopasowywanie ciągów (powolne naiwne podejście a codzienne szybkie wyszukiwanie w Word, przeglądarce, ...)
• Problem najkrótszej ścieżki (stosowany w systemach nawigacyjnych)
• Planowanie (w zależności od stopnia nerwowości drugiej osoby, odnoszą się do procesów biznesowych lub planowania na CPU)

Wyjaśniłbym wtedy, że podczas gdy ludzie PCS dbają o szybką implementację lub dobrą integrację w złożonych systemach, ludzie TCS zastanawiają się, co jest możliwe i dowodzą rzeczy, które zapewniają bezpieczną wiedzę / techniki wielokrotnego użytku dla PCS.

Możesz także wykorzystać frustrację ludzi związaną z komputerami („Nie robi tego, co chcę!”). Możesz zauważyć, że (T) CS zajmuje się tym, jak wyrażać rzeczy w sposób, w jaki komputery mogą rozumieć i wydajnie przetwarzać (odnosząc się do składni, semantyki, struktur danych, algorytmów).

Gdy ktoś zadaje ci pytanie, możesz albo odpowiedzieć bezpośrednio, albo dać mu krok po kroku procedurę postępowania i dowód, że jeśli kroki zostaną wykonane dokładnie, odpowiedź zostanie uzyskana w rozsądnym czasie. Biorąc pod uwagę, że same kroki nie są zbyt skomplikowane i mogą być wykonane szybko przez byt zdolny do istnienia w tym wszechświecie, jakie rodzaje pytań przedstawiają takie procedury? Myślę, że jest to przedmiot teoretycznej informatyki.

Moja zwykła odpowiedź, która nie jest zgryźliwa, ale gwarantuje zatrzymanie martwej rozmowy (bonus!) Brzmi: „jak teoria kwantowa jest matematycznym rdzeniem fizyki, TCS jest matematycznym rdzeniem informatyki”.

Badamy granice obliczeń. Jak szybko możesz rozwiązać określony problem obliczeniowy? Ile czasu potrzeba na jego rozwiązanie, bez względu na to, jakie rozwiązanie spróbujesz? Następnie podam im te przykłady (które są łatwe do wyjaśnienia większości laików - i rzeczywiście wielu laików ma z nimi bezpośrednie doświadczenie - wykazują pewne właściwości problemów z NP-zupełnością i faktycznie mają związek z ratowaniem życia).

Oczywiście ludzie (w tym ja) mogą żartować, że zignorowałem ważne inne zasoby, takie jak przestrzeń, losowość, a nawet kwantowość. Ale kiedy masz tylko 2 minuty, aby powiedzieć komuś o całym polu, niektóre rzeczy zostają pominięte.

Jeśli chcesz spojrzeć kapryśnie w przeszłość, przypomnij swoim odbiorcom, że „komputer” odnosi się do osoby, której zawód polegał na obliczeniach . (Jeśli chcesz naruszyć niektóre stereotypy związane z płcią, możesz zauważyć, że często były to również kobiety).

Następnie możesz osiągnąć garść rzeczy naraz:

• przedstawić przekonujący argument, że „informatyka” może być czymś więcej niż studiowaniem „komputerów”;
• zwracają uwagę, że osoby obliczające potrzebują pewnych zasad, aby wykonać swoje zadanie (szczególnie w pomieszczeniu pełnym „komputerów” wykonujących specjalistyczne zadania - złożoność i równoległość komunikacji, ktoś?), i to samo dotyczy maszyn;
• opisać, że „informatyka” polega na znalezieniu skutecznych sposobów rozwiązywania problemów związanych z „przetwarzaniem” w tym sensie;
• postawmy sprawę, że to, co dokładnie robi przetwarzanie komputerowe, nie jest tak ważne, jak potrzebne zasoby (takie jak czas i przestrzeń na zarysowania).

Zawsze zaczynam od skierowania ich na jakieś kreatywne, celowo lekceważące wideo lub artykuł wyjaśniający koncepcję techniczną na poziomie intuicyjnym. Oto dobry przykład: Doodling in Math: Spirals, Fibonacci i Being a Plant

Kiedy zrozumieją tę koncepcję (i mam nadzieję, że trochę się z tym bawią), próbuję uogólnić to, czego się nauczyli na temat TCS. Na przykład powyższe wideo może prowadzić do podstawowego wyjaśnienia algorytmów lub obliczeń jako procesu rekurencyjnego - „czegoś, co generuje złożoną strukturę z kilku prostych zasad”. Ludzie z TCS po prostu badają, jakie rodzaje reguł tworzą, jakie typy konstrukcji!

Od tego momentu przejście od ogólnego TCS do czynności specyficznych dla domeny jest dość łatwe. :)

Zgodnie z sugestią Rossa Snidera, aby rozpocząć od konkretnego przykładu, można również bezpośrednio wyjaśnić pytanie P vs NP. Można opisać to pytanie laikowi jako zastanawianie się, czy weryfikacja rozwiązania jest łatwiejsza niż znalezienie go, czy też jest prawdą, że ilekroć możemy zweryfikować rozwiązanie, my również możemy je znaleźć?

To moje:

Informatyka to nie tylko nauka, jest w niej dużo inżynierii, ale część naukowa dotyczy zrozumienia obliczeń. A obliczenia to fizyczny proces, który generuje informacje w uporządkowany sposób. W informatyce teoretycznej uważamy, że potrzebujemy stosunkowo wyrafinowanej matematyki, aby zrozumieć obliczenia.

Ładnie prowadzi do mówienia o obliczeniach w biologii, roli logiki w informatyce itp.

Może można tak powiedzieć

teoretyczny informatyk bada naprawdę trudne problemy związane z informatyką.

Naukowiec nie będzie używał komputera będąc kreatywnym, ale raczej dużo myśli, wypisze formuły i dziwaczne rysunki na papierze, a czasem błąka się po okolicy. W związku z tym bezpośrednia praktyczność nie jest najważniejsza, bardziej przypomina artystę badającego i próbującego zrozumieć tajemnice tego świata.

Następnie można wspomnieć o rzeczach, które opierają się na eleganckich rozwiązaniach teoretyków, takich jak komputer, internet, wyszukiwarki, bezpieczna bankowość, filmy 3D, sekwencjonowanie DNA itp. Ale zawsze należy podkreślić, że nikt jeszcze nie zna zastosowań dzisiejszych badań, niektóre z nich można po raz pierwszy zobaczyć za kilka dziesięcioleci.

Z mojego doświadczenia wynika, że ​​wiele osób ma moment AHA, kiedy zdaje sobie sprawę, że informatyka, a teoria w szczególności jest tak bogata w ciekawe pytania i problemy do studiowania. Wiele z nich można opisać na wysokim poziomie! Oto lista prof. Wikipedii (za pośrednictwem SIGACT), wybierz swoje ulubione: algorytmy, struktury danych, teorię złożoności obliczeniowej, obliczenia rozproszone, obliczenia równoległe, VLSI, uczenie maszynowe, biologia obliczeniowa, geometria obliczeniowa, teoria informacji, kryptografia, obliczenia kwantowe , obliczeniowa teoria liczb i algebra, semantyka i weryfikacja programu, teoria automatów i badanie losowości.

Co robi teoretyczny informatyk w kategoriach zrozumiałych dla osób niebędących informatykami?

Prawie tak samo jak specjalista od magnetowidów. Oba zastanawiają się, jak uzyskać najlepszą wydajność maszyn, które odczytują i zapisują informacje na wyjątkowo długich odcinkach taśmy.

To może być trochę więcej języka w policzek niż to, czego chciałeś ...