Inspirująca rozmowa dla uczniów ostatniej klasy liceum

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 / porażki innych ludzi.

Chodzi o to, że są to uczniowie, którzy rozważają ubieganie się o licencjat CS na przyzwoitym uniwersytecie, ale mogą być bardziej zainteresowani matematyką lub inną nauką. Uważam, że zwykłe tematy algorytmów najkrótszej ścieżki lub szybszych metod sortowania nie działają tak naprawdę, aby wzbudzić ich zainteresowanie.

Jest fajny sposób na przedstawienie studentom dowodów zerowej wiedzy, co, jak sądzę, pierwotnie wynika z Oded Goldreich (popraw mnie, jeśli się mylę).

Masz czerwoną i zieloną piłkę, którą biedny ślepy na kolory Charlie uważa za ten sam kolor. Chcesz przekonać Charliego, że potrafisz odróżnić czerwoną piłkę od zielonej i chcesz to zrobić w taki sposób, aby Charlie nie wiedział, która jest czerwona, a która zielona. (Chcesz udowodnić, że coś jest prawdą, w taki sposób, że nikt inny nie może się odwrócić i domagać się tego jako własnego). Jak możesz to zrobić? Czy to niemożliwe?

$1/2$$k$$1-1/2^k$

Teraz, gdy Charlie staje się coraz bardziej przekonany, że widać różnicę, frustrująco nigdy nie dowiaduje się, która piłka jest czerwona, a która zielona.

Źródło dobre dla celów edukacyjnych w ogóle jest CS unplugged , który ma wiele czystych idei CS przełożyło szkół średnich i gimnazjalnych działalności .

Jednym z najbardziej atrakcyjnych aspektów TCS jest sposób, w jaki wykorzystuje abstrakcyjne pomysły matematyczne do codziennych praktycznych zastosowań. Prezentacja może koncentrować się na abstrakcyjnych pomysłach, które leżą o krok za tym, co widzą codziennie w Internecie: najkrótsze ścieżki stają się ekscytujące, gdy zostaną umieszczone w kontekście znajomych na Facebooku. Więcej algorytmów graficznych może jeździć na Pagerank; Zalecenia Amazon podnoszą wyzwanie uczenia maszynowego; a kupowanie rzeczy w Internecie jest z pewnością dobrą drogą do szyfrowania z kluczem publicznym.

Myślę, że prawie każdy temat w informatyce może być użyty do wygłoszenia ciekawej rozmowy, ale niektóre są bardziej odpowiednie, tym ważniejsza jest prezentacja.

Zabawna strona informatyki

Korzystałem z różnych gier z teorii gier kombinacyjnych, głównie z „Fair Games” Richarda Guya i Elwyn R. Berlekamp, ​​Johna H. Conwaya oraz „Winning Ways for your Mathematical Plays” ( wiki ).

Są zabawne i można je odtworzyć w klasie z nimi i niech znaleźć właściwą drogę, aby go odtworzyć, dać kilka wskazówek, więc w końcu one znaleźć sposób, aby wygrać mecz. Te gry są prawdopodobnie bardziej odpowiednie dla młodszych uczniów.

W informatyce są inne zabawne tematy, w których możesz wybrać problem bardziej odpowiedni dla odbiorców i użyć go do ich zaangażowania.

Filozoficzna strona informatyki

W teoretycznej informatyce istnieje wiele tematów związanych z filozofią i dużymi pytaniami . Od twierdzenia o niekompletności Gödela po dowody zerowej wiedzy, bezpieczeństwo, prywatność, algorytmiczną teorię gier, P vs NP, uczenie maszynowe ... Nie wchodziłbym w szczegóły, tylko wykazałbym, że problemy są interesujące, są czymś więcej niż tylko informatyką są związane z dużymi pytaniami. (Zobacz wykłady Scott Aaronson Quantum Computing Since Democritus i Great Ideas In Theoretical Computer Science ). Nie każ im czuć, że temat jest martwy (tzn. Odpowiedziano na wszystkie pytania), spraw, aby czuli, że obszar jest żywy, poczyniono postępy, ale przed nami wciąż duże wyzwania i jest to podróż do nieodkrytej krainy.

Technologiczna strona informatyki

Porozmawiaj o informatyce stojącej za technologiami. Jest tak wiele tematów, które można tutaj wybrać, znane technologie, od gier wideo po wyszukiwanie w Google, tłumaczenie maszynowe, wizja, ... technologie, z których każdy korzysta każdego dnia, a nawet te nieznane. Porozmawiaj o technologiach w toku i nowej generacji, o wpływie, jaki wywarły one na nasze życie, oraz o tym, jak je ulepszyły. Porozmawiaj o badaniach prowadzonych w dużych znanych firmach (takich jak Google, Microsoft, Apple, IBM, ...) i produktach, które opracowują. Porozmawiaj o wielkich problemach naszych czasów i wpływie na nie informatyki.

Matematyczna strona informatyki

Jest to dobre dla studentów, którzy już interesują się matematyką, tych, którzy interesują się czystą i dokładną stroną, ale bez połączenia jej z innym tematem wspomnianym powyżej, nie będzie tak skuteczny dla innych uczniów. Postawiłbym duże pytanie i w pewnym momencie wspomniał o problemach matematycznych.

Interdyscyplinarna strona informatyki

Informatyka jest prawdopodobnie jednym z najbardziej interdyscyplinarnych przedmiotów, istnieje związek z prawie każdym innym przedmiotem, humanistycznym (socjologia, językoznawstwo, ekonomia, filozofia, ...), nauk przyrodniczych (matematyka, fizyka, ...), biologia, nauki medyczne, sztuka, inżynieria (elektronika, mechanika, ...), ... wszystko! Niezależnie od tego, jaki temat Cię interesuje, jest w tym coś związanego z informatyką! Jak powiedział Scott, Every Other Major Sucks By Compare :).

Wszyscy

Możesz także spróbować wymienić wszystkie motywy, o których wspomniałem powyżej. Nie próbowałem tego i nie jestem pewien, jak by to było skuteczne. Musisz przenieść to uczucie i zrozumieć, a to zajmuje trochę czasu. Inną opcją jest krótkie wspomnienie wszystkich z nich na początku (lub na końcu), a następnie przejście do jednej z nich i powiedzenie, że mogą się z Tobą skontaktować, aby uzyskać więcej informacji na temat pozostałych, jeśli są zainteresowani.

kilka komentarzy

Cokolwiek chcesz porozmawiać, powinieneś być entuzjastycznie nastawiony . Znacznie trudniej będzie zainteresować ich tematem, który nie jest dla ciebie interesujący. Powiedz im o swoich powodach wyboru informatyki. I nie bądź nudny .

Z powodzeniem przeprowadziłem dwie rozmowy zarówno z uczniami szkół średnich, jak i studentami pierwszego roku.

1. Origami Prowadzę problem z 5-punktową gwiazdą (działa to dobrze w amerykańskich kontekstach, ze względu na połączenie z amerykańską flagą) i pozwalam uczniom próbować wymyślić, jak zrobić pięciopunktową gwiazdę ze składaniem + 1 cięcie. Mówię o „zasobach” (wycinaniu) io tym, jak projektowanie algorytmów polega na pracy z ograniczonymi zasobami. Potem mówię o innych pytaniach i zastosowaniach związanych z origami w świecie rzeczywistym (zastawki serca, teleskopy NASA, strefy zgniotu w samochodach).

2. Sortowanie naleśników: istnieje piękny związek między sortowaniem naleśników a rearanżacją genomu, a ja właściwie zrobiłem stosy naleśników z pianki dla uczniów do zabawy. Działa świetnie i pozwala mi mówić o algorytmach, sekwencjonowaniu genów, Billa Gatesa (!) I innych zabawnych rzeczach.

Kryptografia jest zawsze czymś, co uchwyca umysł młodszych (i osobiście mam nadzieję, starszych) osób. Miałem przyjaciół, którzy chcieli być asystentkami pielęgniarek, hokeistami, biznesmenami i politykami oraz przyjaciółmi (którzy pomimo swoich wyższych celów) podejmowali pracę jako osoby zajmujące się pakowaniem artykułów spożywczych i pchaczy wózków, pracownicy budowlani i asystenci hodowli - wszyscy wymyślili i złamali się nawzajem ” (co prawda naiwne i proste) kody. W szczególności istnienie kryptografii z kluczem publicznym jest zwykle dość łatwe do wyjaśnienia, jeśli ktoś wybierze drogę RSA. Można również wymienić niektóre ważne wyniki bez dowodów lub konstrukcji - dowody zerowej wiedzy i szyfrowanie homomorficzne z pewnością skuszą czynnik maniaków za to, co jest warte.

Kody korekcji błędów i wykrywania błędów są również bardzo fajne i jeśli zrobisz to dobrze, możesz nauczyć ciekawskich odbiorców. Aby ułatwić ich przyswajanie, można wspomnieć o „uniwersalności” wskaźnika zbiegów okoliczności - że cały nasz język mówiony i pismo mają małe zwolnienia i przesady, które pomagają nam komunikować się w hałaśliwym kanale pokoju zawierającego tasujące torby, stopy i nucące klimatyzatory.

Na koniec zasugerowałbym także proste wprowadzenie do teorii złożoności - coś w stylu mojej odpowiedzi na opis teoretycznej informatyki na stole obiadowym .

Nowy Omnibus firmy Turing firmy AK Dewey ma 66 tak zwanych wycieczek z informatyki. Obejmuje takie tematy, jak analiza algorytmów, sztuczna inteligencja, teoria złożoności, teoria obliczeń, kryptografia, grafika komputerowa i tak dalej. Każdy temat jest napisany w dość skondensowanej formie, co stanowi pewien przełomowy wynik w dziedzinie informatyki. Ta książka może dostarczyć inspiracji.

Inną możliwością jest pozwolenie uczniom na zabrudzenie rąk za pomocą czegoś takiego jak program Google do kodowania . To trochę jak Google of Summer , ale wiesz, dla dzieci. Być może pokazanie niektórych niesamowitych projektów kodowania, w które mogą być zaangażowani studenci, jest jednym z możliwych sposobów wzbudzenia zainteresowania.

Moim zdaniem, aby być seksownym dla licealistów, musisz być jakimś magikiem. Dlatego uważam, że algorytmy randomizowane są bardzo dobre jako atraktor studencki. Na przykład testowanie właściwości jest naprawdę czymś intrygującym, a także czymś, co można wyjaśnić (nie szczegóły techniczne, ale pomysł) każdemu.

PCP to także magia, ale myślę, że jest to poza zasięgiem ...

Oto bardzo ładny artykuł na temat teorii kodowania skierowany do uczniów szkół średnich przez Michaela Mitzenmachera:

http://www.eecs.harvard.edu/~michaelm/FUTUREOFCS/codes-mitzenmacher.pdf

Moja odpowiedź nie jest bezpośrednio związana z TCS, ale może pokazać, że matematyka może być piękna i użyteczna.

Możesz wygłosić mowę na temat uzyskiwania wiarygodnych danych o tym, ilu uczniów oszukuje podczas egzaminu. Gdybyś zapytał ich bezpośrednio, nie uzyskałbyś wiarygodnych danych. Pomysł uzyskania wiarygodnych danych jest bardzo prosty. Najpierw każesz każdemu uczniowi pomyśleć o jakiejś liczbie całkowitej, a następnie mówisz:
- Jeśli była to liczba nieparzysta, zapisz, czy lubisz kolor zielony, czy nie. Możesz wybrać dowolne inne proste pytanie, ale musisz wiedzieć, z jakiejś innej ankiety, jaki procent ludzi odpowiada tak na to pytanie.
- Jeśli to była parzysta liczba, zapisz czy oszukujesz czy nie.

Około 50% studentów udzieli odpowiedzi na pierwsze pytanie, a pozostałe 50% udzieli odpowiedzi na drugie pytanie. Teraz bardzo łatwo jest oszacować, ilu uczniów oszukuje. Przykład: Jeśli 40% odpowiedzi brzmi „tak” i wiesz, że 30% ludzi lubi zielony kolor, to wiesz, że około 50% uczniów oszukuje.

Myślę, że jest to ściśle związane z opisem teoretycznej informatyki przy stole?

Jak pisałem tam, czuję, że algorytm najlepiej łączy się z codziennymi problemami i dlatego może bardzo dobrze motywować TCS. („Jak długo zajęłoby jedno wyszukiwanie w Google, gdyby wyszukiwały w taki sam sposób, w jaki wyszukujesz numery telefonów”)

Według mnie „informatyka” to „nauka wszystkich nauk” :)

Czym jest nauka"? Otrzymujemy dane z natury i staramy się zbudować model, który je objaśnia. Ponadto domyślnie zakładamy, że natura nie jest arbitralna. Prawa przyrody muszą mieć zwięzłe wyrażenie, dane muszą spełniać pewne symetrie itp.

Ale to jest właśnie problem uczenia się! Dane są generowane przez jakiś proces, który ma być „niskiej złożoności”, a naszym zadaniem jest odtworzenie opisu procesu.

Nasze rozumienie takich problemów jest na tak prymitywnym poziomie, że Twoim obowiązkiem jest nad nimi pracować! :) Nawet nasze zrozumienie pozornie prostszego problemu, czy wyjście procesu czarnej skrzynki jest równoważne z jakąś stałą funkcją, jest dalekie od ukończenia. Załóżmy na przykład, że obiecano nam, że czarna skrzynka ocenia funkcję, którą można obliczyć na małej głębokości obwodu arytmetycznego (jest to łatwe do wyjaśnienia dla uczniów szkół średnich) i chcemy dowiedzieć się, czy skrzynka jest obliczanie funkcji zerowej. Nie wiemy, czy można tego dokonać za życia wszechświata dla funkcji w domenach o rozsądnych rozmiarach!

Zacznij mówić o teorii złożoności arytmetycznej, otchłani na głębokości 4, roli losowości w obliczeniach, co wiadomo, jeśli zmniejszymy liczbę bramek mnożenia itp. Itd.

Na warsztatach Algorytmy w terenie miesiąc temu w DIMACS Graham Cormode opowiadał się za nauczeniem technik szkicowania, od algorytmów strumieniowych po studentów. Moses Charikar powiedział, że uczą ich w Princeton, myślę, że @Suresh Venkat również wspomniał, że uczy takich rzeczy, jak algorytm Misra-Gries dla ciężkich uderzeń. Myślę, że niektóre podstawowe wyniki streamowania byłyby również świetne dla uczniów szkół średnich: opierają się na podstawowych, ale ważnych sztuczkach matematycznych, formułowanie problemów jest jak puzzle, a rozwiązania są jak magia, a magia to świetny sposób, aby zainspirować uczniów szkół średnich. Możesz koniecznie podkreślić dramatyczną różnicę między skalą problemu a ilością zasobów, których możesz użyć. Głupi przykład: załóżmy, że możesz poprosić każdą osobę wchodzącą lub wychodzącą z lotniska JFK o podanie kodu pocztowego.