[MUZIK bermain] 

SPEAKER 1: Baiklah, ini adalah CS50, dan ini adalah permulaan minggu empat, dan seperti yang anda mungkin pernah mendengar atau membaca, dunia telah berakhir. Melangkah di seluruh internet mempunyai menjadi pengetahuan dan kesedaran daripada pepijat dalam program, yang bahasa pengaturcaraan yang dikenali sebagai Bash. Ini telah hebat berjenama sebagai Shellshock, atau pintu Bash ini, tetapi artikel seperti ini belum biasa. Dan sebenarnya, ramai di antara mereka membawa kenangan belakang Heartbleed, yang anda mungkin perasan dalam tekan kembali musim bunga yang lepas, yang adalah juga agak dramatik. Sekarang orang-orang di antara kamu di sini hari ini, berapa ramai daripada anda mempunyai, walaupun anda tidak faham apa itu semua kira-kira, mendengar Shellshock? Baiklah, dan bagaimana ramai daripada anda mempunyai komputer yang terdedah? OK, perlu ada ini, jauh lebih tangan sehingga sekarang, atas sebab-sebab yang akan kita lihat. 

Mari kita lihat apa yang telah berlaku di dalam media dan kemudian menjelaskan sedikit di sini untuk kita dari segi teknikal. 

SPEAKER 2: pakar-pakar keselamatan mempunyai memberi amaran bahawa kecacatan yang serius boleh lebih kurang menjejaskan beratus-ratus berjuta-juta pengguna web di dunia. Jadi apa sebenarnya adalah bug yang sudah digelar Shellshock, dan apa yang ia buat? Nah, Shellshock juga dikenali sebagai Bug Bash, perisian yang mengeksploitasi. Hacker menggunakan virus untuk mengimbas terdedah sistem berjalan Linux dan Unix sistem operasi dan kemudian menjangkiti mereka. Bash adalah cangkerang baris perintah. Ini membolehkan isu pengguna arahan untuk melancarkan program dan ciri-ciri dalam perisian dengan menaip teks. Ia biasa digunakan oleh pengaturcara, dan tidak harus dibuka kepada dunia yang lebih luas, walaupun Shellshock perubahan itu. 

Nah, worringly, beberapa penganalisis memberi amaran ia boleh menjadi ancaman yang lebih besar, kerana Shellshock membolehkan lengkap kawalan mesin yang dijangkiti, manakala Heartbleed hanya dibenarkan hacker untuk mengintip komputer. Ia begitu serius, ia telah diberi 10 daripada 10 untuk keterukan oleh National Kelemahan Pangkalan Data. 2/3 daripada semua pelayan web adalah di risiko, termasuk beberapa komputer Mac. Nah, pastikan anda patch sistem anda sekarang. Sesiapa hosting laman web berjalan sistem pengendalian terjejas harus mengambil tindakan secepat mungkin. Sesiapa yang mampu harus melihat untuk pemantauan dan web permohonan mereka firewall untuk melihat keluar untuk sebarang serangan. SPEAKER 3: Perkara yang paling teruk yang boleh berlaku adalah bahawa seseorang akan menulis kod yang secara automatik akan pergi dan mengimbas internet dan akan menjejaskan semua komputer ini. Dan apabila mereka berbuat demikian, baik, perkara yang paling buruk yang mereka boleh lakukan hanya memadam segala-galanya, atau menutup laman ke bawah. Oleh itu, kita dapat melihat kerosakan dari sudut pandang, di mana kita akan mempunyai orang-orang yang berniat jahat yang hanya membuat keputusan untuk menyebabkan malapetaka dengan membawa sistem ke bawah atau memotong gambar, dan perkara-perkara seperti itu. SPEAKER 2: Ada yang mengatakan ini adalah salah satu satu yang paling sukar untuk mengukur bug pada tahun-tahun, dan ia mungkin mengambil masa beberapa minggu atau bulan untuk menentukan kesan muktamad. 

SPEAKER 1: Jadi semua itu adalah benar, tetapi yang anehnya, hampir semua gambaran yang anda hanya melihat, kecuali mungkin papan kekunci, tiada kaitan dengan bug sekalipun. Pelayan dan wayar dan sebagainya, ia semacam tangen berkaitan, tetapi pada teras ia sebenarnya cukup biasa apa yang berlaku di sini. Malah, saya pergi ke perkakas CS50 kami. Biar saya pergi ke hadapan dan memaksimumkan tetingkap terminal di sini. Dan kalian telah menggunakan ini, atau versi tertanam daripadanya, dalam gedit untuk menulis program, menaip arahan, dan sebagainya, dan ini adalah benar-benar, dan mempunyai kerana minggu, Bash, B-A-S-H. Ini adalah Bourne-lagi shell, yang hanya satu cara mewah untuk mengatakan, ini adalah satu program yang mempunyai berkelip cepat, berkesan, yang duduk di sana menunggu untuk input untuk anda. Dan ia arahan antara muka baris yang melalui anda semua telah berjalan arahan dan akhirnya menyusun dan kemudian berjalan program. 

Tetapi Bash juga pengaturcaraan yang bahasa dalam erti kata yang berikut. Anda tahu bahawa ada perintah seperti cd dan ls dan juga dilafaz dan lain-lain, tetapi anda boleh menentukan arahan anda sendiri dengan melaksanakan mereka dalam Bash. Sekarang kita tidak akan pergi ke terperinci untuk Bash bahasa pengaturcaraan, tetapi tahu, misalnya, bahawa pada masa ini, tidak ada arahan yang dikenali sebagai "hello." Oleh itu, ia boleh didapati di salah satu daripada pakej-pakej ini. Ia tidak dipasang pada komputer saya. Tanya pentadbir anda. Tetapi jika saya mahu ke sana untuk menjadi satu program yang dikenali sebagai "hello" dalam Bash atau segera saya, Saya benar-benar boleh menggunakan sintaks itu agak seperti C. Ia tidak cukup yang sama, tetapi ia kelihatan agak serupa dengan fungsi, walaupun hilang beberapa butiran. Tiada apa-apa seolah-olah berlaku, tetapi sekarang saya menaip "hello," anda sebenarnya boleh menulis program, bukan dalam C, tidak di Jawa, tidak dalam pengaturcaraan lain bahasa, tetapi dalam Bash sendiri. 

Sekarang kunci di sini ialah saya menulis menamakan saya mahu memberikan arahan baru ini, dan kurungan adalah juga simbolik ini merupakan fungsi. Sebagai mengetepikan, anda juga boleh melakukan menyeronokkan perkara, dan sebenarnya, walaupun pada Mac OS, ini adalah program yang dikenali sebagai Terminal. Ia datang dibina ke sesiapa komputer yang mempunyai Mac di dalam bilik ini, dan anda boleh melakukan perkara-perkara yang sama di dalam Mac OS, tetapi anda boleh pergi lebih lebih dari itu. Dan ini adalah sedikit yang menyeleweng, tetapi ia adalah jenis keseronokan. Saya diingatkan pagi ini, apabila memikirkan ini melalui, daripada permainan kecil saya digunakan untuk bermain dengan salah satu daripada bekas TFS CS50 ini mana bila-bila masa dia akan berjalan kaki dari keyboard dengan skrin beliau dibuka, Saya akan melaksanakan perintah seperti this-- "bertanya khabar." Dan kini bila-bila masa dia datang kembali kepada beliau keyboard selepas saya dibersihkan skrin dan dia akan duduk, cuba untuk membuat kerja-kerja, menyenaraikan isi kandungan directory-- beliau 

[AUDIO MAIN SEMULA] 

-Hello. Hello. 

SPEAKER 1: Jadi, dalam keadilan, ia tidak benar-benar "hello." Ia adalah sesuatu yang biasanya lebih menyerupai bahawa- [AUDIO MAIN SEMULA] -Beep. SPEAKER 1: --that saya would-- supaya komputer akan bersumpah kepadanya bila-bila masa dia sebenarnya duduk di papan kekunci itu. Dan dengan cepat dia digambarkan tidak meninggalkan skrin beliau dibuka kuncinya. Tetapi ini mencadangkan jenis yang keseronokan bodoh yang anda boleh mempunyai dengan sesuatu seperti Bash. Tetapi ia lebih sedikit serius, untuk memastikan, daripada itu. Dan sebenarnya, ini adalah salah satu daripada pepijat yang paling berbahaya dan tahan lama yang benar-benar melanda dunia global. Pepijat ini telah wujud untuk beberapa 20 tahun, dan anda akan melanda dalam hanya masa oleh kesederhanaan relatif. 

Jadi ini adalah wakil perintah bahawa jika anda memiliki Mac, secara literal sekarang apabila anda mempunyai penutup terbuka, anda boleh cuba menaip ke dalam yang program yang dikenali sebagai Terminal. Terminal adalah di bawah Aplikasi Utilities-- untuk sekali, pengguna Windows tidak perlu bimbang tentang threat-- tertentu tetapi orang-orang di antara kamu dengan Mac boleh menaip ini ke dalam tetingkap seperti saya akan lakukan di sini, dan jika anda menaip itu ke dalam program ini dipanggil Terminal, seperti yang saya akan lakukan sekarang, jika anda melihat perkataan "terdedah," komputer anda terdedah kepada eksploitasi. 

Sekarang apakah yang benar-benar bermakna? Dan ini adalah diakui beberapa sintaks cukup gila, tetapi mari kita sekurang-kurangnya menarik keluar beberapa aspek yang menarik. Jadi ada beberapa sintaks yang kelihatan yang biasa sedikit, sekurang-kurangnya dari C dan pengaturcaraan amnya. Saya melihat beberapa kurungan, koma bertitik, pendakap kerinting, dan apa-apa, tetapi ternyata bahawa ini perkara bodoh di sini berwarna kuning pada asasnya fungsi yang melakukan apa-apa. Cara kolon berbuat apa-apa, dan koma bernoktah bermakna berhenti melakukan apa-apa. Jadi di dalam ini pendakap kerinting, hakikat yang saya ada yang sama menandatangani di sebelah kiri, ini pada dasarnya mewujudkan arahan, atau pembolehubah, dipanggil x, dan memberikan ia yang sedikit kuning kod sana. Itu boleh menjadi sesuatu seperti "echo hello "atau" mengatakan bip "atau sesuatu sewaktu dengannya. Tetapi notis jika mata anda bersiar-siar lagi ke kanan, ada lagi ke baris ini daripada hanya akhir koma bernoktah itu. "Echo terdedah," dan kemudian di luar yang ada lebih. Satu lagi koma bertitik, bash -c :. 

Jadi cerita panjang pendek, baris ini kod adalah mencukupi bagi memaksa komputer itu terdedah kepada melakukan sesuatu yang yang anda mahu ia lakukan, kerana ada bug dalam Bash mana walaupun Bash sepatutnya berhenti membaca baris arahan betul di sana selepas teks yang kuning, untuk bug lama tahun 20-plus, Bash sebenarnya telah membaca di luar koma bernoktah itu dan cantik banyak melakukan apa yang diceritakan. 

Jadi apa implikasi itu akhirnya? Saya hanya berkata "echo hello" atau "echo terdedah," tetapi bagaimana jika anda melakukan sesuatu yang sebenarnya berniat jahat, seperti rm -rf *, yang anda mungkin tidak pernah ditaip sebelum ini, dan terus-terang anda mungkin sepatutnya tidak terlalu lama lagi, kerana anda boleh melakukan banyak kerosakan dengannya. Mengapa? rm melakukan apa, sudah tentu? Menghilangkan. * Bermaksud apa? Semua. Jadi ini adalah apa yang dipanggil kad liar, jadi ia bermakna menghilangkan segala direktori semasa. r berlaku bermakna rekursif, yang bererti jika apa yang anda memotong adalah direktori, dan dalam terdapat adalah fail lain dan direktori lain, secara rekursif menyelam ke sana dan memadam semua itu. Dan -f adalah yang paling teruk daripada mereka semua. Sesiapa tahu apa-f bermakna di sini? Berkuat kuasa. Jadi cara memaksa, walaupun jika ini adalah idea yang buruk, melakukannya tanpa mendorong saya untuk pengesahan lanjut. Jadi, anda tahu, kita ketawa ini, tetapi terus-terang, saya mungkin menaip ini beberapa kali sehari, kerana hakikatnya ia adalah cara paling cepat untuk memadam sejumlah besar barangan. Tetapi saya telah melakukan beberapa kerosakan. 

Tetapi jika anda adalah untuk menipu komputer dalam menentukan beberapa pembolehubah bodoh atau fungsi dipanggil x, tetapi kemudian menipu komputer dalam melaksanakan melangkaui sempadan yang fungsi, di luar koma bertitik itu, anda memang boleh menipu komputer dalam melaksanakan sesuatu seperti rm -rf E-mel atau perintah yang atau arahan Copy. Apa-apa sahaja yang anda benar-benar boleh lakukan dengan komputer, sama ada ia memotong fail, mewujudkan fail, spam seseorang, menyerang beberapa pelayan dari jauh, jika anda boleh meluahkan ia dengan arahan, anda boleh menipu komputer untuk melakukan itu. 

Sekarang apa yang satu contoh bagaimana anda boleh melakukan ini? Nah, terdapat banyak komputer pada Bash internet berjalan. Semua pengguna kami Mac di antara mereka. Banyak pelayan Linux antara mereka juga, dan pelayan Unix. Windows lagi mendapat agak luar buku itu kecuali jika anda telah dipasang perisian khas. Sekarang banyak pelayan, untuk contoh, pelayan web berlari, dan sebenarnya Linux mungkin yang sistem operasi yang paling popular berjalan pada komputer di internet yang sedang berkhidmat menggunakan laman web. Sekarang seperti yang kita akan lihat nanti pada semester, apabila anda menghantar permintaan dari Chrome browser-- anda, Internet Explorer, whatever-- ke pelayan jauh, ternyata bahawa walaupun anda hanya ditaip www.example.com, pelayar anda menghantar mesej itu sedikit lebih sukar difahami, seperti ini. 

Tetapi notis sesuatu yang sedikit pelik. Yang pertama dua baris Saya tidak pernah dilihat sebelum ini, tetapi mereka tidak melihat terutamanya mengancam. Tetapi melihat apa yang saya dicuri untuk baris ketiga di sini. Jika lelaki yang tidak baik adalah untuk menghantar mesej seperti ini dari komputer beliau kepada Mac terdedah atau server Linux terdedah, yang anehnya Bash itu, yang mudah sedikit arahan segera, adalah kehadiran dan sering digunakan untuk melaksanakan dasarnya kandungan sesuatu mesej yang diterima. Dan berdasarkan logik tersebut, anda boleh menipu pelayan web, oleh itu, dengan menghantar sesuatu seperti User-Agent, yang biasanya sepatutnya untuk mengatakan nama pelayar anda. User-Agent Chrome, User-Agent Internet Explorer, User-Agent Firefox, ini hanyalah penyemak imbas anda cara mengenal pasti sendiri. Tetapi jika lelaki yang tidak baik sangat bijak berkata, mm mm, saya tidak akan memberitahu anda apa yang pelayar saya adalah, Saya bukannya akan menghantar anda ini samar-cari perkara dengan -rf rm * Di dalamnya, anda dapat menipu yang pelayan web terdedah di internet dalam melaksanakan apa yang di sana untuk memadam semua fail. Dan terus terang, itu bukan walaupun yang paling teruk daripada itu. Anda boleh melakukan apa-apa. Anda boleh memulakan teragih penafian perkhidmatan serangan jika anda menghantar mesej ini kepada tandan keseluruhan pelayan web dan kemudian mempunyai mereka semua turun, untuk contoh, pada pelayan Harvard.edu, dan anda boleh menyusun bang palang pintu keluar dari mereka oleh trafik rangkaian itu adalah sebaliknya dicetuskan oleh lelaki yang buruk ini. 

Jadi, cerita panjang pendek, hampir semua orang di dalam bilik ini yang memiliki sebuah Mac terdedah kepada ini. Lapisan perak adalah bahawa melainkan jika anda yang menjalankan pelayan web pada komputer riba anda, dan melainkan jika anda benar-benar dikonfigurasikan untuk membolehkan sesuatu seperti SSH ke dalamnya, anda benar-benar selamat. Ia terdedah, tetapi tidak ada satu cuba untuk mendapatkan ke dalam laptop anda, supaya anda boleh semacam yakin. Walau bagaimanapun, Apple tidak lama lagi akan menjadi mengemaskini satu penyelesaian untuk ini. Dunia Linux telah dikeluarkan beberapa pembaikan untuk Fedora dan Ubuntu dan versi lain untuk Linux, dan sesungguhnya jika anda menjalankan kemas kini 50 dalam perkakas, walaupun itu juga akan dikemaskini dan diperbetulkan. Tetapi itu juga tidak mempunyai benar-benar telah terdedah, kerana melainkan anda mempunyai tinkered dengan perkakas ini dan membuat komputer riba anda secara terbuka boleh diakses di internet, yang tidak secara lalai, anda mempunyai sebenarnya telah denda kerana daripada firewalling dan teknik-teknik lain. 

Tetapi ia adalah contoh melampau pepijat bahawa kami telah hidup selama beribu-20 untuk tahun, dan yang tahu jika seseorang selama ini telah diketahui tentang ia? Dan sebenarnya, ini adalah salah satu cabaran asas bahawa kita akan lihat nanti dalam semester mengenai keselamatan, ialah seperti di dunia sebenar, lelaki yang baik adalah di dalam keadaan itu. Untuk menjaga orang jahat keluar, kita perlu memastikan bahawa setiap pintu dikunci, bahawa setiap tetingkap adalah selamat, yang setiap pintu masuk ke dalam rumah adalah selamat untuk menjaga orang-orang jahat keluar. Tetapi apakah lelaki yang buruk perlu lakukan untuk benar-benar bertolak ansur rumah anda dan mencuri dari anda? Dia hanya perlu mencari satu unlocked pintu, satu tingkap yang pecah, atau sesuatu sepanjang garis, dan ia adalah Perkara yang sama dalam keselamatan komputer. Kita boleh menulis berjuta-juta baris kod pengaturcaraan dan menghabiskan beratus-ratus atau beribu-ribu jam cuba untuk mendapatkan ia betul, tetapi jika anda membuat hanya satu kesilapan dalam kebenaran, anda boleh meletakkan keseluruhan sistem dan sesungguhnya dalam kes ini, seluruh internet dan dunia berisiko. 

Jadi, jika anda ingin mengetahui lebih lanjut kira-kira ini, pergi ke URL ini di sini. Tidak ada keperluan untuk tindakan malam ini melainkan jika anda di kalangan mereka yang lebih selesa telah berjalan web anda sendiri pelayan, di mana anda harus, sebenarnya, mengemas kini perisian anda. 

Dan ini juga adalah gelaran ucapan, dan kini kertas kerja, bahawa kami telah dikaitkan kepada laman web kursus untuk hari ini. Ia adalah oleh rakan-rakan yang bernama Ken Thompson, yang telah menerima yang sangat terkenal anugerah dalam bidang sains komputer, dan dia memberikan ucapan ini beberapa tahun lalu, pada asasnya ini topik yang sama. Meminta orang soalan, sekiranya anda benar-benar amanah, akhirnya, perisian yang anda telah diberikan? Sebagai contoh, kita semua mempunyai telah menulis program, dan kami telah menyusun mereka dengan bunyi berdering. Dan untuk pengetahuan anda, anda telah ditulis mana-mana program untuk CS50 di mana ada pintu belakang macam, ada cara yang bahawa lelaki yang tidak baik, jika berjalan program anda, boleh mengambil alih komputer anda? Mungkin tidak, bukan? Mario, dan tamak, dan Kredit. Ini semua adalah program yang cukup kecil. Anda harus menjadi cantik buruk jika anda benar-benar dibuat keseluruhan komputer anda terdedah selepas menulis 10 atau 20 baris kod, atau sekurang-kurangnya tidak sedar beberapa implikasi keselamatan. Sekarang saya mengatakan bahawa dgn jenaka, tetapi kita akan lihat hari ini dan minggu ini ia sebenarnya benar-benar, benar-benar mudah menjadi lapuk dan membuat lebih program-program pendek yang mudah terjejas. 

Tetapi untuk sekarang, sekurang-kurangnya, menyedari bahawa soalan yang ditanya di sini adalah kira-kira bunyi berdering dalam pengkompil. Mengapa kami telah mempercayai dilafaz untuk lepas dua atau tiga minggu? Siapa yang mengatakan bahawa sesiapa yang menulis dilafaz tidak mempunyai "jika" keadaan di sana yang pada asasnya disuntik beberapa sifar dan orang-orang ke dalam setiap program itu menyusun yang akan membiarkan dia atau akses beliau komputer anda apabila anda tidur dan penutup komputer riba anda terbuka dan komputer anda sedang berjalan? Betul? Kami mempunyai ini jenis sistem penghormatan hak kini di mana kita percaya bahawa dilafaz adalah legit. Anda percaya bahawa perkakas ini legit. Anda percaya bahawa harfiah setiap program pada Mac atau PC anda boleh dipercayai. Dan sebagai pepijat ini mudah mencadangkan, walaupun ia bukan berniat jahat, yang sama sekali tidak mungkin kes itu. 

Jadi, anda perlu takut sebagai neraka. Terus terang, tidak ada yang mudah penyelesaian kepada ini selain daripada semacam kesedaran masyarakat kerumitan yang semakin meningkat bahawa kita membina di atas sistem komputer kita, dan bagaimana semakin terdedah kita dengan baik mungkin. 

Kini dengan itu berkata, Breakout. Jadi Breakout masalah menetapkan tiga, dan Breakout adalah permainan dari tadi anda mungkin ingat, tetapi bagi kita dalam masalah menetapkan tiga, ia membolehkan kita untuk mengambil perkara menyandarkan takuk supaya apabila kita menulis program, walaupun dalam tetingkap Terminal seperti ini, kita boleh berlari, akhirnya, program grafik tidak tidak seperti mereka yang kita mempunyai akses ke dalam Scratch. Jadi ini adalah kakitangan pelaksanaan Breakout, yang hanya ini bata pecah permainan yang anda bergerak dayung anda kembali dan sebagainya, dan anda memukul bola terhadap orang-orang bata berwarna sehingga atas. Jadi ini membawa kita semacam kembali ke tempat kami dapat menjadi sangat cepat dengan Awal, dan kini dengan C, melaksanakan sendiri antara muka pengguna grafik. 

Tetapi lebih daripada itu, ini set masalah mewakili pertama di mana kami memberikan anda sekumpulan kod. Dan sebenarnya, saya membawa jelas perhatian kepada ini, kerana terutamanya untuk mereka yang kurang selesa, ini masalah yang dinyatakan, sekurang-kurangnya pada pandangan pertama, akan rasa seperti kami telah mengambil ia sehingga takuk a. Kerana kita telah memberikan anda, untuk beberapa carian dan masalah dalam sorting Serangga ini, sekumpulan kod yang kita menulis, dan beberapa komen yang mengatakan "lakukan," di mana anda perlu mengisi tempat kosong. Jadi tidak terlalu menakutkan, tetapi ia adalah kali pertama kami menyampaikan anda kod yang anda perlu pertama membaca, memahami, dan kemudian menambah dan menyiapkannya. 

Dan kemudian dengan Breakout, kita akan melakukan perkara yang sama, memberikan anda beberapa dozen lebih talian kod itu, terus-terang, memberi anda banyak rangka kerja bagi permainan tetapi berhenti pendek melaksanakan batu bata dan bola dan dayung, tetapi kita melaksanakan beberapa ciri-ciri lain. Dan yang pada pandangan pertama, sekali lagi, terutamanya jika kurang selesa, mungkin kelihatan terutamanya menakutkan dan anda fikir ada begitu banyak fungsi-fungsi baru anda perlu untuk membalut fikiran anda sekitar, dan yang benar. Tetapi perlu diingat, itu agak seperti Scratch. Kemungkinan besar anda tidak menggunakan semua kepingan teka-teki dalam Scratch. Kemungkinan adalah anda tidak peduli untuk membalut fikiran anda di seluruh semua mereka kerana semua itu telah mengambil satu pandangan cepat untuk memahami, oh, itulah yang boleh saya lakukan dengan sekeping teka-teki. Dan memang, dalam masalah yang dinyatakan 3 spec, kami akan menunjukkan anda pada dokumentasi yang akan memperkenalkan anda kepada beberapa fungsi baru, dan akhirnya pengaturcaraan membina anda gunakan. Syarat, gelung, pembolehubah, dan fungsi akan sama dengan apa yang kita lihat setakat ini. 

Jadi sesungguhnya, apa yang kita akan memberikan anda beberapa contoh kod yang membolehkan anda membuat tetingkap yang tidak kelihatan tidak seperti ini, dan akhirnya mengubahnya menjadi sesuatu yang agak seperti ini. Jadi mengambil kesempatan daripada CS50, membincangkan waktu pejabat dan banyak lagi, dan mengambil keselesaan dalam fakta bahawa jumlah kod anda perlu menulis sebenarnya tidak semua yang banyak. Cabaran pertama adalah hanya untuk acclimate diri anda dengan beberapa kod yang kami tulis. 

Apa-apa soalan mengenai pset3, Shellshock, atau sebaliknya? 

PENONTON: Ia seolah-olah seperti melalui dengan Breakout bahawa kod adalah hampir gaya berorientasikan objek, tetapi saya fikir C adalah objek berorientasikan program. SPEAKER 1: Satu soalan yang sangat baik. Jadi dalam mencari melalui kod pengedaran, kod kita menulis untuk pset3, bagi mereka yang biasa, ia kelihatan seperti ia adalah satu sedikit objek berorientasikan. Jawapan ringkasnya adalah, ia adalah. Ia merupakan satu anggaran bagaimana anda mungkin melakukan kod berorientasikan objek menggunakan bahasa seperti C, tetapi ia adalah masih akhirnya prosedur. Tiada kaedah di dalam pembolehubah, kerana anda akan melihat. Tetapi ia mengingatkan itu. Dan kita akan melihat ciri-ciri yang sekali lagi apabila kita mencapai PHP dan JavaScript ke arah akhir semester. Tetapi untuk sekarang, menganggapnya sebagai tanda-tanda bahawa apa yang akan datang. Soalan yang baik. Baiklah. Jadi bergabung jenis adalah bagaimana kita perkara kiri masa lalu. Dan bergabung bentuk adalah sejuk dalam rasa bahawa ia adalah begitu banyak lebih cepat, sekurang-kurangnya berdasarkan ujian sepintas kita lakukan minggu lepas, daripada, katakan, gelembung jenis, jenis pemilihan, jenis sisipan. Dan apa yang terlalu kemas hanya bagaimana ringkas dan bersih anda boleh meluahkan ia. Dan apa yang kita katakan ia adalah atas terikat pada masa yang berjalan di merge menyusun? Yeah? 

PENONTON: n log n? 

SPEAKER 1: n log n, betul. n log n. Dan kita akan kembali kepada apa yang benar-benar bermakna atau di mana yang datang dari, tetapi ini adalah lebih baik daripada masa yang berlari yang kita lihat untuk gelembung pemilihan dan jenis sisipan? Jadi n kuasa dua. n kuasa dua adalah lebih besar daripada ini, dan walaupun ia tidak cukup jelas, tahu bahawa log n lebih kecil daripada n, jadi jika anda n kali sesuatu yang lebih kecil daripada n, ia akan menjadi kurang daripada n kuasa dua. Ia sedikit gerak hati di sana. Tetapi kita membayar harga untuk ini. Ia adalah lebih cepat, tetapi tema yang bermula muncul minggu lepas adalah tradeoff ini. Saya mendapat prestasi yang lebih baik masa yang bijak, tetapi apa yang adakah saya perlu menghabiskan di pihak yang lain tangan, untuk mencapainya? 

PENONTON: Memori. SPEAKER 1: Katakanlah lagi? PENONTON: Memori. SPEAKER 1: memori, atau ruang amnya. Dan bukan super jelas dengan manusia kita, tetapi ingat bahawa sukarelawan kami telah melangkah ke hadapan dan melangkah kembali seolah-olah ada array di sini, dan seolah-olah ada pelbagai kedua di sini bahawa mereka boleh menggunakan, kerana kita kurang lebih diperlukan untuk menggabungkan mereka semua. Kita tidak boleh hanya menukar mereka di tempat. Jadi bergabung jenis leverage adalah lebih banyak ruang, yang kita tidak perlu dengan algoritma yang lain, tetapi terbalik adalah bahawa itu lebih cepat. Dan terus-terang, di dalam ruang dunia sebenar RAM ini days--, cakera keras space-- adalah agak murah, dan sebagainya itu tidak semestinya sesuatu yang buruk. 

Jadi mari kita lihat yang cepat, sedikit lebih teratur, apa yang kita lakukan dan mengapa kita berkata ia n log n. Jadi di sini adalah lapan nombor dan lapan sukarelawan kita mempunyai masa lalu. Dan perkara pertama yang Merge Susun memberitahu kami lakukan ialah apa? PENONTON: Jurang dua. SPEAKER 1: Katakanlah lagi? PENONTON: Jurang dua. SPEAKER 1: Jurang dalam dua, betul. Ini adalah sangat mengingatkan buku telefon, jurang dan menakluk amnya. Oleh itu, kita melihat separuh kiri. Kemudian sebaik sahaja kami berkata, jenis separuh di sebelah kiri unsur-unsur, apakah yang kita seterusnya katakan? Menyusun separuh kiri kiri separuh, yang membolehkan kami, selepas membahagikan dalam dua, memberi tumpuan kepada empat dan dua. 

Bagaimana anda menyusun senarai sekarang, dalam kuning, saiz dua, dengan menggunakan Gabung Susun? Juga dibahagikan pada separuh, dan menyusun separuh kiri. Dan ini adalah di mana perkara-perkara mendapat secara ringkas bodoh sedikit. Bagaimana anda menyusun senarai itu daripada saiz satu, seperti nombor empat di sini? Ia disusun. Anda sudah selesai. 

Tetapi bagaimana anda menyusun senarai saiz satu apabila ia nombor dua? Nah, perkara yang sama, tetapi kini bagaimana ketiga dan langkah penting dalam Merge Susun? Anda terpaksa bergabung kiri separuh dan separuh yang betul. Dan sekali yang kita lakukan itu, kita melihat di empat, kita melihat dua. Kami memutuskan semua hak, jelas dua datang pertama, jadi kami meletakkan dua dalam yang tempat, diikuti oleh empat. Dan sekarang anda perlu jenis putar balik, dan ini adalah jenis ciri daripada algoritma seperti Merge Susun, memutar balik dalam ingatan. Apakah garis cerita seterusnya? Apakah yang perlu saya memberi tumpuan kepada yang akan datang? Separuh kanan kiri setengah, yang merupakan enam dan lapan. 

Jadi biarlah saya melalui langkah ini tanpa belaboring titik terlalu banyak. Enam dan lapan, maka enam adalah disusun, lapan adalah disusun. Bergabung mereka bersama-sama seperti itu, dan kini langkah seterusnya besar adalah, sudah tentu, menyusun separuh kanan dari langkah pertama dalam algoritma ini. Oleh itu, kita memberi tumpuan kepada satu, tiga, tujuh, lima. Kami kemudian memberi tumpuan kepada separuh kiri. Separuh kiri itu, separuh kanan itu, dan kemudian bergabung dalam satu dan tiga. Kemudian separuh kanan, kemudian kiri setengah itu, maka separuh yang betul itu. Bergabung dalam, dan sekarang apa langkah kekal? Bergabung separuh kiri besar dan besar separuh betul, supaya seseorang pergi di bawah sana, kemudian dua, kemudian tiga, kemudian empat, maka lima, kemudian enam, maka tujuh, maka lapan. 

Jadi sekarang kenapa ini akhirnya mendedahkan, terutamanya jika n dan logaritma lebih umumnya agak melarikan diri anda, sekurang-kurangnya dalam ingatan baru-baru ini? Nah, perhatikan ketinggian perkara ini. Kami mempunyai lapan elemen, dan kami membahagikannya dengan dua, dengan dua, dengan dua. Jadi asas log dua daripada lapan memberikan kita tiga. Dan kepercayaan saya pada yang jika yang kabur tentang itu. Tetapi asas log dua daripada lapan adalah tiga, jadi kami telah melakukan tiga lapisan bercantum. Dan apabila kita bergabung unsur-unsur, bilangan elemen yang kita melihat pada setiap daripada mereka baris? Sebanyak n, bukan? Kerana untuk bergabung baris atas, walaupun kita melakukannya sedikit demi sedikit, kita akhirnya menyentuh setiap nombor sekali. Dan di barisan kedua, untuk mereka bergabung senarai saiz dua, kami terpaksa menyentuh setiap elemen sekali. Dan kemudian di sini benar-benar jelas berturut-turut yang lalu, kami terpaksa menyentuh setiap orang elemen sekali, tetapi hanya sekali, jadi di sinilah, maka, n log n kami. 

Dan kini hanya untuk membuat perkara yang sedikit lebih formal untuk seketika, jika anda adalah kini menganalisis ini pada jenis tahap yang lebih tinggi dan cuba untuk membuat keputusan, dan bagaimana mungkin anda pergi tentang menyatakan masa yang berjalan algoritma ini hanya dengan melihat dan tidak dengan menggunakan contoh yang dibuat-? Nah, berapa banyak kali anda akan berkata yang langkah seperti ini dalam kuning akan mengambil, jika n <2 kembali? Itu merupakan O besar apa? Jadi, saya melihat satu, jadi satu langkah, mungkin dua langkah kerana itu jika dan kemudian kembali, tetapi ia pemalar masa, bukan? Oleh itu, kita kata O (1), dan itu bagaimana saya akan menyatakan ini. T, hanya menjadi masa berjalan. n adalah saiz input, jadi T (n), hanya cara yang mewah mengatakan berjalan input diberi masa bersaiz n akan menjadi atas perintah masa tetap, di O (1). 

Tetapi sebaliknya, apa tentang perkara ini? Bagaimana anda meluahkan berjalan masa garis kuning ini? T dari apa? Anda boleh jenis menipu di sini dan menjawab soalan saya cyclically. Jadi, jika masa yang berjalan di umum kita katakan adalah T (n). Dan sekarang anda jenis punting di sini dan berkata, baik, hanya menyusun separuh kiri, dan kemudian menyusun separuh betul. Bagaimana mungkin kita secara simbolik mewakili masa yang berjalan garis kuning ini? T dari apa? Apa saiz input? n lebih dua. Kenapa saya tidak hanya mengatakan bahawa? Dan maka ini adalah satu lagi T (n / 2) dan kemudian sekali lagi, jika saya menggabungkan dua bahagian disusun, berapa banyak elemen saya akan harus menyentuh jumlah? n. Jadi saya boleh meluahkan ini, hanya untuk jenis mewah, sebagai masa berjalan pada umumnya. T (n) hanya masa yang berjalan T (n / 2), ditambah T (n / 2), separuh dan separuh betul kiri, ditambah O (n), yang mungkin n langkah, tetapi mungkin, jika saya menggunakan dua jari, ia dua kali ganda langkah-langkah, tetapi ia linear. Ia beberapa beberapa langkah itulah faktor n, jadi kita mungkin menyatakan ini kerana ini. Dan ini adalah di mana sekarang kita akan menyepak bola ke belakang buku teks matematik sekolah tinggi kita kita yang berulang akhirnya berakhir menyamai ini, n kali log n, jika anda benar-benar melakukan keluar matematik yang lebih formal. 

Jadi itu hanya dua perspektif. Satu berangka dengan keras berkod contoh wakil menggunakan lapan nombor, dan yang lebih rupa umum bagaimana kita sampai di sana. Tetapi apa yang benar-benar menarik di sini adalah, sekali lagi, tanggapan ini berbasikal. Saya tidak menggunakan untuk gelung. Saya jenis mentakrifkan sesuatu dari segi sendiri, bukan sahaja dengan ini fungsi matematik, tetapi juga dari segi kod pseudo ini. Kod pseudo adalah rekursif dalam dua baris yang pada asasnya memberitahu ia pergi menggunakan sendiri untuk menyelesaikan yang lebih kecil masalah saiz yang lebih kecil, dan sekali lagi dan sekali lagi dan sekali lagi sehingga kita meraut ia turun ke kes asas yang dipanggil ini. 

Jadi mari kita sebenarnya menarik lebih menarik bawa pulang dari ini seperti berikut. Biar saya pergi ke gedit dan mengambil lihat beberapa kod sumber hari ini, khususnya contoh ini di sini. Sigma 0, yang nampaknya menambah nombor satu melalui n. Jadi mari kita lihat apa yang biasa dan tidak biasa di sini. Pertama kami mempunyai beberapa termasuk, jadi apa yang baru di sana. Prototaip. Saya kabur sedikit pada ini selepas beberapa hari, tetapi apa yang kita katakan yang prototaip fungsi adalah? PENONTON: [didengar]. SPEAKER 1: Apakah itu? PENONTON: Kami mengumumkannya. SPEAKER 1: Kami mengumumkannya. Jadi, anda sedang mengajar dilafaz, hey, sebenarnya tidak melaksanakan ini, tetapi di suatu tempat di gambar ini, mungkin, adalah akan fungsi yang dipanggil apa? Sigma. Dan ini hanyalah janji yang ia akan kelihatan seperti ini. Ia akan mengambil integer sebagai input-- dan saya boleh menjadi lebih jelas dan berkata int n --and ia akan kembali int satu, tetapi cara koma bertitik, mm, saya akan mendapatkan sekitar untuk melaksanakan ini sedikit kemudian. Sekali lagi, dilafaz adalah dalam keadaan sihat. Ia hanya akan tahu apa yang anda memberitahu ia atas ke bawah, jadi kita perlu sekurang-kurangnya memberi itu tanda-tanda bahawa apa yang akan datang. 

Sekarang mari kita lihat utama di sini. Mari kita tatal ke bawah di sini dan melihat apa yang utama lakukan. Ia bukan yang panjang fungsi, dan sebenarnya membina di sini adalah biasa. Saya mengisytiharkan pembolehubah n, dan kemudian Saya mahukan pengguna lagi dan lagi untuk integer positif menggunakan getInt, dan hanya keluar daripada gelung ini sekali pengguna telah dipatuhi. Adakah Walaupun, kami telah digunakan untuk mengganggu pengguna dengan cara itu. Sekarang ini adalah menarik. Saya mengisytiharkan int dipanggil "jawapan." Saya sediakan nilai pulangan fungsi yang dipanggil "sigma." Saya tidak tahu apa yang tidak lagi, tetapi Saya masih ingat mengisytiharkan ia sebentar tadi. Dan kemudian saya lulus dalam nilai yang pengguna ditaip, n, dan kemudian saya melaporkan jawapannya. Nah mari kita tinjau kembali hanya seketika. Mari kita pergi ke hadapan ke dalam direktori ini, membuat sigma 0, dan benar-benar menjalankan program ini dan lihat apa yang berlaku. Jadi, jika saya pergi ke depan dan jangka program ini, ./sigma-0, dan saya taip yang positif integer seperti dua, Sigma, sebagai simbol Yunani membayangkan, hanya akan menambah semua nombor sifar pada sehingga dua. Jadi 0 campur 1 plus 2. Jadi ini diharapkan dapat memberikan saya 3. Itu semua ia lakukan. Begitu juga, sekiranya saya ini sekali lagi dan saya memberikan nombor tiga, itulah 3 campur 2, supaya 5, ditambah 1 perlu memberi saya 6. Dan kemudian jika saya mendapat benar-benar gila dan mula menaip dalam jumlah yang lebih besar, ia harus memberi saya jumlah wang yang lebih besar dan lebih besar. Jadi itu sahaja. 

Jadi apakah sigma kelihatan seperti? Nah, ia cukup mudah. Ia adalah bagaimana kita mungkin telah melaksanakan ini untuk beberapa minggu lalu. "Int" akan menjadi jenis pulangan. Sigma adalah nama, dan ia mengambil yang m pembolehubah bukan n. Saya akan menukar bahawa sehingga atas. Maka ini adalah hanya cek kewarasan. Kita akan melihat mengapa dalam seketika. Sekarang saya mengisytiharkan pembolehubah yang lain, Kesimpulannya, ia memulakan dengan sifar. Kemudian saya ini Untuk gelung iterating, nampaknya untuk kejelasan, daripada i = 1 pada sehingga = m, yang merupakan apa pengguna ditaip, dan kemudian saya menokokkan jumlah yang seperti ini. Dan kemudian kembali jumlah. 

Jadi beberapa soalan. Satu, saya menuntut dalam komen saya ini mengelakkan risiko gelung tak terhingga. Mengapa lulus dalam beberapa negatif mendorong, berpotensi, gelung tak terhingga? 

PENONTON: Anda tidak akan pernah mencapai m. 

SPEAKER 1: Jangan sekali-kali mencapai m. Tetapi m diluluskan dalam, jadi mari kita mempertimbangkan contoh yang mudah. Jika m diluluskan oleh pengguna sebagai salah satu negatif. Tanpa mengira utama. Utama melindungi kita daripada ini juga, jadi saya hanya yang benar-benar dubur dengan sigma juga memastikan input yang tidak boleh menjadi negatif. Jadi, jika m adalah negatif, sesuatu seperti satu negatif. Apa yang akan berlaku? Well, i akan dapat dimulakan kepada satu, dan kemudian saya akan menjadi kurang daripada atau sama dengan m? 

Berdirilah. Yang was-- jangan, mari Nix cerita ini. Saya tidak bertanya soalan itu, kerana risiko bahawa saya merujuk kepada tidak akan berlaku kerana saya adalah sentiasa akan menjadi lebih besar OK than--, Saya menarik balik soalan itu. OK. Mari kita memberi tumpuan hanya pada bahagian ini di sini. Kenapa saya mengisytiharkan beberapa di luar gelung? Notis di talian 49 saya telah diisytiharkan i di dalam gelung, tetapi talian 48 saya telah diisytiharkan beberapa luar. Yeah. PENONTON: [didengar]. SPEAKER 1: Pasti. Jadi pertama sekali saya pasti tidak mahu mengaku dan memulakan jumlah kepada sifar bahagian dalam gelung pada setiap lelaran, kerana ini jelas akan mengalahkan tujuan menjumlahkan nombor. Saya akan sentiasa berubah nilai kembali ke sifar. Dan juga, apa yang lain lebih sukar difahami Sebab bagi yang demikian keputusan reka bentuk yang sama? Yeah. 

PENONTON: [didengar]. SPEAKER 1: Tepat sekali. Saya mahu mengaksesnya di luar gelung terlalu kepada apa line? Pada 53. Dan berdasarkan peraturan kami ibu jari daripada beberapa ceramah yang lalu, pembolehubah adalah scoped, benar-benar, kepada pendakap kerinting yang merangkumi mereka. Jadi, jika saya tidak mengisytiharkan jumlah wang yang di dalam ini pendakap kerinting luar, Saya tidak boleh menggunakan ia dalam talian 53. Dengan kata lain, jika saya mengisytiharkan jumlah wang di sini, atau dalam Untuk gelung, saya tidak dapat mengaksesnya di 53. Pembolehubah yang berkesan akan hilang. Jadi beberapa sebab di sana. Tetapi sekarang mari kita kembali dan lihat apa yang berlaku. Jadi sigma mendapat dipanggil. Ia menambah sehingga 1 plus 2, atau 1 plus 2 campur 3, dan kemudian mengembalikan nilai, kedai-kedai dalam jawapan, dan printf sini Sebab itulah saya melihat pada skrin. Jadi ini adalah apa yang kita akan memanggil lelaran pendekatan, di mana lelaran hanya bermakna menggunakan gelung. A Untuk gelung, gelung Walaupun, Do Walaupun gelung, hanya melakukan sesuatu sekali lagi dan lagi dan lagi. 

Tetapi sigma adalah jenis fungsi kemas di bahawa saya boleh melaksanakannya berbeza. Apa tentang perkara ini, yang hanya untuk jenis sejuk, biarlah saya benar-benar menghapuskan daripada banyak gangguan kerana fungsi ini adalah benar-benar agak mudah. Mari kita meraut ke bawah hanya kepada garis empat teras yang dan menghapuskan semua komen dan pendakap kerinting. Ini adalah jenis yang fikiran-bertiup pelaksanaan alternatif. Baiklah, mungkin tidak keberatan-bertiup, tetapi ia jenis seksi, hak semua, melihat ini banyak lagi ringkas. Dengan hanya empat baris kod, Saya pertama mempunyai cek kewarasan ini. Jika m adalah kurang daripada atau sama dengan sifar, sigma tidak masuk akal. Ia hanya sepatutnya berada di kes ini untuk nombor positif, jadi saya hanya akan kembali sifar sewenang-wenangnya supaya kita sekurang-kurangnya mempunyai beberapa yang dikenali sebagai kes asas. 

Tetapi di sini kecantikan. Keseluruhan dari idea ini, menambah nombor dari 1 hingga n, atau m dalam kes ini, boleh dilakukan dengan jenis menolak tanggungjawab. Nah, apa adalah jumlah 1 hingga m? Nah, anda tahu apa? Ia adalah sama seperti jumlah m dicampur dengan jumlah 1 hingga m tolak 1. Baik anda tahu apa? Apa sigma m tolak 1? Nah, jika anda jenis ini mengikuti secara logik, ia adalah sama seperti m tolak 1 ditambah sigma m tolak 2. Jadi, anda boleh jenis just-- ini adalah seperti, jika anda hanya cuba untuk menyakitkan hati rakan dan mereka tanya satu soalan, anda jenis bertindak balas dengan soalan, anda boleh menyimpan jenis menolak tanggungjawab. Tetapi apa yang penting adalah bahawa jika anda menyimpan membuat soalan yang lebih kecil dan lebih kecil dan lebih kecil, anda tidak bertanya apa yang sigma n, apa sigma daripada n, apa sigma n? Anda meminta apa yang sigma n, apa sigma n tolak 1, apa yang sigma n tolak 2? Akhirnya soalan anda akan menjadi apa? Apakah sigma satu atau sifar, beberapa nilai yang sangat kecil, dan sebaik sahaja anda mendapatkan itu, rakan anda, anda tidak akan meminta soalan yang sama sekali lagi, anda hanya akan berkata, oh ia sifar. Kami selesai bermain seperti ini permainan kitaran bodoh. 

Jadi rekursi adalah perbuatan yang pengaturcaraan fungsi yang memanggil dirinya. Program ini, apabila disusun dan menjalankan, adalah akan berkelakuan dengan cara yang sama, tetapi apa yang penting adalah bahawa di dalam fungsi yang dikenali sebagai sigma, terdapat satu baris kod mana kita memanggil diri kita sendiri, yang biasanya akan menjadi buruk. Sebagai contoh, bagaimana jika saya pertama disusun ini, sehingga membuat sigma-- membuat sigma 1 ./sigma-1. Integer positif, sila, 50 1275. Jadi apa fungsi yang seolah-olah berkenaan, berdasarkan satu ujian, betul. Tetapi bagaimana jika saya mendapatkan sedikit berbahaya dan memadam kes asas yang dipanggil, dan hanya berkata, dan saya hanya membuat ini lebih rumit daripada ia. Mari kita mengira sigma dengan mengambil m dan kemudian menambah dalam sigma m tolak satu? Nah, apa yang akan berlaku di sini? Mari kita zum keluar. Mari kita susun semula program ini, menyimpannya, susun semula program ini, dan kemudian bersedia ./sigma-1 zoom dalam, memasukkan integer positif sila, 50. Berapa ramai daripada anda sanggup untuk Mengakulah untuk melihat bahawa? 

OK. Jadi ini boleh berlaku untuk beberapa sebab, dan terus terang minggu ini kami akan memberi anda lebih banyak daripada mereka. Tetapi dalam kes ini, cuba dengan alasan ke belakang apa yang mungkin berlaku di sini? Segmentasi bersalah, kita berkata lalu masa, merujuk kepada segmen memori. Sesuatu yang buruk berlaku. Tetapi apa yang ia mekanikal yang pergi serba salah sini kerana pemecatan saya itu yang dikenali sebagai kes asas, di mana saya mengembalikan nilai keras berkod? Apa yang anda fikir yang salah? Yeah. 

PENONTON: [didengar]. SPEAKER 1: Ah. Soalan yang baik. Jadi saiz bilangan bahawa saya telah merumuskan mendapat begitu besar bahawa ia melebihi saiz ruang memori. Idea yang baik, tetapi tidak pada asasnya akan menyebabkan kemalangan. Yang mungkin menyebabkan limpahan integer, di mana bit hanya terbalik dan kemudian kita kesilapan yang benar-benar besar seperti nombor untuk nombor negatif, tetapi itu sendiri tidak akan menyebabkan kemalangan. Kerana pada akhir hari int adalah masih 32 bit. Anda tidak akan sengaja mencuri sedikit ke-33. Tetapi pemikiran yang baik. Yeah. 

PENONTON: [didengar]. SPEAKER 1: Kaedah ini tidak pernah berhenti berlari, dan sememangnya ia memanggil sendiri lagi dan lagi dan lagi dan lagi dan sekali lagi, dan tiada fungsi-fungsi yang pernah selesai kerana talian tunggal mereka kod panggilan dirinya sendiri sekali lagi dan sekali lagi dan lagi. Dan apa yang benar-benar berlaku di sini, dan kini kita jenis ini boleh menarik bergambar. Biar saya pergi ke satu gambar hanya seketika. Ini adalah gambar, yang akhirnya akan daging keluar dengan lebih terperinci, daripada apa yang berlaku di di dalam memori komputer anda. Dan ternyata bahawa pada bahagian bawah gambar ini adalah sesuatu yang dinamakan tindanan. Ini adalah sebahagian daripada ingatan, sebahagian RAM, yang yang hanya digunakan bila-bila masa fungsi dipanggil. Bila-bila masa anda, programmer, memanggil fungsi, sistem operasi, seperti Mac OS, Windows atau Linux, menangkap sekumpulan bait, mungkin beberapa kilobytes, mungkin beberapa megabait ingatan, tangan mereka kepada anda, dan kemudian membolehkan anda menjalankan fungsi anda menggunakan apa pembolehubah yang anda perlukan. Dan jika anda kemudian memanggil lagi fungsi dan fungsi lain, anda mendapat satu lagi sebahagian daripada memori dan satu lagi keping ingatan. 

Dan sesungguhnya, jika ini dulang hijau dari Annenberg mewakili memori itu, di sini adalah apa yang berlaku pertama kali anda memanggil fungsi sigma. Ia seperti meletakkan dulang seperti ini pada apa yang pada mulanya stack kosong. Tetapi jika dulang yang panggilan sendiri, jadi untuk bercakap, memanggil contoh lain daripada sigma, itu seperti bertanya sistem operasi, aduh, perlu memori yang lebih sedikit, memberi saya itu. Dan kemudian ia akan bertimbun di atas. Tetapi apa yang penting di sini ialah dulang pertama masih ada, kerana dia digunakan dulang kedua ini. Sekarang sementara itu, sigma panggilan sigma, itu seperti meminta lebih banyak memori. Dapat bertimbun di sini. sigma panggilan sigma, itu lain dulang yang mendapat bertimbun di sini. Dan jika anda terus melakukan perkara ini, akhirnya, jenis peta visual ini carta itu, apa yang akan berlaku dengan timbunan dulang? Ia akan melebihi jumlah yang memori komputer anda mempunyai. Dan sebaik sahaja dulang hijau ini melebihi garisan mendatar di atas timbunan dan ke atas perkataan timbunan, yang kita akan kembali ke dalam masa depan, bahawa adalah satu perkara yang tidak baik. Timbunan itu yang berbeza segmen ingatan, dan jika anda membiarkan ini dulang cerucuk dan cerucuk pada, anda akan melebihi segmen anda sendiri ingatan, dan program yang memang akan crash. 

Sekarang sebagai diketepikan, idea ini daripada rekursi, oleh itu, dengan jelas boleh membawa kepada masalah, tetapi ia tidak semestinya sesuatu yang buruk. Kerana menganggap, selepas semua, how-- dan mungkin ini mengambil masa untuk membiasakan diri untuk --how elegan atau bagaimana mudah bahawa pelaksanaan sigma adalah. Dan kami tidak akan menggunakan rekursi semua yang banyak dalam CS50, tetapi dalam CS51, dan benar-benar mana-mana golongan di mana anda memanipulasi struktur data seperti pokok-pokok, atau pokok-pokok keluarga, yang mempunyai beberapa hierarki, ia super, super berguna. Sekarang, sebagai diketepikan, supaya anda sebagai ahli-ahli sains komputer yang bercita-cita sudah biasa dengan beberapa Google jenaka di dalam, jika anda pergi ke Google dan anda mencari apakah definisi, berkata, rekursi, masukkan. Uh-huh. Sebagai mengetepikan, saya ditarik ke atas beberapa. Ini adalah seperti 10 minit procrastination pagi ini. Jika anda juga Google "serong," notis dengan menyengetkan kepala anda slightly-- dan kemudian satu ini mungkin yang paling kejam sekali sejak seseorang menghabiskan seperti hari mereka melaksanakan ini beberapa tahun ago-- datang. Oh, wait-- itu pepijat. 

Jadi berjalan pada salah satu laman web terbesar dunia adalah ini bodoh sedikit telur Paskah. Mereka mungkin memakan bilangan nontrivial senarai kod hanya supaya kita boleh mempunyai perkara yang menyeronokkan kecil seperti itu. Tetapi sekurang-kurangnya sekarang anda mendapatkan beberapa orang-orang di dalam jenaka. 

Sekarang mari kita lihat pada beberapa putih terletak kami telah memberitahu lewat, dan mula mengupas kembali beberapa lapisan teknikal supaya anda benar-benar memahami apa yang telah berlaku dan anda boleh memahami beberapa ancaman, seperti Shellshock, yang kini telah mula menjadi di barisan hadapan dalam semua orang perhatian, sekurang-kurangnya dalam media. Jadi di sini adalah fungsi yang sangat mudah yang mengembalikan apa-apa, tidak sah. Namanya adalah swap. Ia mengambil masa dalam dua pembolehubah dan ia akan mengembalikan apa-apa. Mengambil masa dalam a dan b. Jadi demonstrasi cepat. Kami dibesarkan ini. Kita juga mungkin mengambil sedikit memecahkan di sini untuk seketika dan mempunyai sesuatu yang kecil untuk minum. Jika seseorang tidak keberatan menyertai saya di sini untuk seketika. Bagaimana pula dengan anda dalam baju merah? Marilah naik. Hanya satu hari ini. Terima kasih, walaupun. Baiklah, dan kami mempunyai yang datang di sini? Apa nama anda? 

SPEAKER 4: Laura. 

SPEAKER 1: Laura. Marilah naik. Jadi Laura, cabaran yang sangat mudah hari ini. Nice untuk memenuhi yo. Baiklah. Jadi kita mempunyai sedikit susu di sini dan kita mempunyai beberapa jus oren di sini dan beberapa cawan yang kita dipinjam daripada Annenberg hari ini. 

SPEAKER 4: dipinjam. SPEAKER 1: Dan akan pergi ke depan dan memberi anda setengah gelas ini. Baiklah. Dan kami akan memberikan separuh segelas susu. Oh, dan hanya supaya anda boleh ingat apa ini adalah seperti, Saya teringat untuk membawa ini dan pada hari ini. Okay. Jika anda tidak keberatan, mari kita lihat, kita boleh meletakkan mereka ke atas kaca mata anda sendiri jika anda mahu. Ini akan dunia dari mata Laura itu. Baiklah. Jadi matlamat anda, dengan dua cawan cecair di sini, susu dan jus oren, adalah menukar dua kandungan supaya jus oren masuk ke dalam cawan susu dan susu yang masuk ke dalam cawan jus oren. 

SPEAKER 4: Adakah saya mendapatkan cawan yang lain? SPEAKER 1: Saya amat gembira anda bertanya, walaupun ia akan menjadi rakaman jauh lebih baik jika anda tidak meminta. Tetapi ya, kita boleh menawarkan anda satu pertiga cawan yang kosong, sudah tentu. Baiklah. Jadi menukar kandungan di sana. Very nice. Sangat baik. Anda lakukan ini amat berhati-hati. Dan langkah tiga. Baiklah. Cemerlang. Satu pusingan besar tepukan akan menjadi baik untuk Laura. Baiklah. Kami mempunyai hadiah perpisahan sedikit untuk anda, tetapi biarlah saya mengambil ini. Terima kasih banyak. Jadi contoh yang mudah, walaupun, untuk menunjukkan bahawa jika anda melakukan ingin tukar kandungan dua bekas, atau mari kita memanggil mereka pembolehubah, anda memerlukan penyimpanan sementara untuk mengadakan satu kandungan dalam berbuat bahawa anda sebenarnya boleh melakukan swap. Jadi sesungguhnya, kod sumber ini di sini di C adalah wakil betul-betul itu. Jika jus oren adalah satu dan susu adalah b, dan kami mahu menukar kedua-dua, anda boleh mencuba sesuatu yang kreatif dengan menuang satu ke yang lain, tetapi itu mungkin tidak akan berakhir terutamanya dengan baik. Dan supaya kita menggunakan cawan ketiga, panggilan ia RMT, T-M-P oleh konvensyen, dan meletakkan kandungan OJ dalam itu, kemudian menukar satu cawan, kemudian meletakkan ke dalam OJ cawan asal, dengan itu mencapai, tepat seperti yang Laura lakukan, swap. 

Jadi mari kita melakukan perkara tersebut. Biar saya pergi ke hadapan dan membuka sehingga satu contoh itu sebenarnya dipanggil "tidak swap, "kerana ini bukan sebagai hanya dilakukan kerana anda mungkin berfikir. Jadi, dalam program ini, melihat bahawa Saya menggunakan stdio.h, kawan lama kami. Saya mempunyai prototaip untuk swap di sana, yang ertinya pelaksanaannya ini mungkin ke bawah di bawah, dan mari kita lihat apa ini utama program yang akan lakukan untuk saya. Saya pertama mengisytiharkan int x mendapat satu, dan int y mendapat dua. Jadi memikirkan mereka sebagai OJ dan susu masing-masing. Dan kemudian saya hanya mempunyai printf berkata x ialah dan y adalah ini, supaya saya boleh visual melihat apa yang berlaku. Kemudian saya telah printf mendakwa bahawa saya bertukar-tukar kedua-dua, dan kemudian saya mencetak mendakwa bahawa mereka ditukar, dan saya mencetak x dan y lagi. Jadi turun di sini di swap adalah apa Laura lakukan, dan apa yang kita lihat pada skrin sebentar tadi. 

Jadi mari kita pergi ke depan dan menjadi sangat kecewa. Janganlah swap, dan menjalankan tiada swap, zoom di atas output di sini. Masukkan x adalah 1, y ialah 2, Pertukaran ditukar. masih x 1, y dan masih 2. Jadi walaupun, terus terang, ini kelihatan betul-betul suka, walaupun lebih teknikal, apa Laura lakukan, tidak kelihatan untuk bekerja. Jadi mengapa yang? Nah, ternyata bahawa apabila kita menyediakan program seperti ini yang kedua-dua utama, yang diketengahkan di sini, dan kemudian fungsi lain, seperti swap, menekankan di sini, yang ia memanggil, dunia kelihatan sesuatu yang kecil seperti dulang ini sebentar tadi. Apabila utama pertama mendapat dipanggil, itu seperti bertanya sistem operasi untuk sedikit memori untuk mana-mana tempat pembolehubah seperti x dan y yang mempunyai utama, dan mereka berakhir di sana. Tetapi jika panggilan utama swap, dan utama pas untuk menukar dua hujah, a dan b, jus oren dan susu, ia tidak suka menyerahkan jus oren dan susu untuk Laura. Apa komputer tidak, adakah pas salinan jus oren dan salinan susu untuk Laura, supaya apa yang akhirnya di dalam dulang ini adalah satu nilai dan dua, atau OJ dan susu, tetapi salinannya, supaya pada ketika ini dalam cerita itu, terdapat adalah OJ dan susu dalam setiap dulang ini. Ada satu dan dua dalam setiap dulang ini, dan fungsi swap ini memang bekerja. Ia bertukar-tukar mereka dalam dulang kedua paling atas, tetapi bertukar-tukar yang tidak mempunyai kesan. Dan berdasarkan beberapa prinsip asas kita kena bercakap tentang sebelum ini, dan sesungguhnya hanya beberapa minit yang lalu, apa yang mungkin menjelaskan mengapa berubah a dan b di dalam swap mempunyai kesan ke atas x dan y, walaupun Saya lulus x dan y dengan fungsi swap. Apa perkataan utama di sini bahawa simplistically mungkin menjelaskan? Saya rasa saya mendengar ia di sini? PENONTON: Return. SPEAKER 1: Kembali? Tidak kembali. Mari kita pergi dengan satu yang lain. Apa itu? 

PENONTON: [didengar]. 

SPEAKER 1: OK, jadi kita boleh return-- membuat kerja kembali dalam cerita, tetapi ada penjelasan yang lebih mudah. PENONTON: Skop. SPEAKER 1: Skop. Saya akan mengambil skop. Jadi skop, ingat di mana x dan y kami diisytiharkan. Mereka diisytiharkan dalam daripada hak utama di sini. a dan b, sementara itu, adalah berkesan diisytiharkan bahagian dalam swap, tidak cukup di pendakap kerinting tetapi masih di kawasan umum swap. Dan memang, a dan b hanya wujud di dalam dulang ini dari Annenberg, ini sebahagian kedua kod. Jadi, kita memang berubah salinan, tetapi itu tidak benar-benar semua yang membantu. 

Jadi mari kita lihat tahap yang sedikit lebih rendah ini. Saya akan kembali ke Direktori Sumber, dan saya akan pertama zum di sini, dan hanya mengesahkan bahawa saya dalam ini tetingkap terminal yang lebih besar, program ini masih berkelakuan seperti itu. Katakan sekarang ini tidak sengaja. Jelas sekali saya mahu swap untuk kerja, jadi ia berasa seperti pepijat. Sekarang saya boleh mula menambah banyak printf untuk kod saya, mencetak x di sini, y lebih di sini, di sini, b di sini. Tetapi terus terang, itu mungkin apa yang anda telah lakukan untuk beberapa minggu sekarang, dalam waktu pejabat dan di rumah apabila bekerja pada psets cuba mencari beberapa bug. Tetapi anda akan lihat, jika anda tidak mempunyai sudah, masalah yang menetapkan tiga memperkenalkan anda kepada perintah yang dipanggil GDB, mana GDB, GNU penyahpepijat, mempunyai sendiri sejumlah besar ciri-ciri yang benar-benar boleh mari kita memahami keadaan seperti ini, tetapi ia amat lebih, menyelesaikan masalah dan mencari bug. Jadi saya akan melakukan ini. Daripada ./noswap, saya bukan akan menjalankan GDB ./noswap. Dalam erti kata lain, saya akan berjalan saya program tidak Bash, kawan baru kami hari ini. Saya akan berjalan saya program noswap dalam program ini selain dikenali sebagai GDB, yang debugger, yang adalah satu program yang direka untuk membantu anda manusia zaman dan menghapuskan bug. Jadi jika saya memukul Main di sini, ada jumlah kejam teks bahawa anda benar-benar tidak perlu dibaca. Ia pada dasarnya gangguan dari segera, yang Saya akan melanda Kawalan-L bangun di atas sana. Ini adalah segera GDB itu. Jika saya mahu menjalankan program ini sekarang, kerana ini kunci cheat sedikit pada hari ini slaid menunjukkan, Run adalah yang pertama menyuruh kami bermaksud untuk memperkenalkan. Dan saya hanya akan menaip berjalan di sini di dalam GDB, dan sememangnya ia berlari program saya. Sekarang ada beberapa tambahan output skrin seperti ini, tetapi itu hanya menjadi GDB dubur dan memberitahu kita apa yang sedang berlaku. Anda tidak benar-benar perlu bimbang mengenai butiran ini sekarang. Tetapi apa yang benar-benar sejuk tentang GDB, jika saya melakukan ini again-- Kawalan-L membersihkan screen-- biarlah saya pergi hadapan dan jenis "memecahkan utama," dengan itu, apabila saya tekan Enter, menetapkan apa yang dipanggil titik rehat di noswap.c, talian 16, yang mana GDB digambarkan program saya sebenarnya adalah, fungsi saya sebenarnya. Ini kita akan mengabaikan untuk sekarang tetapi itu alamat dalam ingatan khusus fungsi ini. Jadi sekarang apabila saya menaip berlari, perhatikan apa yang sejuk di sini. Program ni memecah di garisan I memberitahu GDB untuk berhenti seketika di pelaksanaan. Jadi saya tidak perlu kini menukar kod saya, menambah beberapa printf ini, susun semula ia, jalankan lagi ia, menukar, menambah beberapa printf ini, menyimpannya, susun semula ia, menjalankannya. Saya hanya boleh berjalan melalui program saya langkah demi langkah demi langkah pada kelajuan manusia, tidak sama jenis Intel-bahagian dalam kelajuan. 

Jadi sekarang perhatikan baris ini muncul di sini, dan jika saya kembali untuk program saya dalam gedit, melihat bahawa yang sebenarnya baris pertama kod. Ada talian 16 dalam gedit. Ada talian 16 dalam GDB, dan juga walaupun muka hitam dan putih ini tidak hampir sebagai pengguna mesra, ini bermakna bahawa 16 talian belum dilaksanakan lagi, tetapi ia akan menjadi. Jadi memang saya menaip cetak x, tidak printf, hanya cetak x, Saya mendapat beberapa nilai palsu terdapat sifar, kerana x belum dimulakan lagi. Jadi saya akan menaip depan, atau, jika anda mahu menjadi mewah, hanya n untuk seterusnya. Tetapi apabila saya menaip seterusnya memasuki, kini notis ia bergerak ke baris 17. Jadi secara logiknya, jika saya telah dilaksanakan talian 16 dan saya taip cetak x, apa yang perlu saya lihat? Satu. 

Dan sekarang ini diakui mengelirukan. $ 2 adalah hanya satu cara mewah daripada, jika anda ingin merujuk kepada nilai yang kemudian, anda boleh berkata "dolar menandatangani dua." Ia seperti rujukan kembali. Tetapi untuk sekarang, hanya tidak mengendahkannya. Apa yang menarik adalah apa yang di sebelah kanan tanda yang sama. Dan sekarang saya menaip datang lagi dan y cetak, saya akan melihat 2. Saya juga kini boleh mencetak x lagi, dan terus-terang, jika saya mendapat sedikit keliru untuk di mana saya, saya boleh menaip senarai untuk senarai dan hanya melihat beberapa konteks sekitar titik Saya sebenarnya di. Dan sekarang saya boleh menaip akan datang, dan ada x ialah 1. Sekarang saya menaip depan. Oh, y ialah 2. Dan sekali lagi, ia mengelirukan, kerana output GDB ini sedang berbaur dengan output saya sendiri. Tetapi jika anda ingat, dengan sambil mengerling ke belakang dan sebagainya di kod anda atau meletakkan ia keluar sebelah menyebelah mungkin, anda akan melihat yang benar-benar saya hanya melangkah melalui program saya. 

Tetapi melihat apa yang berlaku seterusnya, secara literal. Berikut adalah garis 22. Biar saya pergi ke ia, dengan itu beralih hingga 23, dan jika saya mencetak x sekarang, masih satu. Dan jika saya mencetak y sekarang, masih satu. Jadi ini tidak adalah satu latihan yang berguna. Jadi mari kita buat semula ini. Biar saya naik semula ke top dan jenis jangka lagi. Dan ia berkata program ini yang yang yang debugged telah bermula sudah, bermula dari awal. Ya, mari kita buat ini lagi. Dan kali ini mari kita buat akan datang, akan datang, akan datang, akan datang, akan datang, tetapi kini hal-hal yang menarik. Sekarang saya mahu melangkah ke swap, jadi saya tidak menaip depan. Saya menaip langkah, dan kini menyedarinya telah meningkat saya untuk talian noswap.c 33. Jika saya kembali ke gedit, apa talian 33? Itu yang pertama sebenar baris kod bahagian dalam swap. Yang bagus, kerana sekarang saya boleh jenis mencucuk sekitar dan mendapatkan ingin tahu tentang apa yang berlaku benar-benar di sana. Biar saya mencetak tmp. Wah. Mengapa tmp mempunyai beberapa gila, nilai sampah palsu? PENONTON: Ia belum dimulakan. SPEAKER 1: Ia belum dimulakan. Dan sesungguhnya, apabila anda menjalankan program, anda diberi sejumlah besar memori oleh sistem operasi, tetapi anda tidak dimulakan apa-apa nilai, jadi apa sahaja bit anda lihat di sini, walaupun ia negatif ini gila besar nombor, hanya bermakna bahawa mereka adalah sisa-sisa dari beberapa penggunaan sebelumnya RAM itu, walaupun saya tidak mempunyai diri saya diperlukan lagi. Jadi sekarang saya akan pergi ke depan dan jenis akan datang, dan jika saya kini taip cetak tmp, apa yang perlu saya lihat? Apa sahaja nilai yang adalah, adalah hujah yang pertama, hanya seperti x adalah yang pertama perkara yang diluluskan pada, jadi dan x perlu yang sama, jadi tmp mencetak perlu mencetak saya satu. 

Jadi apa yang anda akan melihat dalam set masalah tiga adalah tutorial macam pada GDB, tetapi sedar bahawa ini adalah permulaan daripada lihat alat yang akan benar-benar membantu anda menyelesaikan masalah begitu banyak lebih berkesan. Apa yang kita akhirnya akan lakukan pada hari Rabu yang mula mengupas kembali beberapa lapisan dan mengeluarkan beberapa roda latihan. Itulah rentetan perkara yang dipanggil kita telah menggunakan untuk beberapa waktu, kita akan perlahan-lahan mengambil yang jauh daripada anda dan mula bercakap tentang sesuatu yang lebih esoterically dikenali sebagai char *, tetapi kita akan berbuat baik ini dan perlahan-lahan pada mulanya, walaupun petunjuk, kerana mereka dipanggil, boleh melakukan beberapa perkara yang sangat buruk jika disalahgunakan, dengan melihat pada claymation sedikit daripada rakan kami Nick Parlante dari Stanford University, seorang profesor dalam komputer sains yang meletakkan bersama-sama pralihat ini daripada apa yang akan datang Rabu ini. 

[VIDEO MAIN SEMULA] -Hey, Binky. Bangun. Ia adalah masa untuk pointer menyeronokkan. 

-Apa Itu? Belajar mengenai petunjuk? Oh, goody! [VIDEO AKHIR MAIN SEMULA] SPEAKER 1: Yang menanti anda pada hari Rabu. Kami akan melihat anda kemudian. [VIDEO MAIN SEMULA] -Dan Sekarang, Pemikiran Deep, oleh Daven Farnham. 

-Mengapa kita belajar C? Mengapa tidak + A? 

[Ketawa] 

[VIDEO AKHIR MAIN SEMULA]