[MUSIC PLAYING] 

SPEAKER 1: Baiklah, ini adalah CS50, dan ini adalah awal minggu keempat, dan karena Anda mungkin telah mendengar atau membaca, dunia telah berakhir. Pergi di sekitar internet memiliki menjadi pengetahuan dan kesadaran bug dalam program, a bahasa pemrograman yang disebut Bash. Ini telah mengagumkan bermerek sebagai SHELLSHOCK, atau pintu Bash, tapi artikel seperti ini belum biasa. Dan pada kenyataannya, banyak dari mereka membawa kenangan belakang Heartbleed, yang Anda mungkin telah memperhatikan dalam tekan kembali pada musim semi lalu, yang adalah sama cukup dramatis. Sekarang orang-orang dari Anda di sini hari ini, berapa banyak dari Anda miliki, bahkan jika Anda tidak mengerti apa itu semua tentang, mendengar SHELLSHOCK? Baiklah, dan berapa banyak dari Anda memiliki komputer yang rentan? OK, harus ada jauh, jauh lebih banyak tangan up sekarang, untuk alasan yang akan kita lihat. 

Mari kita lihat apa yang telah terjadi di media dan kemudian menjelaskannya sedikit di sini untuk kita secara teknis. 

SPEAKER 2: Para ahli keamanan telah memperingatkan bahwa kekurangan yang serius bisa menjadi sekitar untuk mempengaruhi ratusan jutaan pengguna web di dunia. Jadi apa sebenarnya adalah bug yang sudah dijuluki SHELLSHOCK, dan apa fungsinya? Nah, SHELLSHOCK juga dikenal sebagai Bug Bash, perangkat lunak yang memanfaatkan. Hacker menggunakan virus untuk memindai rentan sistem yang menjalankan Linux dan Unix sistem operasi dan kemudian menginfeksi mereka. Bash adalah shell baris perintah. Hal ini memungkinkan pengguna mengeluarkan perintah untuk memulai program dan fitur dalam perangkat lunak dengan mengetik teks. Ini biasanya digunakan oleh para programmer, dan tidak harus terbuka ke dunia yang lebih luas, meskipun SHELLSHOCK perubahan itu. 

Nah, worringly, beberapa analis memperingatkan itu bisa menjadi ancaman yang lebih besar, karena SHELLSHOCK memungkinkan lengkap kontrol mesin yang terinfeksi, sedangkan Heartbleed hanya diperbolehkan hacker untuk memata-matai komputer. Ini sangat serius, itu telah dinilai 10 dari 10 untuk keparahan oleh National Kerentanan Database. 2/3 semua server web di risiko, termasuk beberapa komputer Mac. Nah, pastikan Anda menambal sistem Anda. Siapapun hosting menjalankan situs web sistem operasi yang terkena dampak harus mengambil tindakan sesegera mungkin. Siapa pun yang mampu membelinya harus melihat untuk monitoring dan web aplikasi mereka firewall untuk melihat keluar untuk setiap serangan. SPEAKER 3: Hal terburuk yang bisa terjadi adalah bahwa seseorang akan menulis kode yang akan secara otomatis pergi dan memindai internet dan akan mempengaruhi semua komputer. Dan setelah mereka melakukannya, baik, hal terburuk yang bisa mereka lakukan hanya menghapus semuanya, atau menutup situs bawah. Jadi kita bisa melihat kerusakan dari sudut pandang, di mana kita akan memiliki orang-orang jahat yang baru saja memutuskan untuk menyebabkan kerusakan dengan membawa sistem ke bawah atau menghapus file, dan hal-hal seperti itu. SPEAKER 2: Beberapa orang mengatakan ini adalah salah satu yang paling sulit untuk mengukur bug di tahun, dan itu mungkin waktu berminggu-minggu atau bahkan bulan untuk menentukan dampak utamanya. 

SPEAKER 1: Jadi semua itu benar, tapi lucunya, hampir semua citra Anda hanya melihat, kecuali mungkin keyboard, tidak ada hubungannya dengan bug apapun. Server dan kabel dan sebagainya, itu semacam tangensial terkait, tapi pada intinya itu sebenarnya cukup familiar apa yang terjadi di sini. Bahkan, biarkan aku pergi ke alat CS50 kami. Biarkan aku pergi ke depan dan memaksimalkan jendela terminal di sini. Dan kalian telah menggunakan ini, atau versi tertanam padanya, di gedit untuk menulis program, mengetik perintah, dan sebagainya, dan ini sebenarnya, dan memiliki berkunjung selama berminggu-minggu, Bash, B-A-S-H. Ini adalah Bourne-lagi shell, yang hanya cara mewah mengatakan, ini adalah program yang memiliki berkedip cepat, efektif, yang duduk di sana menunggu untuk masukan bagi Anda. Dan itu perintah antarmuka baris via yang kalian telah menjalankan perintah dan akhirnya kompilasi dan kemudian berjalan program. 

Tapi Bash juga pemrograman sebuah bahasa dalam arti berikut. Anda tahu bahwa ada perintah seperti cd dan ls dan juga dentang dan lain-lain, tetapi Anda dapat menentukan perintah Anda sendiri dengan menerapkan mereka di Bash. Sekarang kita tidak akan pergi ke detail untuk Bash bahasa pemrograman, tetapi tahu, misalnya, bahwa pada saat ini, tidak ada perintah yang disebut "halo." Jadi dapat ditemukan di salah satu dari paket ini. Ini tidak terinstal di komputer saya. Tanyakan administrator Anda. Tetapi jika saya ingin ada program disebut "halo" di Bash atau pada prompt saya, Aku benar-benar dapat menggunakan sintaks yang cukup seperti C. Ini tidak persis sama, tapi tampaknya cukup mirip dengan fungsi, meskipun kehilangan beberapa rincian. Tidak ada yang tampaknya terjadi, tapi jika saya ketik "Halo," Anda benar-benar dapat menulis Program, bukan di C, bukan di Jawa, tidak dalam pemrograman lain bahasa, namun di Bash sendiri. 

Sekarang kunci di sini adalah bahwa saya menulis nama saya ingin memberikan perintah baru ini, dan tanda kurung juga simbolis ini menjadi fungsi. Sebagai samping, Anda juga dapat melakukan menyenangkan hal, dan pada kenyataannya, bahkan pada Mac OS, ini adalah sebuah program yang disebut Terminal. Muncul dibangun ke siapa pun komputer yang memiliki Mac di ruangan ini, dan Anda dapat melakukan hal-hal serupa di Mac OS, tapi Anda dapat pergi lebih lebih dari itu. Dan ini sedikit tangensial, tapi itu semacam menyenangkan. Aku teringat pagi ini, ketika berpikir ini melalui, dari sedikit permainan saya gunakan untuk bermain dengan salah satu mantan TF CS50 ini dimana setiap saat dia akan berjalan kaki dari keyboard-nya dengan layar nya dibuka, Saya akan menjalankan perintah seperti ini-- "menyapa." Dan sekarang setiap kali dia kembali ke nya Keyboard setelah aku membersihkan layar dan ia akan duduk, mencoba untuk melakukan beberapa pekerjaan, daftar isi directory-- nya 

[AUDIO PLAYBACK] 

-Halo. Hello. 

SPEAKER 1: Jadi, dalam keadilan, itu tidak benar-benar "Halo." Itu biasanya sesuatu lebih mirip dengan itu-- [AUDIO PLAYBACK] -Beep. SPEAKER 1: -yang saya would-- sehingga komputer akan bersumpah padanya setiap saat dia benar-benar duduk di keyboard-nya. Dan sangat cepat ia tahu tidak meninggalkan layar nya dibuka. Tapi ini menunjukkan semacam itu bodoh menyenangkan bahwa Anda dapat memiliki dengan sesuatu seperti Bash. Tapi itu sedikit lebih serius, untuk memastikan, dari itu. Dan pada kenyataannya, ini adalah salah satu kebanyakan bug berbahaya dan tahan lama yang telah benar-benar melanda dunia secara global. Bug ini telah ada selama 20 tahun, dan Anda akan memukul hanya dalam saat ke relatif sederhana. 

Jadi ini adalah perwakilan perintah bahwa jika Anda memiliki Mac, benar-benar tepat sekarang ketika Anda memiliki tutup terbuka, Anda dapat mencoba mengetik ke dalam program yang disebut Terminal. Terminal berada di bawah Aplikasi Utilities-- untuk sekali, pengguna Windows tidak perlu khawatir tentang threat-- tertentu tapi bagi anda dengan Mac dapat mengetik ini ke jendela seperti aku akan lakukan di sini, dan jika Anda mengetik bahwa dalam program ini disebut Terminal, seperti aku akan lakukan sekarang, jika Anda melihat kata "rentan," komputer Anda rentan terhadap eksploitasi. 

Sekarang apa yang benar-benar berarti? Dan ini diakui beberapa sintaks cukup gila, tapi mari kita setidaknya menarik keluar beberapa aspek yang menarik. Jadi ada beberapa sintaks yang terlihat sedikit akrab, setidaknya dari C dan pemrograman lebih umum. Saya melihat beberapa tanda kurung, koma, kurung kurawal, dan semacamnya, tapi ternyata ini hal bodoh di sini dengan warna kuning pada dasarnya fungsi yang tidak apa-apa. Kolon berarti melakukan apa-apa, dan koma berarti berhenti melakukan apa-apa. Jadi dalam ini kurung kurawal, fakta bahwa saya memiliki sama tanda ke kiri, ini pada dasarnya menciptakan perintah, atau variabel, disebut x, dan menugaskan yang sedikit kuning kode sana. Itu bisa menjadi sesuatu seperti "echo halo "atau" mengatakan bip "atau sesuatu mirip dengan itu. Tapi perhatikan jika mata Anda mengembara jauh ke kanan, masih ada lagi untuk baris ini dari hanya akhir titik koma itu. "Echo rentan," dan kemudian di luar itu ada bahkan lebih. Lain titik koma, bash-c :. 

Jadi cerita panjang pendek, baris kode adalah cukup untuk menarik komputer yang rentan terhadap melakukan sesuatu yang ingin Anda untuk melakukan, karena ada bug di Bash dimana meskipun Bash seharusnya berhenti membaca baris perintah yang tepat di sana setelah teks kuning, untuk tahun 20-plus bug tua, Bash sebenarnya sudah membaca di luar titik koma itu dan cukup banyak melakukan apa yang diperintahkan. 

Jadi apa implikasi dari yang pada akhirnya? Aku hanya berkata "echo hello" atau "echo rentan," tetapi bagaimana jika Anda melakukan sesuatu benar-benar berbahaya, seperti rm-rf *, yang tidak Anda mungkin pernah diketik sebelumnya, dan terus terang Anda mungkin seharusnya tidak terlalu cepat, karena Anda dapat melakukan banyak kerusakan dengan itu. Mengapa? rm melakukan apa, tentu saja? Menghapus. * Berarti apa? Semua. Jadi apa yang disebut wild card, jadi itu berarti menghapus segala sesuatu dalam direktori saat ini. r terjadi berarti rekursif, yang berarti jika apa yang Anda menghapus adalah sebuah direktori, dan dalam sana adalah berkas dan direktori lainnya, rekursif menyelam ke sana dan menghapus semua itu. Dan f adalah yang terburuk dari mereka semua. Ada yang tahu apa-f berarti di sini? Force. Jadi memaksa berarti, bahkan jika ini adalah ide yang buruk, melakukannya tanpa disuruh me untuk konfirmasi lebih lanjut. Jadi, Anda tahu, kita menertawakan ini, tapi terus terang, saya mungkin ketik ini beberapa kali hari, karena kenyataannya itu adalah cara tercepat untuk menghapus sejumlah besar barang. Tapi bahkan aku telah melakukan beberapa kerusakan. 

Tapi jika Anda adalah untuk mengelabui komputer dalam mendefinisikan beberapa variabel bodoh atau fungsi yang disebut x, tapi kemudian menipu komputer dalam melaksanakan melampaui batas-batas yang fungsi, di luar titik koma itu, Anda memang bisa menipu komputer dalam melaksanakan sesuatu seperti rm-rf atau perintah Email atau perintah Copy. Apa pun benar-benar dapat Anda lakukan dengan komputer, apakah itu menghapus file, membuat file, spamming seseorang, menyerang beberapa server yang jauh, jika Anda bisa mengungkapkannya dengan perintah, Anda dapat trik komputer untuk melakukan itu. 

Sekarang apa contoh bagaimana Anda bisa melakukan ini? Nah, ada banyak komputer pada Bash internet berjalan. Semua pengguna kami Mac di antara mereka. Banyak server Linux adalah salah mereka juga, dan server Unix. Windows lagi mendapat relatif lolos kecuali jika Anda telah menginstal software khusus. Sekarang banyak server, untuk Misalnya, web server berjalan, dan bahkan Linux mungkin adalah kebanyakan sistem operasi populer untuk berjalan di komputer di internet yang melayani sampai halaman web. Sekarang seperti yang kita akan lihat nanti di semester, ketika Anda mengirim permintaan dari browser-- Chrome Anda, Internet Explorer, whatever-- ke server jauh, ternyata bahwa meskipun Anda hanya mengetik www.example.com, Browser Anda mengirimkan pesan itu sedikit lebih misterius, seperti ini. 

Tapi perhatikan sedikit sesuatu yang aneh. Dua baris pertama Aku belum pernah melihat sebelumnya, tapi mereka tidak terlihat terutama mengancam. Tapi perhatikan apa yang saya dicuri untuk baris ketiga di sini. Jika orang jahat yang mengirim pesan seperti ini dari komputer nya ke Mac rentan atau Linux server rentan, lucunya Bash itu, yang sedikit perintah sederhana yang cepat, mana-mana dan sering digunakan untuk mengeksekusi dasarnya isi pesan yang diterima. Dan dengan logika itu, Anda bisa trik web server, oleh karena itu, dengan mengirimkan sesuatu seperti User-Agent, yang biasanya seharusnya mengatakan nama browser Anda. User-Agent Chrome, User-Agent Internet Explorer, User-Agent Firefox, ini hanya browser Anda cara mengidentifikasi dirinya. Tetapi jika orang jahat yang sangat cerdik mengatakan, mm-mm, aku tidak akan memberitahu Anda apa browser saya, Aku bukannya akan mengirimkan ini samar-mencari hal dengan rm-rf * Di dalamnya, Anda benar-benar dapat mengelabui web server yang rentan di internet dalam melaksanakan hal itu di ada untuk menghapus semua file. Dan terus terang, itu tidak bahkan yang terburuk. Anda dapat melakukan apa-apa. Anda bisa mulai didistribusikan penolakan serangan layanan jika Anda mengirim pesan ini ke Seluruh tandan server web dan kemudian memiliki mereka semua turun, untuk Misalnya, pada server Harvard.edu, dan Anda dapat mengurutkan bang sih dari mereka oleh lalu lintas jaringan yang dinyatakan dipicu oleh orang jahat ini. 

Jadi, singkat cerita, hampir semua orang di ruangan ini yang memiliki Mac rentan terhadap ini. Lapisan perak adalah bahwa kecuali jika Anda menjalankan server web pada laptop Anda, dan kecuali Anda sudah benar-benar dikonfigurasi untuk memungkinkan sesuatu seperti SSH ke dalamnya, Anda benar-benar aman. Ini rentan, tetapi tidak ada satu mencoba masuk ke laptop Anda, sehingga Anda dapat semacam yakinlah. Namun, Apple akan segera menjadi memperbarui untuk memperbaiki ini. Dunia Linux telah dirilis sejumlah perbaikan untuk Fedora dan Ubuntu dan versi lain dari Linux, dan memang jika Anda mengalami pembaruan 50 di alat, bahkan itu juga akan diperbarui dan diperbaiki. Tapi itu terlalu belum benar-benar telah rentan, karena kecuali Anda sudah bermain-main dengan alat dan membuat laptop Anda publik diakses di internet, yang tidak secara default, Anda sudah sebenarnya baik-baik saja karena dari firewall dan teknik lainnya. 

Tapi itu contoh ekstrim bug bahwa kita sudah hidup untuk untuk benar-benar 20 tahun, dan siapa tahu jika seseorang selama ini telah tahu tentang hal itu? Dan pada kenyataannya, ini adalah salah satu tantangan mendasar bahwa kita akan lihat nanti dalam semester tentang keamanan, adalah bahwa sama seperti di dunia nyata, orang-orang yang baik di merugikan. Untuk menjaga orang-orang jahat, kita harus memastikan bahwa setiap pintu terkunci, bahwa setiap jendela aman, yang setiap titik masuk ke rumah aman untuk menjaga orang-orang jahat keluar. Tapi apa orang jahat harus lakukan untuk benar-benar kompromi rumah Anda dan mencuri dari Anda? Dia hanya harus menemukan satu dibuka pintu, satu jendela rusak, atau sesuatu sepanjang garis, dan itu adalah hal yang sama dalam keamanan komputer. Kita bisa menulis jutaan baris kode pemrograman dan menghabiskan ratusan atau ribuan jam mencoba untuk mendapatkannya benar, tetapi jika Anda membuat hanya satu kesalahan dalam kebenaran, Anda dapat menempatkan seluruh sistem dan memang dalam hal ini, seluruh internet dan dunia beresiko. 

Jadi jika Anda ingin mempelajari lebih lanjut tentang hal ini, pergi ke URL ini di sini. Tidak perlu tindakan malam ini kecuali jika Anda di antara mereka lebih nyaman yang telah menjalankan web Anda sendiri Server, dalam hal ini Anda harus, pada kenyataannya, memperbarui perangkat lunak Anda. 

Dan ini juga adalah judul pidato, dan sekarang kertas, bahwa kita telah terhubung pada situs mata kuliah untuk hari ini. Itu sesama bernama Ken Thompson, yang sedang menerima sangat terkenal penghargaan dalam ilmu komputer, dan ia memberikan pidato ini beberapa tahun lalu, pada dasarnya tentang topik ini sama. Mengajukan orang pertanyaan, Anda benar-benar harus kepercayaan, akhirnya, perangkat lunak yang Anda telah diberikan? Misalnya, kita semua memiliki telah menulis program, dan kami sudah menyusun mereka dengan dentang. Dan untuk pengetahuan Anda, yang telah ditulis program untuk CS50 mana ada pintu belakang macam, di situ ada jalan bahwa orang jahat, jika menjalankan program Anda, bisa mengambil alih komputer Anda? Mungkin tidak, kan? Mario, dan Greedy, dan Kredit. Ini semua adalah program cukup kecil. Anda akan harus cukup buruk jika Anda benar-benar membuat seluruh komputer Anda rentan setelah menulis 10 atau 20 baris kode, atau setidaknya menyadari beberapa implikasi keamanan. Sekarang saya mengatakan bahwa berkelakar, tapi kita akan lihat hari ini dan minggu ini itu sebenarnya benar-benar, benar-benar mudah menjadi buruk dan membuat bahkan program pendek yang rentan. 

Tapi untuk saat ini, setidaknya, menyadari bahwa pertanyaan yang diajukan di sini adalah tentang dentang dalam kompilator. Mengapa kami telah percaya dentang selama dua atau tiga minggu terakhir? Siapa bilang bahwa siapa pun yang menulis dentang tidak memiliki "jika" kondisi ada yang pada dasarnya disuntikkan beberapa nol dan orang-orang ke dalam setiap program yang mengkompilasi yang akan membiarkan dia atau akses nya komputer Anda saat Anda sedang tidur dan tutup laptop Anda terbuka dan komputer Anda berjalan? Benar? Kami memiliki semacam ini sistem kehormatan hak sekarang di mana kita percaya bahwa dentang legit. Anda percaya bahwa alat legit. Anda percaya bahwa benar setiap program pada Mac atau PC dapat dipercaya. Dan sebagai bug yang sederhana ini menunjukkan, bahkan jika itu tidak berbahaya, itu sama sekali tidak mungkin terjadi. 

Jadi, Anda harus takut sekali. Terus terang, tidak ada sederhana solusi untuk ini lain dari semacam kesadaran masyarakat dari meningkatnya kompleksitas bahwa kita sedang membangun di atas sistem komputer kita, dan bagaimana semakin rentan kita mungkin sangat baik menjadi. 

Sekarang dengan mengatakan bahwa, Breakout. Jadi Breakout adalah masalah menetapkan tiga, dan Breakout adalah permainan dari masa lampau bahwa Anda mungkin ingat, tapi bagi kita di masalah menetapkan tiga, memungkinkan kita untuk mengambil hal back up takik sehingga ketika kita menulis program, bahkan dalam jendela Terminal seperti ini, kita benar-benar dapat berjalan, akhirnya, program grafis tidak tidak seperti kami memiliki Akses ke dalam Scratch. Jadi ini adalah staf pelaksanaan Breakout, yang hanya ini bata-melanggar permainan, Anda memindah pemukul Anda kembali dan sebagainya, dan Anda memukul bola terhadap orang-orang batu bata berwarna di bagian atas. Jadi ini membawa kita semacam kembali ke tempat kami mampu menjadi sangat cepat dengan Scratch, dan sekarang dengan C, menerapkan kita sendiri antarmuka pengguna grafis. 

Tapi lebih dari itu, ini Masalah set merupakan yang pertama di mana kami memberikan Anda sekelompok kode. Dan pada kenyataannya, saya membawa eksplisit memperhatikan hal ini, karena terutama bagi mereka yang kurang nyaman, ini permasalahan yang, setidaknya pada pandangan pertama, akan merasa seperti kami sudah itu membuat takik. Karena kami telah memberikan, untuk beberapa pencarian dan memilah masalah dalam PSET tersebut, sekelompok kode yang kita tulis, dan beberapa komentar yang mengatakan "untuk melakukan," di mana Anda harus mengisi kekosongan. Jadi tidak terlalu menakutkan, tapi itu adalah pertama kalinya kami menyerahkan Anda kode yang Anda butuhkan untuk pertama kali membaca, memahami, dan kemudian menambah dan menyelesaikannya. 

Dan kemudian dengan Breakout, kita akan melakukan hal yang sama, memberikan Anda beberapa lusin lebih baris kode yang, terus terang, memberikan banyak kerangka kerja untuk permainan tapi berhenti singkat penerapan batu bata dan bola dan pemukul, tetapi kita mengimplementasikan beberapa fitur lainnya. Dan bahkan yang pada pandangan pertama, sekali lagi, terutama jika kurang nyaman, mungkin tampak sangat menakutkan dan Anda berpikir ada begitu banyak fungsi baru Anda perlu untuk membungkus pikiran Anda sekitar, dan itu benar. Namun perlu diingat, itu cukup seperti Scratch. Kemungkinan besar Anda tidak menggunakan semua potongan puzzle dalam Scratch. Kemungkinan besar Anda tidak peduli untuk membungkus pikiran Anda sekitar semua dari mereka karena semua butuh adalah sekilas untuk memahami, oh, itulah yang bisa saya lakukan dengan potongan puzzle. Dan memang, dalam permasalahan yang 3 spec, kami akan mengarahkan Anda dokumentasi yang akan memperkenalkan Anda kepada beberapa fungsi baru, dan akhirnya pemrograman konstruksi Anda gunakan. Kondisi, loop, variabel, dan fungsi akan sama dengan apa yang telah kita lihat sejauh ini. 

Jadi memang, apa yang kita akan memberikan Anda adalah beberapa contoh kode yang memungkinkan Anda membuat jendela yang terlihat tidak seperti ini, dan akhirnya mengubahnya menjadi sesuatu yang seperti ini. Jadi memanfaatkan CS50, membahas jam kantor dan lebih, dan mengambil kenyamanan di fakta bahwa jumlah kode Anda harus menulis sebenarnya tidak semua yang jauh. Tantangan pertama adalah hanya untuk menyesuaikan diri diri Anda untuk beberapa kode yang kami telah menulis. 

Pertanyaan pset3, SHELLSHOCK, atau sebaliknya? 

AUDIENCE: Sepertinya melalui dengan Breakout bahwa kode ini hampir gaya berorientasi objek, tapi saya pikir C adalah program berorientasi objek. SPEAKER 1: Sebuah pertanyaan yang sangat bagus. Jadi dalam melihat melalui kode distribusi, kode kami menulis untuk pset3, untuk mereka yang akrab, itu Sepertinya itu adalah sedikit berorientasi objek. Jawaban singkatnya adalah, itu. Ini perkiraan bagaimana Anda mungkin melakukan kode berorientasi obyek menggunakan bahasa seperti C, tetapi masih akhirnya prosedural. Tidak ada metode dalam variabel, seperti yang akan Anda lihat. Tapi itu mengingatkan itu. Dan kita akan melihat fitur yang lagi ketika kita sampai ke PHP dan JavaScript menjelang akhir semester. Tapi untuk saat ini, menganggapnya sebagai sedikit apa yang akan datang. Pertanyaan yang bagus. Baiklah. Jadi melebur semacam itu bagaimana kita hal kiri terakhir kali. Dan melebur semacam dingin di arti bahwa itu begitu jauh lebih cepat, setidaknya berdasarkan tes sepintas kami lakukan minggu lalu, dari, katakanlah, gelembung sort, selection sort, insertion sort. Dan apa yang rapi juga hanya bagaimana ringkas dan bersih Anda bisa mengungkapkannya. Dan apa yang kita katakan itu adalah atas terikat pada waktu berjalan dari merge mengurutkan? Ya? 

AUDIENCE: n log n? 

SPEAKER 1: n log n, benar. n log n. Dan kami akan kembali ke apa itu benar-benar berarti atau mana yang berasal dari, tapi ini lebih baik dari apa waktu berjalan yang kami lihat untuk gelembung seleksi dan insertion sort? Jadi n kuadrat. n kuadrat lebih besar dari ini, dan bahkan jika itu tidak cukup jelas, tahu bahwa log n lebih kecil dari n, jadi jika Anda melakukan n kali sesuatu yang lebih kecil dari n, itu akan menjadi kurang dari n kuadrat. Itu adalah sedikit dari intuisi sana. Tapi kita membayar harga untuk ini. Itu lebih cepat, tapi tema yang dimulai muncul minggu lalu adalah tradeoff ini. Aku punya kinerja yang lebih baik waktu bijaksana, tapi apa aku harus menghabiskan di sisi lain tangan, dalam rangka untuk mencapai itu? 

AUDIENCE: Memory. SPEAKER 1: Katakanlah lagi? AUDIENCE: Memory. SPEAKER 1: Memory, atau ruang yang lebih umum. Dan itu bukan super jelas dengan manusia kami, tapi ingat bahwa relawan kami melangkah maju dan melangkah kembali seolah-olah ada sebuah array di sini, dan seolah-olah ada array kedua di sini bahwa mereka bisa menggunakan, karena kita dibutuhkan tempat untuk menggabungkan orang-orang itu. Kita tidak bisa hanya swap mereka di tempat. Jadi menggabungkan pengaruh semacam lebih banyak ruang, yang kita tidak perlu dengan algoritma lain, tapi terbalik adalah bahwa hal itu jauh lebih cepat. Dan terus terang, di ruang dunia nyata ini RAM days--, hard disk space-- relatif murah, dan jadi itu tidak selalu berarti buruk. 

Jadi mari kita lihat, sedikit lebih metodis, pada apa yang kita lakukan dan mengapa kita mengatakan itu n log n. Jadi di sini adalah delapan angka dan delapan relawan kami memiliki waktu terakhir. Dan hal pertama yang Merge Urut mengatakan kepada kita lakukan adalah apa? AUDIENCE: Divide dua. SPEAKER 1: Katakanlah lagi? AUDIENCE: Divide dua. SPEAKER 1: Divide dua, benar. Hal ini sangat mengingatkan buku telepon, membagi dan menaklukkan lebih umum. Jadi kita melihat kiri setengah. Dan kemudian setelah kita berkata, semacam kiri setengah dari unsur-unsur, apa yang kita selanjutnya katakan? Urutkan kiri setengah dari kiri setengah, yang memungkinkan kita untuk, setelah membagi dua, fokus pada empat dan dua. 

Bagaimana Anda mengurutkan daftar sekarang, di kuning, ukuran dua, menggunakan Merge Sort? Nah membagi menjadi dua, dan mengurutkan setengah kiri. Dan ini adalah di mana hal-hal mendapat sebentar bodoh sedikit. Bagaimana Anda menyortir daftar itu dari ukuran satu, seperti nomor ini empat sini? Ini diurutkan. Anda sudah selesai. 

Tapi kemudian bagaimana Anda menyortir daftar satu ukuran ketika itu nomor dua? Nah, hal yang sama, tapi sekarang apa yang ketiga dan langkah kunci dalam Merge Sort? Anda harus menggabungkan kiri setengah dan setengah benar. Dan setelah kami melakukan itu, kami melihat pukul empat, kami melihat dua. Kami memutuskan apa-apa, jelas dua datang pertama, sehingga kami menempatkan dua di nya Tempat, diikuti oleh empat. Dan sekarang Anda harus jenis mundur, dan ini adalah semacam karakteristik dari algoritma seperti Merge Urut, mundur dalam memori. Apa baris berikutnya dari cerita ini? Apa yang harus saya berfokus pada berikutnya? Bagian kanan kiri setengah, yang merupakan enam dan delapan. 

Jadi biarkan aku hanya langkah melalui ini Tanpa penekanan titik terlalu banyak. Enam dan delapan, kemudian enam adalah diurutkan, delapan diurutkan. Menggabungkan mereka bersama-sama seperti itu, dan sekarang langkah besar berikutnya , tentu saja, mengurutkan kanan setengah dari langkah pertama dari algoritma ini. Jadi kita fokus pada satu, tiga, tujuh, lima. Kami kemudian fokus pada kiri setengah. Kiri setengah dari itu, bagian kanan itu, dan kemudian bergabung dalam satu dan tiga. Kemudian bagian kanan, kemudian meninggalkan setengah itu, maka bagian kanan itu. Merge dalam, dan sekarang apa langkah yang tersisa? Menggabungkan setengah kiri yang besar dan besar setengah benar, sehingga orang pergi ke sana, kemudian dua, kemudian tiga, lalu empat, lalu lima, lalu enam, kemudian tujuh, lalu delapan. 

Jadi sekarang mengapa ini akhirnya mengungkapkan, terutama jika n dan logaritma lainnya umumnya agak melarikan diri Anda, setidaknya dalam memori baru-baru ini? Nah, perhatikan ketinggian hal ini. Kami memiliki delapan elemen, dan kami dibagi dengan dua, dua, dua. Jadi dasar log dua dari delapan memberi kita tiga. Dan percayalah bahwa jika sedikit kabur itu. Tapi dasar log dua dari delapan tiga, jadi kami sudah melakukan tiga lapis penggabungan. Dan ketika kita bergabung elemen, berapa banyak elemen Apakah kita melihat pada masing-masing baris? Sebanyak n, kan? Karena untuk menggabungkan baris atas, meskipun kami melakukannya sedikit demi sedikit, kita akhirnya menyentuh setiap nomor sekali. Dan di baris kedua, untuk menggabungkan daftar tersebut ukuran dua, kita harus menyentuh setiap elemen sekali. Dan maka di sini benar-benar jelas di baris terakhir, kita harus menyentuh masing-masing elemen sekali, tapi hanya sekali, jadi di sinilah letak, maka, n log n kami. 

Dan sekarang hanya untuk membuat sesuatu yang sedikit lebih formal untuk sesaat, jika Anda yang sekarang menganalisis ini pada semacam tingkat yang lebih tinggi dan mencoba untuk memutuskan, baik bagaimana mungkin Anda pergi tentang mengekspresikan waktu berjalan dari algoritma ini hanya dengan melihat itu, bukan dengan menggunakan contoh-buat? Nah, berapa banyak waktu Anda akan mengatakan langkah seperti ini warna kuning akan mengambil, jika n <2 kembali? Itu O besar dari apa? Jadi aku melihat satu, jadi satu langkah, mungkin dua langkah karena jika dan kemudian kembali, tapi itu waktu yang konstan, kan? Kami katakan O (1), dan itu bagaimana saya akan mengungkapkan hal ini. T, hanya akan berjalan waktu. n adalah ukuran input, sehingga T (n), hanya cara mewah mengatakan yang sedang berjalan waktu tertentu masukan ukuran n akan berada di urutan dari waktu yang konstan, di O (1). 

Tapi sebaliknya, bagaimana ini? Bagaimana Anda akan mengungkapkan waktu berjalan dari garis kuning ini? T apa? Anda dapat jenis menipu di sini dan menjawab pertanyaan saya siklis. Jadi jika waktu berjalan di umum kita hanya mengatakan adalah T (n). Dan sekarang kau jenis punting sini dan mengatakan, baik, hanya mengurutkan kiri setengah, dan kemudian mengurutkan bagian kanan. Bagaimana mungkin kita secara simbolis mewakili waktu berjalan dari garis kuning ini? T apa? Apa ukuran input? n lebih dari dua. Mengapa saya tidak hanya mengatakan bahwa? Dan maka ini adalah T lain (n / 2) dan kemudian lagi, jika saya menggabungkan dua bagian diurutkan, berapa banyak elemen yang akan saya harus menyentuh keseluruhan? n. Jadi saya bisa mengungkapkan ini, hanya menjadi semacam mewah, sebagai waktu berjalan secara umum. T (n) hanya waktu berjalan dari T (n / 2), ditambah T (n / 2), meninggalkan setengah dan setengah benar, ditambah O (n), yang mungkin n langkah, tapi mungkin, jika saya menggunakan dua jari, itu dua kali lebih banyak langkah, tapi itu linear. Ini beberapa jumlah langkah itu faktor n, sehingga kita bisa mengungkapkan ini karena ini. Dan ini adalah di mana sekarang kita akan menyepak bola ke belakang buku matematika SMA kami kami bahwa kekambuhan pada akhirnya berakhir setara ini, n kali log n, jika Anda benar-benar melakukan out matematika lebih formal. 

Jadi itu hanya dua perspektif. Satu numerik dengan keras-kode contoh yang representatif menggunakan delapan angka, dan lebih pandangan umum bagaimana kita sampai di sana. Tapi apa benar-benar menarik di sini adalah, sekali lagi, gagasan ini bersepeda. Saya tidak menggunakan untuk loop. Aku agak mendefinisikan sesuatu dalam hal itu sendiri, tidak hanya dengan ini fungsi matematika, tetapi juga dalam hal kode semu ini. Pseudo code ini adalah rekursif dalam dua lini pada dasarnya mengatakan untuk pergi gunakan sendiri untuk memecahkan lebih kecil masalah ukuran yang lebih kecil, dan kemudian lagi dan lagi dan lagi sampai kita kurangi itu ke kasus dasar ini disebut. 

Jadi mari kita benar-benar menarik lebih menarik dibawa pulang dari ini sebagai berikut. Biarkan aku pergi ke gedit dan mengambil melihat beberapa kode sumber saat ini, khususnya contoh ini di sini. Sigma 0, yang tampaknya menambahkan angka satu sampai n. Jadi mari kita lihat apa yang akrab dan asing di sini. Pertama kita memiliki beberapa termasuk, jadi tidak ada yang baru di sana. Prototype. Aku sedikit kabur pada ini setelah beberapa hari, tapi apa yang kita katakan prototipe fungsi adalah? AUDIENCE: [Tak terdengar]. SPEAKER 1: Apa itu? AUDIENCE: Kami mengumumkannya. SPEAKER 1: Kami mengumumkannya. Jadi Anda mengajar dentang, hey, tidak benar-benar menerapkan ini belum, tetapi di suatu tempat dalam file ini, mungkin, akan menjadi fungsi yang disebut apa? Sigma. Dan ini hanya janji yang itu akan terlihat seperti ini. Ini akan mengambil integer sebagai input-- dan aku bisa lebih eksplisit dan mengatakan int n --dan itu akan mengembalikan int, tapi berarti titik koma, mm, aku akan mendapatkan sekitar untuk menerapkan ini sedikit kemudian. Sekali lagi, dentang bodoh. Ini hanya akan tahu apa Anda mengatakan itu atas ke bawah, jadi kita perlu setidaknya memberikan itu sedikit dari apa yang akan datang. 

Sekarang mari kita lihat utama di sini. Mari kita gulir ke bawah sini dan melihat apa utama lakukan. Ini bukan berarti bahwa panjang dari suatu fungsi, dan sebenarnya membangun di sini akrab. Saya mendeklarasikan variabel n, dan kemudian Saya mengganggu pengguna lagi dan lagi untuk bilangan bulat positif menggunakan getInt, dan hanya keluar dari lingkaran ini sekali pengguna telah memenuhi. Do While, kami telah digunakan untuk mengganggu pengguna dengan cara itu. Sekarang ini adalah menarik. Saya mendeklarasikan int disebut "jawaban." Saya menetapkan nilai kembali dari fungsi yang disebut "sigma." Aku tidak tahu apa yang tidak, tapi Aku ingat menyatakannya beberapa saat yang lalu. Dan kemudian aku lewat di nilai bahwa pengguna mengetik, n, dan kemudian saya melaporkan jawabannya. Nah mari kita gulir kembali untuk sesaat. Mari kita pergi ke depan dalam direktori ini, membuat sigma 0, dan benar-benar menjalankan program ini dan melihat apa yang terjadi. Jadi jika saya pergi ke depan dan menjalankan Program ini, ./sigma-0, dan saya ketik secara positif bilangan bulat seperti dua, Sigma, sebagai simbol Yunani menyiratkan, hanya akan menambahkan semua nomor dari nol pada hingga dua. Jadi 0 ditambah 1 ditambah 2. Jadi ini harus mudah-mudahan memberi saya 3. Itu semua yang dilakukannya. Dan sama, jika saya menjalankan ini lagi dan saya memberikan nomor tiga, itu 3 ditambah 2, jadi itu 5, ditambah 1 harus memberikan 6. Dan kemudian jika saya benar-benar gila dan mulai mengetik dalam jumlah yang lebih besar, harus memberi saya besar dan lebih besar jumlah. Jadi itu saja. 

Jadi apa sigma terlihat seperti? Yah, itu cukup sederhana. Ini bagaimana kita mungkin telah menerapkan ini selama beberapa minggu. "Int" akan menjadi jenis kembali. Sigma adalah nama, dan dibutuhkan m variabel bukan n. Aku akan mengubah itu di bagian atas. Maka ini adalah hanya cek kewarasan. Kita akan melihat mengapa dalam sekejap. Sekarang saya mendeklarasikan variabel lain, Singkatnya, menginisialisasi ke nol. Lalu aku punya ini untuk lingkaran iterasi, tampaknya untuk kejelasan, dari i = 1 pada hingga = m, yang apapun pengguna mengetik di, dan kemudian aku kenaikan jumlah seperti ini. Dan kemudian kembali jumlah tersebut. 

Jadi beberapa pertanyaan. Satu, saya menyatakan dalam komentar saya bahwa ini menghindari risiko loop tak terbatas. Mengapa lewat di angka negatif menginduksi, potensial, infinite loop? 

AUDIENCE: Anda tidak akan pernah mencapai m. 

SPEAKER 1: Jangan pernah mencapai m. Tapi m dilewatkan dalam, jadi mari kita pertimbangkan contoh sederhana. Jika m dilewatkan oleh pengguna sebagai salah satu negatif. Terlepas dari utama. Main melindungi kita dari ini juga, jadi aku hanya menjadi benar-benar anal dengan sigma juga untuk memastikan bahwa input tidak boleh negatif. Jadi jika m negatif, sesuatu seperti satu negatif. Apa yang akan terjadi? Nah, saya akan mendapatkan diinisialisasi ke satu, dan kemudian saya akan menjadi kurang dari atau sama dengan m? 

Stand by. Itu was-- jangan, mari kita nix cerita ini. Aku tidak menanyakan hal itu, karena risiko bahwa saya menyinggung tidak akan terjadi karena saya adalah selalu akan lebih besar OK than--, Saya menarik kembali pertanyaan itu. OK. Mari kita fokus hanya pada bagian ini di sini. Mengapa saya menyatakan beberapa luar loop? Pemberitahuan on line 49 saya sudah menyatakan i dalam loop, tapi secara online 48 Aku sudah menyatakan beberapa luar. Ya. AUDIENCE: [Tak terdengar]. SPEAKER 1: Tentu. Jadi pertama dan terutama saya pasti tidak ingin menyatakan dan menginisialisasi sum dengan nol bagian dalam loop pada setiap iterasi, karena ini jelas akan mengalahkan tujuan menjumlahkan angka-angka. Saya akan terus berubah nilai kembali ke nol. Dan juga, apa lagi yang lebih misterius alasan untuk itu keputusan desain yang sama? Ya. 

AUDIENCE: [Tak terdengar]. SPEAKER 1: Tepat. Saya ingin mengaksesnya di luar loop juga pada apa baris? Pada 53. Dan berdasarkan aturan kami praktis dari beberapa kuliah yang lalu, variabel scoped, benar-benar, dengan kurung kurawal yang mencakup mereka. Jadi jika saya tidak menyatakan jumlah dalam ini kurung kurawal luar, Saya tidak dapat menggunakannya sesuai 53. Dengan kata lain, jika saya menyatakan sum di sini, atau bahkan di dalam Untuk lingkaran, saya tidak bisa mengaksesnya di 53. Variabel efektif akan hilang. Jadi beberapa alasan di sana. Tapi sekarang mari kita kembali dan melihat apa yang terjadi. Jadi sigma dipanggil. Ini menambahkan sampai 1 ditambah 2, atau 1 ditambah 2 ditambah 3, dan kemudian mengembalikan nilai, menyimpannya dalam jawaban, dan printf sini mengapa saya melihat di layar. Jadi ini adalah apa yang akan kita sebut berulang pendekatan, di mana iterasi hanya berarti menggunakan loop. A Untuk lingkaran, loop Sementara, Do Sementara lingkaran, hanya melakukan sesuatu lagi dan lagi dan lagi. 

Tapi sigma adalah jenis fungsi rapi di bahwa saya bisa menerapkannya berbeda. Bagaimana dengan ini, yang hanya untuk jenis dingin, biarkan aku benar-benar menyingkirkan dari banyak gangguan karena fungsi ini benar-benar sangat sederhana. Meraut itu mari kita turun hanya dengan jalur inti empat dan menyingkirkan semua komentar dan kurung kurawal. Ini adalah jenis pikiran-bertiup implementasi alternatif. Baiklah, mungkin tidak pikiran-bertiup, tapi agak seksi, baik-baik saja, untuk melihat ini jauh lebih ringkas. Dengan hanya empat baris kode, Saya pertama kali memiliki kewarasan cek ini. Jika m kurang dari atau sama dengan nol, sigma tidak masuk akal. Ini hanya seharusnya berada di hal ini untuk bilangan positif, jadi aku hanya akan kembali nol sewenang-wenang sehingga kita setidaknya memiliki beberapa disebut kasus dasar. 

Tapi di sini keindahan. Keseluruhan ide ini, menambahkan angka dari 1 sampai n, atau m dalam kasus ini, dapat dilakukan dengan jenis lewat uang. Nah, apa adalah jumlah dari 1 sampai m? Nah, Anda tahu apa? Ini sama dengan jumlah m ditambah jumlah 1 sampai m dikurangi 1. Yah kau tahu apa? Apa sigma dari m dikurangi 1? Nah, jika Anda jenis ini mengikuti logis, itu sama dengan m dikurangi 1 ditambah sigma dari m minus 2. Jadi Anda dapat jenis hanya-- ini seperti, jika Anda hanya mencoba untuk mengganggu teman dan mereka mengajukan pertanyaan, Anda jenis merespon dengan pertanyaan, Anda dapat jenis terus lewat uang. Tapi apa kuncinya adalah bahwa jika Anda tetap membuat pertanyaan yang lebih kecil dan lebih kecil dan lebih kecil, Anda tidak meminta apa sigma n, apa sigma dari n, apa sigma n? Anda meminta apa sigma dari n, apa sigma n dikurangi 1, apa sigma n minus 2? Akhirnya pertanyaan Anda akan menjadi apa? Apa sigma dari satu atau nol, beberapa nilai yang sangat kecil, dan segera setelah Anda mendapatkan itu, teman Anda, Anda tidak akan bertanya pertanyaan yang sama lagi, Anda hanya akan mengatakan, oh itu nol. Kami selesai bermain semacam ini permainan siklus bodoh. 

Jadi rekursi adalah tindakan dalam pemrograman fungsi yang menyebut dirinya. Program ini, ketika dikompilasi dan dijalankan, adalah akan berperilaku dengan cara yang sama, tapi apa kuncinya adalah bahwa di dalam dari fungsi yang disebut sigma, ada baris kode dimana kita memanggil diri kita sendiri, yang biasanya akan menjadi buruk. Misalnya, bagaimana jika saya pertama kali dikompilasi ini, sehingga membuat sigma-- membuat sigma 1 ./sigma-1. Bilangan bulat positif, silahkan, 50 1275. Jadi apa fungsi tampaknya jadi, berdasarkan satu tes, benar. Tapi bagaimana jika saya mendapatkan sedikit berbahaya dan menghapus apa yang disebut kasus dasar, dan hanya mengatakan, baik aku hanya membuat ini lebih rumit dari itu. Mari kita menghitung sigma yang dengan mengambil m dan kemudian menambahkan di sigma dari m minus satu? Nah, apa yang akan terjadi di sini? Mari kita zoom out. Mari kita ulang program, menyimpannya, ulang program, dan kemudian siap ./sigma-1 zoom, masukkan bilangan bulat positif silahkan, 50. Berapa banyak dari Anda bersedia untuk mengaku hingga melihat itu? 

OK. Jadi ini dapat terjadi karena sejumlah alasan, dan terus terang minggu ini kami akan memberi Anda lebih banyak dari mereka. Tapi dalam kasus ini, coba untuk alasan mundur apa yang mungkin terjadi di sini? Segmentation fault, kami katakan terakhir waktu, mengacu pada segmen memori. Sesuatu yang buruk terjadi. Tapi apa itu mekanis yang pergi kacau di sini karena penghapusan saya itu kasus dasar yang disebut, di mana aku kembali nilai keras-kode? Bagaimana menurut Anda salah? Ya. 

AUDIENCE: [Tak terdengar]. SPEAKER 1: Ah. Pertanyaan yang bagus. Jadi ukuran nomor bahwa saya menyimpulkan mendapat begitu besar bahwa itu melebihi ukuran ruang memori. Ide bagus, tapi tidak mendasar akan menyebabkan kecelakaan. Yang mungkin menyebabkan integer overflow, dimana bit hanya terbalik dan kemudian kita benar-benar kesalahan besar nomor seperti nomor negatif, tapi itu sendiri tidak akan menyebabkan kecelakaan. Karena pada akhir hari int masih 32 bit. Anda tidak akan sengaja mencuri sedikit 33. Tapi pikiran yang baik. Ya. 

AUDIENCE: [Tak terdengar]. SPEAKER 1: Metode tidak pernah berhenti berjalan, dan memang itu menyebut dirinya lagi dan lagi dan lagi dan lagi dan lagi, dan tidak ada fungsi-fungsi yang pernah selesai karena jalur satu-satunya mereka kode panggilan themself lagi dan lagi dan lagi. Dan apa yang benar-benar terjadi di sini, dan sekarang kita dapat jenis menggambar ini pictorially. Biarkan aku pergi ke sebuah gambar untuk sesaat. Ini adalah gambar, yang akhirnya akan menyempurnakan secara lebih rinci, apa yang terjadi pada dalam memori komputer Anda. Dan ternyata bahwa pada bagian bawah gambar ini sesuatu yang disebut stack. Ini adalah sepotong memori, sepotong RAM, itu hanya digunakan setiap saat fungsi ini disebut. Setiap kali Anda, programmer, memanggil fungsi, sistem operasi, seperti Mac OS, Windows, atau Linux, meraih sekelompok byte, mungkin beberapa kilobyte, mungkin beberapa megabyte memori, tangan mereka kepada Anda, dan kemudian memungkinkan Anda menjalankan fungsi Anda menggunakan variabel apa pun yang Anda butuhkan. Dan jika Anda kemudian memanggil yang lain fungsi dan fungsi lain, Anda mendapatkan sepotong memori yang lain dan lain sepotong memori. 

Dan memang, jika ini nampan hijau dari Annenberg merupakan memori yang, inilah yang terjadi pertama kali Anda memanggil fungsi sigma. Ini seperti menempatkan nampan seperti ini pada apa yang awalnya stack kosong. Tapi kemudian jika baki yang menyebut dirinya, sehingga untuk berbicara, memanggil contoh lain sigma, itu seperti meminta sistem operasi, ooh, membutuhkan memori sedikit lebih, memberi saya itu. Dan kemudian itu akan ditumpuk di atas. Tapi apa kunci di sini adalah bahwa baki pertama masih ada, karena ia dipanggil tray kedua ini. Sekarang sementara itu, sigma panggilan sigma, itu seperti meminta lebih banyak memori. Mendapat menumpuk di sini. sigma panggilan sigma, itu lain tray yang akan menumpuk di sini. Dan jika Anda terus melakukan hal ini, akhirnya, jenis peta visual ini bagan itu, apa yang akan terjadi dengan tumpukan nampan? Hal ini akan melebihi jumlah memori komputer Anda. Dan segera setelah tray hijau melebihi garis horizontal di atas tumpukan dan di atas itu tumpukan kata, yang kita akan kembali di masa depan, itu adalah hal yang buruk. Heap adalah berbeda segmen memori, dan jika Anda membiarkan ini nampan tumpukan dan tumpukan pada, Anda akan melebihi segmen Anda sendiri dari memori, dan program ini memang akan crash. 

Sekarang sebagai samping, ide ini rekursi, oleh karena itu, jelas dapat menyebabkan masalah, tetapi itu tidak selalu hal yang buruk. Karena pertimbangkan, setelah semua, how-- dan mungkin ini mengambil beberapa membiasakan untuk --how elegan atau cara sederhana bahwa pelaksanaan sigma adalah. Dan kita tidak akan menggunakan rekursi semua yang banyak di CS50, tetapi dalam CS51, dan benar-benar setiap kelas di mana Anda memanipulasi struktur data seperti pohon, atau pohon keluarga, yang memiliki beberapa hirarki, itu super, super berguna. Sekarang, sebagai samping, sehingga Anda sebagai calon ilmuwan komputer akrab dengan beberapa Google lelucon, jika Anda pergi ke Google dan anda melihat apa yang definisi, katakanlah, rekursi, masukkan. Uh-huh. Sebagai samping, aku menarik beberapa. Ini seperti 10 menit prokrastinasi pagi ini. Jika anda juga Google "miring," pemberitahuan dengan memiringkan kepala Anda slightly-- dan kemudian yang satu ini mungkin paling mengerikan dari semua karena seseorang menghabiskan seperti hari mereka menerapkan ini beberapa tahun ago-- datang. Oh, wait-- itu bug. 

Jadi berjalan pada salah satu website terbesar di dunia bodoh telur Paskah kecil ini. Mereka mungkin mengkonsumsi jumlah trivial baris kode hanya agar kita dapat memiliki sedikit menyenangkan hal-hal seperti itu. Tapi setidaknya sekarang Anda bisa beberapa dari mereka lelucon. 

Sekarang mari kita lihat beberapa dari putih terletak kami telah memberitahu akhir-akhir ini, dan mulai mengupas beberapa lapisan teknis sehingga Anda benar-benar memahami apa yang telah terjadi dan Anda dapat memahami beberapa ancaman, seperti SHELLSHOCK, bahwa sekarang sudah mulai menjadi di garis depan semua orang perhatian, setidaknya di media. Jadi di sini adalah fungsi yang sangat sederhana yang mengembalikan apa-apa, tidak berlaku. Namanya adalah swap. Dibutuhkan dua variabel dan mengembalikan apa-apa. Membawa dalam a dan b. Jadi demonstrasi cepat. Kami membawa ini ke atas. Kami mungkin juga mengambil sedikit istirahat di sini untuk sesaat dan memiliki sedikit sesuatu untuk minum. Jika seseorang tidak keberatan bergabung saya di sini untuk sesaat. Bagaimana Anda di kemeja merah marun? Ayo up. Hanya satu hari ini. Terima kasih, meskipun. Baiklah, dan kami memiliki datang yang di sini? Siapa nama Anda? 

SPEAKER 4: Laura. 

SPEAKER 1: Laura. Ayo up. Jadi Laura, tantangan yang sangat sederhana hari ini. Senang bertemu yo. Baiklah. Jadi kita memiliki beberapa susu di sini dan kami memiliki beberapa jus jeruk di sini dan beberapa cangkir yang kita dipinjam dari Annenberg hari ini. 

SPEAKER 4: Borrowed. SPEAKER 1: Dan akan pergi ke depan dan memberikan setengah gelas ini. Baiklah. Dan kami akan memberikan setengah segelas susu. Oh, dan hanya sehingga Anda dapat ingat apa ini seperti, Saya ingat untuk membawa ini dan pada hari ini. Oke. Jika Anda tidak keberatan, mari kita lihat, kita dapat menempatkan mereka di atas gelas Anda sendiri jika Anda ingin. Ini akan menjadi dunia dari mata Laura. Baiklah. Jadi tujuan Anda, mengingat dua cangkir cair di sini, susu dan jus jeruk, adalah menukar dua isi sehingga jus jeruk masuk ke cangkir susu dan susu masuk ke cangkir jus jeruk. 

SPEAKER 4: Apakah saya mendapatkan secangkir lagi? SPEAKER 1: Aku sangat senang kau bertanya, meskipun itu akan menjadi rekaman yang jauh lebih baik jika Anda tidak bertanya. Tapi ya, kami bisa memberikan sepertiga cangkir yang kosong, tentu saja. Baiklah. Jadi menukar isi sana. Sangat bagus. Sangat bagus. Anda melakukan ini sangat hati-hati. Dan langkah ketiga. Baiklah. Sangat baik. Sebuah tepuk tangan meriah akan baik bagi Laura. Baiklah. Kami memiliki hadiah perpisahan kecil untuk Anda, tapi biarkan aku ambil ini. Terima kasih banyak. Jadi contoh sederhana, meskipun, untuk menunjukkan bahwa jika Anda ingin menukar isi dari dua kontainer, atau mari kita sebut mereka variabel, Anda membutuhkan penyimpanan sementara untuk tahap salah satu isi dalam begitu bahwa Anda benar-benar dapat melakukan swap. Jadi memang, sumber kode di sini di C adalah wakil dari hal itu. Jika jus jeruk dan susu adalah b, dan kami ingin menukar dua, Anda bisa mencoba sesuatu yang kreatif dengan menuangkan satu ke yang lain, tapi itu mungkin tidak akan berakhir dengan baik. Dan jadi kita menggunakan cangkir ketiga, panggilan itu tmp, T-M-P oleh konvensi, dan menempatkan isi OJ dalam hal itu, kemudian menukar satu cangkir, kemudian menempatkan OJ ke dalam cangkir asli, sehingga mencapai, persis seperti Laura melakukan, swap. 

Jadi mari kita melakukan hal itu. Biarkan aku pergi ke depan dan membuka sebuah contoh yang benar-benar disebut "tidak menukar, "karena ini bukan sebagai hanya dilakukan seperti yang Anda bayangkan. Jadi dalam program ini, perhatikan bahwa Saya menggunakan stdio.h, teman lama kami. Saya memiliki prototipe untuk tukar di sana, yang berarti pelaksanaannya dunia mungkin di bawah, dan mari kita lihat apa ini main Program akan lakukan untuk saya. Saya pertama kali menyatakan int x mendapat satu, dan int y mendapat dua. Jadi memikirkan mereka sebagai OJ dan susu, masing-masing. Dan kemudian aku hanya memiliki printf mengatakan x adalah ini dan y adalah ini, agar aku bisa visual melihat apa yang terjadi. Lalu aku telah printf mengklaim bahwa aku menukar dua, dan kemudian saya mencetak mengklaim bahwa mereka bertukar, dan saya mencetak x dan y lagi. Jadi di sini di swap apa Laura lakukan, dan apa yang kami lihat di layar beberapa saat yang lalu. 

Jadi mari kita pergi ke depan dan sangat kecewa. Jangan swap, dan menjalankan tanpa swap, zoom pada output sini. Masukkan x adalah 1, y adalah 2, swapping bertukar. x masih 1, dan y masih 2. Jadi meskipun, terus terang, ini terlihat persis seperti, meskipun lebih teknis, apa Laura lakukan, tampaknya tidak bekerja. Jadi kenapa begitu? Nah, ternyata bahwa ketika kita menulis program seperti ini yang kedua utama, disorot sini, dan kemudian fungsi lain, seperti swap, disorot di sini, yang itu panggilan, dunia terlihat sedikit sesuatu seperti nampan ini beberapa saat yang lalu. Ketika main pertama dipanggil, itu seperti meminta sistem operasi untuk sedikit memori untuk setiap lokal variabel seperti x dan y yang memiliki utama, dan mereka akhirnya di sana. Tapi jika panggilan utama menukar, dan main lolos ke swap dua argumen, a dan b, jus jeruk dan susu, tidak seperti menyerahkan jus jeruk dan susu Laura. Apa komputer tidak, itu melewati salinan jus jeruk dan salinan dari susu Laura, sehingga apa akhirnya dalam baki ini adalah nilai satu dan dua, atau OJ dan susu, tetapi salinannya, sehingga pada saat ini dalam cerita, ada adalah OJ dan susu di setiap nampan. Ada satu dan dua di setiap nampan, dan fungsi swap memang bekerja. Ini swapping mereka di dalam dari baki paling atas kedua, tapi swapping yang tidak memiliki dampak. Dan berdasarkan hanya beberapa Prinsip dasar kami telah bicarakan sebelumnya, dan memang hanya beberapa menit yang lalu, apa yang mungkin menjelaskan mengapa perubahan a dan b dalam swap tidak berpengaruh pada x dan y, meskipun Aku melewati x dan y untuk fungsi swap. Apa kata kunci di sini bahwa mungkin menyederhanakan menjelaskan? Saya pikir saya dengar di sini? AUDIENCE: Kembali. SPEAKER 1: Kembali? Tidak kembali. Mari kita pergi dengan yang lain. Apa itu? 

AUDIENCE: [Tak terdengar]. 

SPEAKER 1: OK, jadi kita bisa return-- membuat pekerjaan kembali dalam cerita, tapi ada penjelasan yang lebih sederhana. AUDIENCE: Cakupan. SPEAKER 1: Lingkup. Aku akan mengambil ruang lingkup. Jadi ruang lingkup, ingat di mana x dan y kita menyatakan. Mereka menyatakan dalam dari utama tepat di sini. a dan b, sementara itu, efektif menyatakan dalam swap, tidak cukup di kurung kurawal tetapi masih di wilayah umum swap. Jadi memang, a dan b hanya ada di dalam baki ini dari Annenberg, ini potongan kedua kode. Jadi kita memang mengubah copy, tapi itu tidak benar-benar semua yang bermanfaat. 

Jadi mari kita lihat tingkat ini sedikit lebih rendah. Aku akan kembali ke Direktori Source, dan aku akan lebih dulu memperbesar sini, dan hanya untuk mengkonfirmasi bahwa aku dalam hal ini jendela terminal yang lebih besar, program masih berperilaku seperti itu. Misalkan sekarang ini tidak disengaja. Jelas saya ingin swap kerja, jadi rasanya seperti bug. Sekarang saya bisa mulai menambahkan banyak printf untuk kode saya, mencetak x di sini, y atas di sini, di sini, di sini b. Tapi terus terang, itu mungkin apa yang Anda telah lakukan selama beberapa minggu sekarang, secara jam kantor dan di rumah ketika bekerja pada psets mencoba untuk menemukan beberapa bug. Tapi Anda akan melihat, jika Anda belum melakukannya, masalah itu menetapkan tiga memperkenalkan Anda untuk perintah yang disebut GDB, mana GDB, GNU debugger, memiliki sendiri sejumlah besar fitur yang benar-benar dapat mari kita memahami situasi seperti ini, tetapi lebih compellingly, memecahkan masalah dan menemukan bug. Jadi aku akan melakukan hal ini. Alih-alih ./noswap, aku bukan akan menjalankan GDB ./noswap. Dengan kata lain, aku akan menjalankan saya Program tidak di Bash, teman baru kami hari ini. Aku akan menjalankan saya Program NOSWAP dalam program lain yang disebut GDB, yang merupakan debugger, yang adalah sebuah program yang dirancang untuk membantu Anda tampaknya manusia menemukan dan menghapus bug. Jadi jika aku memukul Jalankan sini, ada jumlah mengerikan teks bahwa Anda benar-benar tidak perlu membaca. Ini dasarnya gangguan dari prompt, yang Aku akan memukul Control-L bangun di atas sana. Ini adalah prompt GDB. Jika saya ingin menjalankan program ini sekarang, sebagai cheat ini lembar kecil di hari ini geser menunjukkan, Run adalah yang pertama memerintahkan agar kita dimaksudkan untuk memperkenalkan. Dan aku hanya akan mengetikkan berlari di sini dalam GDB, dan memang itu berlari program saya. Sekarang ada beberapa tambahan output dari layar seperti ini, tapi itu hanya menjadi GDB anal dan mengatakan kepada kita apa yang terjadi. Anda tidak benar-benar perlu khawatir tentang rincian ini sekarang. Tapi apa benar-benar keren tentang GDB, jika saya melakukan ini lagi-- Control-L membersihkan screen-- biarkan aku pergi depan dan ketik "istirahat utama," demikian, ketika saya tekan Enter, pengaturan apa disebut titik istirahat di noswap.c, baris 16, yang mana GDB tahu program saya benar-benar adalah, fungsi saya sebenarnya. Ini kita akan mengabaikan untuk saat ini tapi itu alamat dalam memori khusus dari fungsi ini. Jadi sekarang ketika saya mengetik menjalankan, melihat apa yang keren di sini. Program saya istirahat di garis I mengatakan GDB untuk menghentikan eksekusi pada. Jadi saya tidak harus sekarang mengubah kode saya, menambahkan beberapa printf ini, mengkompilasi ulang itu, jalankan kembali itu, mengubah, menambah beberapa printf ini, menyimpannya, mengkompilasi ulang, menjalankannya. Aku hanya bisa berjalan melalui program saya langkah demi langkah demi langkah dengan kecepatan manusia, tidak pada Intel-inside jenis kecepatan. 

Jadi sekarang melihat baris ini muncul di sini, dan jika aku kembali untuk program saya di gedit, melihat bahwa yang sebenarnya baris pertama kode. Ada baris 16 di gedit. Ada baris 16 dalam GDB, dan bahkan meskipun antarmuka hitam dan putih ini tidak hampir sebagai pengguna anak, ini berarti bahwa garis 16 belum dieksekusi , tapi itu akan menjadi. Jadi memang jika saya ketik cetak x, tidak printf, hanya print x, Saya mendapatkan beberapa nilai palsu di sana dari nol, karena x belum diinisialisasi belum. Jadi aku akan mengetik berikutnya, atau, jika Anda ingin menjadi mewah, hanya n untuk berikutnya. Tapi ketika saya ketik selanjutnya masukkan, sekarang melihat itu bergerak ke baris 17. Jadi logis, jika saya sudah dieksekusi baris 16 dan sekarang saya mengetikkan print x, apa yang harus saya lihat? Satu. 

Dan sekarang ini diakui membingungkan. $ 2 hanya cara mewah, jika Anda ingin lihat nilai itu nanti, Anda bisa mengatakan "dollar menandatangani dua." Hal ini seperti referensi kembali. Tapi untuk saat ini, abaikan saja. Yang menarik adalah apa yang di sebelah kanan tanda sama. Dan jika saya ketik next lagi dan mencetak y, saya harus melihat 2. Saya juga sekarang dapat mencetak x lagi, dan terus terang, jika saya mendapatkan sedikit bingung keberadaan saya, saya bisa mengetik daftar untuk daftar dan hanya melihat beberapa konteks sekitar titik aku benar-benar di. Dan sekarang saya bisa mengetik berikutnya, dan ada x adalah 1. Sekarang saya ketik selanjutnya. Oh, y adalah 2. Dan lagi, itu membingungkan, karena keluaran GDB ini sedang bercampur dengan output saya sendiri. Tetapi jika Anda perlu diingat, berdasarkan melirik bolak-balik kode Anda atau meletakkan keluar sisi berdampingan mungkin, Anda akan melihat yang benar-benar aku hanya melangkah melalui program saya. 

Tapi perhatikan apa yang terjadi selanjutnya, secara harfiah. Berikut baris 22. Biarkan aku pergi di atasnya, sehingga bergerak pada menjadi 23, dan jika saya mencetak x sekarang, masih satu. Dan jika saya mencetak y sekarang, masih satu. Jadi ini bukan latihan yang berguna. Jadi mari kita mengulang ini. Biarkan aku pergi kembali ke top dan jenis run lagi. Dan itu mengatakan program yang sedang debugged sudah dimulai, mulai dari awal. Ya, mari kita lakukan ini lagi. Dan kali ini mari kita lakukan selanjutnya, next, next, next, next, tapi sekarang hal-hal menarik. Sekarang saya ingin melangkah ke swap, jadi saya tidak mengetik berikutnya. Saya ketik langkah, dan sekarang menyadarinya telah melompat saya garis noswap.c 33. Jika saya kembali ke gedit, apa baris 33? Itulah pertama sebenarnya baris kode dalam swap. Yang bagus, karena sekarang aku bisa jenis melihat-lihat dan mendapatkan penasaran seperti apa yang terjadi benar-benar di sana. Biarkan saya mencetak tmp. Whoa. Mengapa tmp memiliki beberapa gila, palsu nilai sampah? AUDIENCE: Belum diinisialisasi. SPEAKER 1: Ini belum diinisialisasi. Dan memang, ketika Anda menjalankan sebuah program, Anda diberi sejumlah besar memori oleh sistem operasi, tetapi Anda belum diinisialisasi nilai-nilai, sehingga bit apa pun yang Anda lihat di sini, meskipun itu negatif ini besar gila jumlah, hanya berarti bahwa mereka adalah sisa-sisa dari beberapa penggunaan sebelumnya RAM itu, meskipun saya belum sendiri membutuhkannya belum. Jadi sekarang aku akan pergi ke depan dan jenis berikutnya, dan jika sekarang saya mengetikkan print tmp, apa yang harus saya lihat? Apapun nilai dari itu, adalah argumen pertama, hanya seperti x adalah yang pertama Hal yang berlalu dalam, jadi dan x harus sama, jadi mencetak tmp harus mencetak saya satu. 

Jadi apa yang Anda akan melihat di masalah set tiga adalah tutorial macam pada GDB, tetapi menyadari bahwa ini adalah awal dari melihat alat yang benar-benar akan membantu Anda memecahkan masalah jauh lebih efektif. Apa yang kita akhirnya akan lakukan pada Rabu adalah mulai mengupas beberapa lapisan dan menghapus beberapa roda pelatihan. Itu hal yang disebut string yang kami telah digunakan untuk beberapa waktu, kita akan perlahan-lahan mengambilnya dari Anda dan mulai berbicara tentang sesuatu yang lebih esoterically dikenal sebagai char *, tapi kami akan melakukan yang baik ini dan lembut pada awalnya, meskipun pointer, Mereka menyebutnya, dapat melakukan beberapa hal yang sangat buruk jika disalahgunakan, dengan melihat claymation sedikit dari teman kita Nick Parlante dari Stanford University, seorang profesor di komputer ilmu yang mengumpulkan pratayang ini dari apa yang akan datang Rabu ini. 

[VIDEO PEMUTARAN] Hei, Binky. Bangun. Sudah waktunya untuk pointer menyenangkan. 

Apa itu? Pelajari tentang pointer? Oh, goody! [END VIDEO PUTAR] SPEAKER 1: Itu menanti Anda pada hari Rabu. Kami akan lihat nanti. [VIDEO PEMUTARAN] -Dan Sekarang, Deep Thoughts, oleh Daven Farnham. 

Kenapa kita belajar C? Mengapa tidak A +? 

[Tertawa] 

[END VIDEO PUTAR]