Pembicaraan inspirasional untuk siswa sekolah menengah tahun terakhir

Saya sering diminta oleh departemen saya untuk memberikan ceramah kepada siswa sekolah menengah tahun terakhir tentang lebih banyak unsur matematika dari ilmu komputer. Saya melakukan yang terbaik untuk memilih topik dari TCS yang mungkin menginspirasi minat mereka (yang sebagian besar melibatkan sesuatu yang berkaitan dengan masalah Penghentian) tetapi akan senang mendengar gagasan / keberhasilan / kegagalan orang lain.

Yang perlu diperhatikan adalah bahwa ini adalah siswa yang sedang mempertimbangkan melamar gelar sarjana CS di universitas yang layak tetapi mungkin lebih tertarik dengan matematika atau ilmu lainnya. Saya menemukan bahwa topik umum dari algoritma jalur terpendek atau metode penyortiran yang lebih cepat tidak benar-benar berfungsi lagi untuk menyurutkan minat mereka.

Ada cara yang rapi untuk memperkenalkan bukti nol-pengetahuan kepada siswa, yang saya pikir awalnya karena Oded Goldreich (tolong perbaiki saya jika saya salah).

Anda memiliki bola merah dan bola hijau, yang menurut Charlie warna kulit buta miskin adalah warna yang sama. Anda ingin meyakinkan Charlie bahwa Anda bisa membedakan bola merah dan bola hijau, dan Anda ingin melakukan ini dengan cara yang tidak dilakukan Charlie. dipelajari mana yang merah dan mana yang hijau. (Anda ingin membuktikan sesuatu itu benar, sedemikian rupa sehingga tidak ada orang lain yang dapat berbalik dan mengklaim bukti bahwa itu adalah milik mereka.) Bagaimana Anda dapat melakukan ini? Atau tidak mungkin?

Satu protokol adalah sebagai berikut. Charlie meletakkan bola di masing-masing tangan, lalu memilih untuk mengganti kedua bola di belakangnya, atau tidak. Lalu dia menyajikan dua bola lagi. Jika Anda selalu dapat mendeteksi apakah dia mengganti dua bola atau tidak, maka Charlie semakin yakin bahwa Anda dapat membedakan antara keduanya. Jika Charlie tidak acak ini secara acak dan Anda benar-benar tidak bisa membedakan antara warna, maka Anda hanya akan menebak dengan benar dengan probabilitas . Setelah k uji coba, Charlie harus yakin bahwa Anda dapat memberitahu perbedaan dengan probabilitas setidaknya 1 - 1 / 2 $1/2$$k$$1-1/2^k$ .

Sekarang sementara Charlie menjadi semakin yakin bahwa Anda dapat membedakannya, ia dengan frustrasi tidak pernah mengetahui bola mana yang berwarna merah dan mana yang berwarna hijau.

Sumber yang baik untuk tujuan pendidikan secara umum adalah CS tidak terhubung , yang memiliki banyak ide CS yang rapi diterjemahkan ke dalam kegiatan sekolah menengah dan menengah .

Salah satu aspek yang paling menarik dari TCS adalah bagaimana ia menggunakan ide-ide matematika abstrak untuk aplikasi praktis sehari-hari. Presentasi dapat fokus pada ide-ide abstrak yang terletak satu langkah di belakang apa yang mereka lihat setiap hari di Internet: Jalur terpendek menjadi menarik setelah ditempatkan dalam konteks teman-teman di Facebook. Lebih banyak algoritma grafik dapat digunakan pada Pagerank; Rekomendasi Amazon meningkatkan tantangan pembelajaran mesin; dan barang-barang yang dibeli di Internet jelas merupakan petunjuk yang baik untuk crypto kunci publik.

Saya pikir hampir semua topik dalam ilmu komputer dapat digunakan untuk memberikan ceramah yang menarik, tetapi beberapa lebih cocok, bagian yang lebih penting adalah presentasi.

Sisi Menyenangkan Ilmu Komputer

Saya telah menggunakan berbagai permainan dari Teori Permainan Kombinatorial, terutama dari "Permainan Adil" Richard Guy dan Elwyn R. Berlekamp, ​​John H. Conway, dan "Kemenangan Cara Richard Ways untuk Permainan Matematika Anda" ( wiki ).

Mereka menyenangkan , dan Anda dapat memainkannya di kelas bersama mereka dan membiarkan mereka menemukan cara yang tepat untuk memainkannya, berikan beberapa petunjuk sehingga pada akhirnya mereka menemukan cara untuk memenangkan permainan. Permainan ini mungkin lebih cocok untuk siswa yang lebih muda.

Ada topik menyenangkan lainnya dalam Ilmu Komputer di mana Anda dapat memilih masalah yang lebih cocok untuk audiens Anda dan menggunakannya untuk melibatkan mereka.

Sisi Filsafat Ilmu Komputer

Ada banyak topik dalam ilmu komputer teoretis yang terkait dengan filsafat dan pertanyaan besar . Dari teorema ketidaklengkapan Gödel ke bukti nol-pengetahuan, keamanan, privasi, teori permainan algoritmik, P vs NP, pembelajaran mesin, ... Saya tidak akan merinci, hanya menunjukkan bahwa masalahnya menarik, mereka lebih dari sekadar ilmu komputer , Mereka terkait dengan pertanyaan besar. (Lihatlah Komputasi Quantum Scott Aaronson Sejak Democritus dan Ide-Ide Besar dalam kuliah Ilmu Komputer Teoritis ). Jangan membuat mereka merasa seolah-olah topiknya sudah mati (yaitu semua pertanyaan dijawab), buat mereka merasa bahwa daerah itu hidup, sudah ada kemajuan tetapi masih ada tantangan besar di depan, dan itu adalah perjalanan ke tanah yang belum ditemukan.

Sisi Teknologi Ilmu Komputer

Bicara tentang ilmu komputer di balik teknologi. Ada begitu banyak topik yang dapat dipilih di sini, teknologi yang biasa digunakan dari video-game hingga pencarian Google, terjemahan mesin, visi, ... teknologi yang digunakan setiap orang setiap hari, atau bahkan yang tidak dikenal. Bicara tentang kemajuan dan teknologi generasi mendatang, tentang dampaknya terhadap kehidupan kita, dan bagaimana mereka memperbaikinya. Bicara tentang penelitian yang terjadi di perusahaan terkenal besar (seperti Google, Microsoft, Apple, IBM, ...) dan produk yang mereka kembangkan. Bicara tentang masalah besar pada zaman kita dan apa dampak ilmu komputer terhadapnya.

Sisi Matematika Ilmu Komputer

Ini bagus untuk siswa yang sudah tertarik pada matematika, mereka yang tertarik dengan murni dan tepat , tetapi tanpa menggabungkannya dengan tema lain yang disebutkan di atas, itu tidak akan efektif bagi siswa lain. Saya akan pergi dengan pertanyaan besar dan pada titik tertentu menyebutkan mulai berbicara tentang masalah matematika yang terlibat.

Sisi Interdisipliner Ilmu Komputer

Ilmu Komputer mungkin adalah salah satu mata pelajaran yang paling interdisipliner , ada beberapa hubungan dengan hampir semua mata pelajaran lainnya, humanistik (sosiologi, linguistik, ekonomi, filsafat, ...), ilmu alam (matematika, fisika, ...), biologi, ilmu kedokteran, seni, teknik (elektronik, mekanik, ...), ... apa saja! Apa pun topik yang Anda minati, ada sesuatu dalam ilmu komputer yang terkait dengannya! Seperti kata Scott, Every Other Major Sucks By Comparison :).

Mereka semua

Anda juga dapat mencoba menyebutkan semua tema yang telah saya sebutkan di atas. Saya belum mencoba ini, dan saya tidak yakin seberapa efektif itu. Anda harus mentransfer perasaan dan menegaskan maksudnya, dan itu butuh waktu. Satu pilihan lain adalah dengan menyebutkan semuanya secara singkat di awal (atau di akhir) dan kemudian melanjutkan dengan salah satunya, dan memberi tahu mereka bahwa mereka dapat menghubungi Anda untuk mendapatkan informasi lebih banyak tentang yang lain jika mereka tertarik.

beberapa komentar

Apa pun yang akan Anda bicarakan, Anda harus antusias . Akan jauh lebih sulit untuk menarik mereka pada topik yang tidak terlalu menarik bagi Anda. Beri tahu mereka alasan Anda memilih ilmu komputer. Dan jangan membosankan .

Saya telah menggunakan dua ceramah dengan cukup sukses dengan siswa sekolah menengah dan siswa baru.

1. Origami. Saya memimpin dengan masalah bintang 5 poin (ini bekerja dengan baik dalam konteks Amerika, karena koneksi ke bendera Amerika) dan membiarkan siswa mencoba mencari cara membuat bintang lima poin dengan lipat + 1 potongan. Saya berbicara tentang "sumber daya" (pemotongan) dan bagaimana desain algoritma bekerja dengan sumber daya terbatas. Lalu saya berbicara tentang pertanyaan dan aplikasi origami lainnya di dunia nyata (katup jantung, teleskop NASA, zona crumple di mobil).

2. Menyortir pancake: ada hubungan yang indah antara menyortir pancake dan penyusunan ulang genom, dan saya benar-benar membuat tumpukan pancake dari busa untuk dimainkan siswa. Bekerja dengan baik, dan izinkan saya berbicara tentang algoritme, pengurutan gen, Bill Gates (!), Dan hal-hal menyenangkan lainnya.

Kriptografi selalu merupakan sesuatu yang menangkap pikiran orang yang lebih muda (dan saya pribadi berharap lebih tua). Saya mempunyai teman-teman yang ingin menjadi asisten perawat, pemain hoki, pengusaha dan politisi dan teman-teman (yang meskipun memiliki tujuan yang lebih tinggi) mengambil pekerjaan sebagai pedagang kelontong dan pengangkut kereta, pekerja konstruksi dan asisten kandang - yang semuanya menemukan dan menghancurkan satu sama lain ' (diakui naif dan sederhana) kode. Secara khusus, keberadaan kriptografi kunci publik biasanya cukup mudah dijelaskan jika seseorang mengambil rute RSA. Orang mungkin juga membuat daftar beberapa hasil penting tanpa bukti atau konstruksi - Bukti Nol-Pengetahuan dan Enkripsi Homomorfik terikat untuk memeras faktor geek untuk apa nilainya.

Forward Error Correction dan Error Detection codes juga sangat keren dan jika dilakukan dengan benar dapat diajarkan kepada audiens yang penasaran. Untuk membuatnya lebih mudah dicerna, Anda dapat menyebutkan "universalitas" dari indeks kebetulan - bahwa semua bahasa dan tulisan kita memiliki redudansi kecil dan berlebihan yang membantu kita berkomunikasi dalam saluran bising dari sebuah ruangan yang berisi tas, kaki, dan tas pengocok. pendingin udara humming.

Akhirnya, saya juga menyarankan untuk melakukan pengantar sederhana untuk teori kompleksitas - sesuatu yang sejalan dengan jawaban saya untuk deskripsi Tabel Makan Malam dari Theoretical Computer Science .

Omnibus Turing Baru oleh AK Dewey memiliki 66 kunjungan yang disebut dalam ilmu komputer. Ini mencakup topik-topik seperti analisis algoritma, AI, teori kompleksitas, teori komputasi, kriptografi, grafik komputer dan sebagainya. Setiap topik ditulis dalam bentuk yang agak kental, menangkap beberapa hasil penting dalam ilmu komputer. Buku ini bisa memberikan inspirasi.

Kemungkinan lain adalah memungkinkan siswa untuk mengotori tangan mereka melalui sesuatu seperti program Code-in Google . Ini sedikit seperti Musim Panas Kode Google , tetapi, Anda tahu, untuk anak-anak. Mungkin menunjukkan beberapa proyek pengkodean luar biasa yang dapat dilibatkan siswa adalah salah satu cara yang mungkin untuk menarik minat.

Menurut pendapat saya, untuk menjadi seksi bagi siswa sekolah menengah, Anda harus menjadi semacam pesulap. Itu sebabnya saya berpikir bahwa algoritma acak sangat baik sebagai penarik siswa. Misalnya pengujian properti benar-benar sesuatu yang menarik, dan juga sesuatu yang dapat dijelaskan (bukan teknis, tetapi gagasan) kepada siapa pun.

PCP juga ajaib, tapi saya kira ini di luar jangkauan ...

Berikut ini adalah artikel yang sangat bagus tentang teori pengkodean yang ditujukan untuk siswa sekolah menengah oleh Michael Mitzenmacher:

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

Jawaban saya tidak terhubung langsung dengan TCS, tetapi dapat menunjukkan bahwa matematika dapat menjadi indah dan bermanfaat.

Anda bisa berpidato tentang cara mendapatkan data yang dapat diandalkan tentang berapa banyak siswa yang selingkuh pada ujian. Jika Anda bertanya secara langsung maka Anda tidak akan mendapatkan data yang dapat diandalkan. Gagasan tentang cara mendapatkan data yang andal sangat sederhana. Pertama Anda memberitahu setiap siswa untuk memikirkan beberapa bilangan bulat, maka Anda berkata:
- Jika itu angka ganjil, tulis apakah Anda suka warna hijau atau tidak. Anda dapat memilih pertanyaan sederhana lainnya, tetapi Anda harus tahu, dari beberapa survei lain, berapa persen orang yang menjawab ya pada pertanyaan ini.
- Jika nomor itu bahkan menuliskan apakah Anda curang atau tidak.

Sekitar 50% siswa akan menjawab pertanyaan pertama, dan 50% lainnya akan menjawab pertanyaan kedua. Sekarang sangat mudah untuk memperkirakan berapa banyak siswa yang selingkuh. Contoh: Jika 40% jawaban adalah ya, dan Anda tahu bahwa 30% orang menyukai warna hijau, maka Anda tahu bahwa sekitar 50% siswa berselingkuh.

Saya pikir ini terkait erat dengan deskripsi meja makan ilmu komputer teoritis?

Ketika saya memposting di sana saya merasa algoritme berhubungan dengan masalah terbaik setiap hari dan karenanya dapat memotivasi TCS dengan sangat baik. ("Berapa lama satu pencarian google akan memakan waktu jika mereka mencari dengan cara yang sama Anda mencari nomor telepon")

Menurut saya, "ilmu komputer" adalah "ilmu semua ilmu" :)

Apa itu "sains"? Kami mendapatkan data dari alam, dan kami mencoba membuat model yang menjelaskan data. Juga, kami berasumsi secara implisit bahwa alam tidak sewenang-wenang. Hukum-hukum alam harus memiliki ekspresi yang ringkas, data harus memenuhi beberapa simetri, dll.

Tapi ini justru masalah belajar! Data dihasilkan oleh beberapa proses yang dijanjikan memiliki "kompleksitas rendah", dan tugas kami adalah merekonstruksi deskripsi proses.

Pemahaman kami tentang masalah-masalah semacam itu berada pada tingkat primitif sehingga tugas Anda untuk mengatasinya! :) Bahkan pemahaman kita tentang masalah yang tampaknya lebih sederhana apakah output dari proses black-box setara dengan beberapa fungsi tetap masih jauh dari lengkap. Sebagai contoh, misalkan kita dijanjikan bahwa kotak hitam mengevaluasi fungsi yang dapat dihitung oleh sirkuit aritmatika kedalaman kecil (ini mudah dijelaskan kepada siswa sekolah menengah), dan kami ingin mengetahui apakah kotak tersebut menghitung fungsi nol. Kita tidak tahu apakah ini bisa dilakukan dalam masa kehidupan semesta untuk fungsi pada domain berukuran wajar!

Isyarat untuk mulai berbicara tentang teori kompleksitas aritmatika, jurang pada kedalaman 4, peran keacakan dalam perhitungan, apa yang diketahui jika kita mengurangi # gerbang multiplikasi, dll. Dll ...

Dalam lokakarya Algoritma di Lapangan sebulan yang lalu di DIMACS, Graham Cormode membantah mengajarkan teknik sketsa dari streaming algoritma ke sarjana. Moses Charikar mengatakan bahwa mereka mengajar mereka di Princeton, saya pikir @Suresh Venkat juga menyebutkan dia mengajarkan hal-hal seperti algoritma Misra-Gries untuk pemukul berat. Saya pikir beberapa hasil streaming dasar akan bagus untuk siswa sekolah menengah juga: mereka mengandalkan trik matematika dasar tetapi penting, rumusan masalahnya seperti teka-teki, dan solusinya terasa seperti sihir, dan sihir adalah cara yang bagus untuk menginspirasi siswa sekolah menengah. Anda dapat memastikan untuk menekankan perbedaan dramatis antara skala masalah dan jumlah sumber daya yang dapat Anda gunakan. Contoh konyol: anggaplah Anda dapat meminta setiap orang yang memasuki atau meninggalkan kode pos mereka di bandara JFK.