SNOW logo
  • 로그인 회원가입 도움말 ENGLISH
CS50 / 3주차: 월요일 (CS50 / Week 3: Monday)
[정규강의] 컴퓨터 과학 개론 (CS50) (CS50 ) 6강/총19강
메일보내기
트위터로 보내기
페이스북으로 보내기
북마크
소스복사
강의정보한글스크립트원문스크립트자막

강의소개 

비트, 이진수, ASCII, 프로그래밍, 알고리즘, 스크래치, 구문, 부울대수표현, 조건문, 루프, 변수, 스레드, 이벤트 입문. 더 많은 것은 http://cs50.tv에 있습니다.
님이 한글스크립트를 등록 해 주셨습니다.

펼쳐보기

작성참여하기  히스토리

프린트

*  
님이 등록 해 주셨습니다.
CS 50에 다시 돌아온 것을 환영합니다! 이번이 세 번째 주입니다. 그리고 지난 가을에 마지막 평가에서 한 학생으로부터 우리가 얻을 수 있었던 코멘트의 의미는 그들이 어떻게 명백하게 수업에 일찍 올 수 있도록 유인 되어 지는가에 관한 것이었습니다. 간단하게 그 이유를 말하자면 우리는 거의 매 번의 수업을 조금은 어리석은 무언가와 함께 시작하기 때문입니다. 그래서 저는 우리가 2분을 일찍 시작해야겠다고 마음먹었습니다. 그렇게 함으로써 우리는 그 2분 가량의 시간 동안 동기부여를 할 수 있게 될 것이라고 생각하였습니다. 물론 이것은 문제 번호 2번과 관련이 되어있는데요, 그게 어떠한 것인가 하면 여러분이 해커 편집에 도전을 하며 여러분은 암호를 구현합니다. 하지만 그 역으로 보면 실제로 해독은 알려져 있는 사람들의 비밀번호입니다. 그래서 이 것을 가지고, 저는 여러분에게 이러한 아마도 유명한 클립을 제공하겠습니다.  
 
(클립 영상) 
- 무슨 일이 일어나고 있는 거야! 내 딸에게 무슨 짓을 하고 있는 거지?  
- 제가 재기 넘치는 젊은 성형 외과 의사인 필름 스로트킨 박사를 소개하도록 해 주십시오. 이 박사는 베버리 힐스와 전 세계 전체에서 가장 훌륭한 코 수술 담당 의사입니다. 공주 마마. 
- 코 수술? 난 도무지 이해를 못 하겠어! 그녀는 이미 코 수술을 받았다고. 그것은 그녀가 16세 때 받은 달콤한 선물이었지. 
- 아니, 당신이 생각하는 그런 것이 아닙니다. 당신이 생각하는 것보다 훨씬 더, 훨씬 더 안 좋은 거에요. 만약에 당신이 나에게 그 조합을 알려주지 않는다면 (안 들리게) 박사 슬로트킨이 그녀의 예전 코를 당신의 딸에게 돌려줄 것이에요!  
- 아, 안 돼! 그거 어디서 났어요? 
- 알았어 좋아, 내가 말해주지, 말해줄게. 
- 안 돼 아빠! 안 돼, 그러면 안돼요! 
- 그래 네가 맞아, 내 사랑하는 딸아. 나는 너의 새로운 코가 그리울 거야, 하지만 난 그에게 무슨 일이 있어도 그 조합을 말할 수 없어. 
- 아주 좋아요. 슬로트킨 박사. 최대한 대충 해주세요. 
- 네, 저의 기쁨입니다. 
- 안 돼! 잠깐, 잠깐! 내가 말 할게. 내가 말 한다고! 
- 난 그게 제대로 작동할 줄 알았습니다. 좋아요, 저에게 알려 주시죠. 
- 조합은 1이지. 하나. 하나. 둘. 둘. 둘. 셋. 셋. 셋. 네. 네. 네. 다섯. 다섯. 다섯. 따라서 조합은 하나, 둘, 셋, 넷, 다섯이지. 
- 그건 내가 내 인생에서 들어 본 가장 멍청한 조합이에요. 그건 정말 바보 같은 조합이라고 말 할 수 있어요! 
- 감사합니다, 공주 마마. 
- 당신은 무슨 짓을 한 거야? 
- 나는 꺼져 (안 들리게) –. 
- 아니, 당신은 하지 않았어요. 당신은 전체 영화를 해제하지 않습니다. 
- 나는 잘못 버튼을 눌러야만 합니다. 
- 그것을 다시 넣어 줘, 다시 영화를 넣어. 그 일이 해결 되어야 돼. 우리가 돌아 왔다! 우리는 조합이 있습니다. 
- 뭐? 
- 우리는 당신과 함께 끝납니다. 골프 코스로 이동하여 퍼팅에 작동합니다. 
- 아놀드, 가자. 그레첸, 이리와. 물론 당신도 알다시피 나는 여전히 당신에게 청구 할 것이요. 
- 그녀는 훌륭한 투구를 제공할 겁니다. 
- 그거 제대로 작동 하나요? 키는 어디 있지? 
- 선생님, 그거 작동 합니다. 우리가 조합을 사용할 수 있습니다. 
- 좋아요. 이제 우리는 공장에서 신선한 공기의 모든 마지막 숨을 취할 수 있겠군요. (안 들리게) 조합은 무엇입니까?  
- 하나, 둘, 셋, 넷, 다섯. 
- 하나, 둘, 셋, 넷, 다섯? 
- 예. 
- 그거 정말 놀라워요. 내 수하물에 동일한 조합을 가지고 있어요! 즉시 출발을 위해, 우주 볼 하나를 준비합시다. 
- 예. 선생님. 
- 그리고 내 수화물의 조합을 변경하세요. 
 
좋습니다. 정말 그것보다 멍청할 수는 없습니다. 자 그러니까 이것이 CS 50입니다. 우리는 암호화, 궁극적으로 문제 세트 2번의 문제 도메인을 소개하는 것이었다는 동기 부여를 보고 지난 주에 중단하였습니다. 그러나 그것보다 더, 그것은 이러한 현실을 더 분명하게 만들어 줍니다. 만약 여러분이 이미 P 세트 2를 장착하였다면, 또는 이번 주에 곧 그렇게 할 예정이라면, 궁극적인 것은 공평하게 흥미로운 아이디어라든지 평범한 문단을 갖는다든지, 텍스트를 변환하거나 그리고 일반적으로 유용한 어떤 것을 하는 것, 정보를 암호화 하는 것, 그것은 정말로 어떠한 정말 정말 간단한 것을 몇 가지로 줄여 줄 것입니다. 여러분은 평범한 문단에서 찾게 될 것입니다. 그 문단은 단지 문자열과 문자의 배열인데 여러분을 문자 정렬로부터 돌아 보게 하는 호출의 문제입니다. 음, 텍스트를 암호화 한 후, 정말 그냥 문자열의 길이에 대한 0을 동일한 해당 배열을 통해 반복 한 다음 문자 각각의 조작에 대한 어떤 일을 통해 줄일 예정입니다. 아마 조금 전 보았던 왕의 경우에는, 일부 추가의 경우입니다. 그러나 거기에는 문제가 있습니다. 그래서 당신이 텍스트와 견적 인용을 끝 맺은 장소의 일부 번호로 문자의 각을 회전하여 이를 통한 알고리즘을 이용합니다. 그리고 부패 13 (가정 철자)의 비밀 회전 값이 소위 말하는 키가 13이었을 경우는 매우 구체적인 예입니다. 그러나 우리는 이것을 일반화 할 수 있습니다. 그것은 0에서 무한대까지에 어떤 것이든 될 수 있습니다. 하지만 그 것들 중 몇은 물론, 26을 예로 들어보자면 실제로 몇 가지 유틸리티를 가지게 됩니다. 여러분은 만약 이 시저 암호로 암호화 된 경우, 어떻게 다른 사람의 비밀번호를 알아낼 것이며, 균열은 어떻게 해야 할까요? 여러분에게 제가 텍스트 문자열을 주면, 이것은 말이 안 되는 것처럼 보입니다. 왜냐하면 그것은 부패 13으로 암호화 되어있고, 한 번 된 것이지 두 번 된 것이 아니기 때문입니다. 여러분은 어떻게 하겠습니까? 
(들리지 않는 청중의 코멘트) 
그건 뭘까요? 자, 좋습니다. 그러니까 자주 나오는 분석에서는, 멋지게 말하는 방법으로는, 음. 거기에는 다른 문자보다 더 많은 인기가 있는 알파벳의 일부 문자가 있습니다. 만약 여러분이 행운의 바퀴를 본 적이 있다면, 여러분은 이 것에 대하여 대부분의 참가자가 잘 알아챌 수 있을 것입니다. 그래서 아마 여러분은 암호문에서 가장 자주 등장하는 글자의 모양을 알아채게 될 것입니다. 알파벳 Q, 흠, 실제로 Q는 정말 많이 나타납니다. 그렇지만 잠시만요. 이건 지금까지 암호화 되어 왔어요. 이 Q 는 아마도 더 일반적인 글자인 음 아마도 E를 암호화하여 나온 결과입니다. 그 결과로 Q 가 발생한 것입니다. 그럼 여러분은 아마 비밀 키로 어떤 추론을 만들어 어떤 것을 반대로 엔지니어링 할 수 있을 겁니다. 또는 심지어 여러분이 그렇게 똑똑하지 않더라도, 그리고 여러분이 지금까지 한 번도 이 용어 주파수 분석에 대해 들어본 적이 없더라도 그것은 최소한 카이사르로 암호화 된, 여러분도 알다시피, 또 다른 접근 방법, 올바른 접근 방법, 이러한 경우에도 마찬가지입니다. 맞습니까? 
(들리지 않는 청중의 코멘트) 
네, 좋아요. 우리가 카이사르에 대해 얘기하는 경우 사용될 수 있는 글자 수는 겨우 26개의 키입니다. 그래요, 그럼 좀 지루한 이야기가 될 수도 있겠지만, 단지 가능한 모든 키를 시도한다고 해도 그 시간이 영원히 걸리지는 않을 것입니다. 그리고 사실, 이 암호화 된 전체 문자 또는 단락이든 뭐든 간에, 특히 전체 메시지인 경우에는 가능한 모든 키를 시도 할 필요가 없을 것입니다. 이 문장처럼 보이는 경우, 처음 몇 글자를 시도 해보고, 영어 팝업을 표시하거나, 어쩌면 프랑스어 또는 스페인어 또는 A에서부터 Z를 통해 표시 할 수 있는 작업이 시작되면 만약 그것이 단어처럼 보이는 경우, 또는 만약 그것이 문장처럼 보이는 경우, 여러분은 열쇠를 발견한 것입니다. 따라서 카이사르는 그렇게 강하지 않고, 아마 예전에는 사용되었다는 것이 사실 이지만, 이후에 확실히 개선 되어 졌습니다. 왜냐하면 심지어 우리는 종이와 연필의 속도로 우리는 카이사르의 암호를 깰 수 있기 때문입니다. 음, Visionaire [가정 철자], 이 암호를 보세요. 이 건 몇 년을 따라 이후에 온 것인데 정교함을 위한 약간의 모습이 보입니다. 이 곳의 일부 번호로 알파벳 문자를 회전하기 때문에, 카이사르의 접근 방식을 취하고 있지만, 장소의 다른 번호로 다른 문자를 회전하게 됩니다. 그 대신 일반 텍스트의 모든 단일 문자를 암호화하는 K, 그 키, 그 숫자 키를 사용하는데 그래서 각 연속 문자에 대해 다른 키를 사용하는 것입니다. 이제 영원히 계속되지 않을 것입니다. 일반적으로 키의 고정 번호를 선택하고 방금 키의 고정 번호를 지정 해야 하는 경우에는 실제로, 여러분은 우리가 키워드라고 부르는 것을 선택합니다. 따라서 foobar 같은 것 말이죠. 자 이제 다른 측변에서 보면, 만약에 여러분이 왜 내가 계속적으로 fu와 bar 그리고 모든 Baz와 모든 이러한 변수에 대한 이상한 이름에 의존하는지 궁금해 한다면, 여러분은 이 단지 바보 같은 컴퓨터 과학과, 바보 같은 프로그래밍에 대한 것, 컨벤션을 찾게 될 것입니다. 여러분이 토론을 위해 임의의 변수를 골라낼 필요가 있을 때마다, fu는 전형적으로 어떤 하나의 첫 번째 본능입니다. Bar, 그 다음에 따라오는 것인데, 다음은 ucks (소리 나는대로), 그리고 그 다음은 그 후에 오는 바보 같은 사람들의 전체 무리가 있습니다. 그럼 foobar은 우리가 사용할 수 있는 임의의 단어의 원추형, 예를 들어 일종의 그것 입니다. 하지만 우리는 이 경우, foobar의 각 문자가 서로 다른 키를 나타내고 있다는 것을 깨닫게 될 수 있습니다. 그래서 F는 하나의 키를 나타냅니다. 그리고 O는 다른 키를 나타냅니다. O는 동일함을 나타내기 위해 발생합니다. B는 다른 키이기 때문에, 즉 여러분의 키워드를 여러분은 일반 텍스트의 아래 줄로, 그리고 여러분은 그 열쇠에 의해 암시되는 곳의 번호로 일반 텍스트 문자의 각을 회전 할 수 있습니다. 따라서 그렇다면, F는 무엇을 나타냅니까? 음, 어디 보자. 우리가 보통 때처럼 제로로 카운트를 시작 한다면, A는 제로 이므로 다음이 B, C, D, E, F가 오겠지요. 그럼 F는 숫자 키 5를 나타냅니다. 그러니까 이게 무슨 뜻 이죠? 음, 만약에 저의 일반적인 텍스트 P가 안녕하세요 라는 세계를 나타낸다면, 그리고 나는 H를 F로 바꾸어야 한다면, 그것은 5개의 장소를 통해 일어납니다. 즉 H, I, J, K, L, M이 나타납니다. 좋아요. 그래서 암호 텍스트 문자의 결과는 M이고, 그럼 제가 사용하는 동일한 과정을 다른 키를 사용해서 반복해보죠. 지금 그렇다면 아마도, 제가 일반 텍스트를 암호화 할 메시지는 희망적으로 키보다 더 멀리 있을 것입니다. 만약에 여러분이 실제 메시지보다 좀 더 긴 키를 기억하고 있는 경우라면 여러분은 아마도 거기에서 효율성을 잃게 될 것입니다. 자, foobar는 여섯 글자입니다. 그렇다면 우리의 일반 텍스트는 여섯 글자 이상입니까? 어쩌죠 글쎄, 여러분은 다시, 다시, 또 다시 반복을 시작할 것입니다. 그렇다면 그럼 그냥 잠깐 물어 보겠습니다. 카이사르에게 26개의 키가 있는 경우, 반면에 Visionaire 여기에는 얼마나 많은 수의 키가 있습니까? 좀 더 자신감을 가지고 크게 말해보세요. 좋아요, 무한히 많은, 확실합니다. 우리는 어떤 길이의 가능한 모든 키워드라도 선택할 수 있기 때문입니다. 그러나 이 것을 일반화 해봅시다. 우리가 Visionaire에 대한 키워드에 N 문자가 있다고 가정 해 보겠습니다. 얼마나 많은 마지막 문자 키 단어가 Visionaire에 대하여 가능합니까? 맞아요, 그러니까 끝까지 26개이죠. 그럼, 모든 경우에 - 여러분이 N 문자 키 단어 그러니까 이 경우에는 6 개, 그리고 그 문자의 각각을 가지고 있다면 A부터 Z까지 어떠한 26개의 수라도 선택할 수 있습니다. 여러분은 그 26개의 선택 곱하기 26개의 선택, 곱하기 26개의 선택을 갖게 되는 거에요. 따라서 그것은 N에 대한 26개입니다. 그리고 다음으로 제가 여섯 글자이라는 제약 조건을 완화시키면, 그리고 내가 ehh라고 말하면, 그 키는 문자들 중 어떠한 수도 가능합니다. 여러분이 가지고 있는 것보다 큰 것도 가능하다는 말이죠. 여러분은 2에 대하여 26개, 더하기 3에 대한 26개, 더하기 4에 대한 26개, 따라서 짧게 말하자면 그 키의 공간은 무척 커지게 되는 것입니다. 이제 궁극적으로 여러분이 여전히 몇 가지 방법에 의해 Visionaire단어의 암호를 깰 수 있습니다. 여러분이 지적인 조작을 할 수 있을 것입니다. 또 여러분은 패턴을 찾을 수 있을 것입니다. 예를 들어, 여러분은 주파수 분석을 할 수 있게 되는 것입니다. 일부 상당히 복잡한 추론을 하거나, 가능한 모든 키를 시도할 수도 있습니다. 여러분이 하는 모든 시도가 다시 감각을 멈추게 한 후 다음에 오는 모든 글자가 하나의 키로 시작되며, 모든 두 개의 문자 키, 세 개의 문자 키를 사용해보십시오. 그리고 그 알고리즘은 그러나 결국 적어도 이론적으로는 작동하게 됩니다. 여러분은 주변 대기 시간이 충분히 주어집니다. 불행하게도, 이 일은 여러분 자신의 책상 또는 노트북 아래에 있는 전원의 2 기가 헤르츠에 있을 때 여러분은 매우 신속하게 키의 많은 것을 통해 할 수 있으며, 실제로 DES, 이 DES이라는 알고리즘이 있습니다. 이것은 알고리즘인데 일반적으로 자신의 암호를 암호화하는 데 있어서 여전히 리눅스 나 UNIX, 또는 Mac OS 시스템, 그리고 오늘날에 사용되는 함수에 사용되는 것들이 있습니다. 그래서 지금, 아마도 자신의 컴퓨터에, 확실히 좋은 FAS Harvard.edu에 사용자 이름과 암호가 있는데, 비밀번호는 다행히 암호화 방식으로 저장되어 있습니다. 이것에 대한 이유는, 예를 들어, 사용자는 여러분이 그것을 잊어 버린 경우에 시스템이 암호화 되어 저장되기 때문에, 여러분의 비밀번호를 알려줄 수 없어 하듯이 그들에게 요구하게 됩니다. 이 알고리즘은 그러니까 이 기능은 몇 년의 Visionaire 후, DES는 얼마 동안 사용되었다고 하지만, 더 최근의 현대 시대에는 이것 때문에 특정 알고리즘이 무언가를 암호화하는 데 사용되는 비트의 수가 DES 72 백만의 사 제곱 정도의 가능한 키가 있습니다. 이제 우리는 구체적인 내용은 다루지 않을 것입니다. 이 것의 상대적인 복잡성의 인기와 일반적인 텍스트 책에 작은 조각을 넣습니다. Visionaire는 매우 간단합니다. 여러분이 종이와 연필로 수행 할 수 있습니다. 화살표 순서도의 일반적 의미로는, DES는 컴퓨터나 계산기로 시작합니다. 그렇지만 컴퓨터가 매우 빠르게 DES 암호화 텍스트를 계산 할 수도 있습니다. 불행하게도, 너무 빨리 해버리죠. 여러분은 DES 함께 무엇인가를 암호화하면 현실이 됩니다. 그래서 누군가가 자신에게 충분한 시간과 충분한 CPU주기가 주어져 있는 경우에는, 여러분도 알다시피, 그들은 비밀번호를 해킹 할 수 있습니다. 그리고 그것에 대한 문제가 무엇 이냐 하면, 2의 해커 버전은 모든 것에 대해 이러한 설정을 정확히 한다는 사실입니다. 이제 이 어떤 임의의 대학의 시스템에서 암호의 맥락에서 보면 어쩌면 재미있습니다. 여러분도 아시다시피, 임의의 사람이 자신의 무릎에 노트북과 CS 50 학생들이 DES 같은 것으로 암호화 된 정보를 해독 할 수 있는지에 대한 것은 더 많이 꺼림칙한 일입니다. DES는 매우 더 이상 안전하지 않습니다. 56 비트의 키는 한 번의 사용으로 더 안전합니다. 따라서 거기에는 어떠한 변형이 있습니다. 사실은 말하자면, 누군가가 방금 DES를 사용하겠다는 좋은 아이디어를 내놓았다 하더라도 그렇지만 DES를 세 번 실행 하는 것은 DES 또는 3 DES를 건드리는 것입니다. 그리고 그 사실 때문에 조금 더 안전하지 않습니다. 그래서 우리 세계는 더 정교한 알고리즘을 마련해 놓았습니다. 여러분이 먹는, 또는 여러분의 컴퓨터 과학은 120의 시간이 있고 암호화 클래스가 있으며, 몇 몇의 대학원 정도 수준의 사람들이 있다면, 정말 흥미롭습니다. 여기서 재미있는 건 오늘날의 암호화 메커니즘의 보안이 궁극적으로 많은 가정에 가져다 줄 수 있습니다. 가정에 이에 대하여 안전한 것이라고 말 할 수 있습니다. 즉, 이 RSA이라는 알고리즘이 있으며 이러한 다양한 웹 사이트에서 나와 볼 수도 있고, 여러분은 전에 알고리즘에 대하여 들어 본 적이 있을 것입니다. 웹 사이트에서 안전하게 브라우저와 통신 할 수 있게 하는 정말 훌륭한 방식은 기본적인 것이라고 요약 할 수 있겠습니다. 하지만 그건 단지 특별한 경우입니다. 여러분은 훨씬 더 많은 흥미로운 목적을 위해 사용할 수 있습니다. 말하자면 ATM 기계, 은행 거래 등 흥미로운 내용을 아주 많이 사용할 수 있는 것이죠. 그러나 궁극적으로는 이 알고리즘이 실제로 작동 여부에 상관없이 긴, 요즘엔 매우 짧은 길이인 56 비트, 또는 긴 128 비트 또는 1024 비트 아르 키를 사용하고 있는지 RSA의 보안의 여부에 달려있습니다. 인류는 고려해 보면 많은 양의 빠른 방법을 구축 할 수 있습니다. 그러니까 다시 길고도 짧은 이야기인 이 알고리즘은 인류를 가정에 RSA 종기라고 하고, 자신의 컴퓨터에는 두 개의 큰 소수의 숫자로 아주 빠르게, 또 아주 큰 번호와 요소를 가져오게 할 수 없습니다. 그럼 여러분은 정보를 암호화 할 수 있는 그리고 그 것 및 RSA와 같은 알고리즘을 사용하려는 경우, 두 개의 매우 큰 소수의 숫자를, 다른 방법을 이용하여 그 둘을 함께 곱하는데 이것은 어려운 게 아닙니다. 심지어 소수의 숫자를 생성하는 것도 어렵지는 않습니다. 심지어 정말 큰 숫자라도 그것들을 곱하는 것은 어렵지 않습니다. 그러나 여러분이 해야 할 모든 일들이 컴퓨터로 정말 큰 숫자를 다루는 것이고 그 다음에 ‘이봐’ 라고 말한 뒤 그것들이 무엇인지 나에게 말해봐 라고 하는 것이라면 그 과정을 취소하기가 훨씬 더 어렵습니다. 우리는 지금까지, 계산에 대하여 비교적 신속하게 마련되지 않았습니다. 우리가 살아 생전에 이보다 탁 트인 일반화를 만들기 위해, 예를 들어, 더 많은 단위를 취하게 될 것입니다. 그렇지만 키는 밤에 개선하거나 일부는 너무 세계 자체가 지금 우리의 돈을 맡기는 것을 알고리즘의 보안 및 물건의 전체 무리를 깰 수 있는 흥미로운 기회를 많이 가지고 있다는 것을 의도하지 않습니다. 여러분들에게 더 큰 키가 어떻게 생겼는지에 대한 감각을 제공합니다. 의도적으로 오히려 작고, 그래서 이 알파벳 문자와 숫자로 표현 하고자 하는 것은 정말 큰 숫자입니다. 단지 효율성의 향상을 위해서 그 키 하나가 RS A와 같은 알고리즘과 함께 사용할 수 있는 1에서 26의 숫자보다 훨씬 더 크다는 것입니다. 이 foobar 같은 단어보다 훨씬 더 큰 것입니다. 오늘날 실제로 보안의 종류에 따라서 사용됩니다. 그리고 따라서 그것은 우리가 오늘날 선택하게 되는 시기입니다. 그래서 우리는 우리가minutia의 일부라도 마지막으로 문법과 C 프로그래밍에 대해 얘기한 지난 2 주 동안 많은 시간을 소비한 것이고, 루프에 대한 어떤 것들과 언제 동안 루프가 존재하며, 여러분이 아직까지 그 구문의 세부적인 것까지 편안해 지도록 연습할 수도 있습니다. 우리는 드디어 이제 강의와 이러한 과정을 통해 여러분은 실제로 더 효과적으로 생각하기 시작하였고, 방법에 대한 약간 더 높은 수준에서 이야기를 시작 할 수 있게 되었습니다. 카탈로그 청구는 보다 효율적으로 문제를 해결 할 수 있는 방법 등 다른 약속입니다. 그리고 우리는 정말 큰 전화 번호부를 시각적으로 흥미로운 예를 들어 이런 종류와 함께 이 코스를 시작하였고 제가 훨씬 더 빨리 말한 것 보다 마이크 스미스를 찾을 수 있게 되었습니다. A와 B와 그리고 그 다음 C를 통해 시작함으로써. 제가 이러한 나눔의 문제에 대한 접근을 절반으로 하였고 그것의 단지 절반만 결론지었기 때문입니다. 그리고 저는 깨달았습니다. 오, 만약에 내가 아는 마이크가 오른손 잡이의 전화번호부에 있다면 저를 이것을 다시 할 수 있게 해주세요. 그리고 문제를 반복해서 분할하게 하세요. 그리고 만약 그 전화 번호부 그리고 그것이 1,000 페이지나 1024 페이지라면, 몇 번 내가 실제로 마이크 스미스 같은 사람을 찾아 반으로 그 문제를 분할 해야 하는 것입니까. 열 번, 그렇죠? 여러분은 1024 페이지를 가지고 있고, 여러분은 여러분의 머리로 또는 종이에 계산을 할 경우, 반은 열 번에서 해당 번호를 나눌 수 있습니다. 자, 그럼 이제 여러분의 마지막 페이지에 도착하면 끝 부분에 흥미로운 반올림 문제가 있습니다. 그러나 1024 페이지 대신 열 번입니다. 우리가 이번 주에 말한 것처럼 전화 번호부가 1000페이지가 아니라 4,000,000,000 페이지라고 가정합시다. 정말 전화 번호부 지옥이네요. 수많은 이름이 그 안에 있습니다. 그러나 내가 실제로 보아야 하는 페이지는 몇 페이지 인가요. 내가 4,000,000,000페이지의 전화 번호부의 절반에서 몇 번 보아야 하나요. 32번입니다. 이유가 뭐죠? 글쎄, 여러분은 40 억 걸릴 것을 약 32 시간에 나눌 수 있습니다. 그리고 이 기본 장치와 알고리즘에 삽입된 지능은 단지 소량으로 수행 할 수 있는 힘으로 지능적으로 실제 설계 알고리즘의 힘으로 말합니다. 제가 지금 당장 알고 있는 전화 번호부를 검색한다면, 여러분은 확실히 최근에 구현하는 방법을 통해 분열과 정복을 문법과 C의 기능을 사용하여 전화 번호부 검색을 구현할 수 있고 지금까지 가장 간단한 방법으로 여러분은 루프에 대한 쓰기 같은 것을 하게 됩니다. 나는 제로를 얻었습니다. 40억보다 작거나 같은 그리고 그 다음 에는 그저 40억까지 체크를 해보면 됩니다. 누군가가 현재의 여부에서 있는지 없는지. 또는 현재 정돈된 것, 또는 여러분이 실제로 코딩 한 것에서 말이죠. 여러분은 몇 분의 시간으로 그것을 구현할 수 있습니다. 그러나 문제는 실행하는 데 시간이 걸릴 겁니다. 대조적으로, 조금 더 넣어보면 알고리즘 자체가 훨씬 더 빠르게 실행됩니다. 그래서 우리는 일어 서서 다시 이 일에 탐닉하지 않을 것입니다. 하지만, 이 같은 생각은 같은 것에 대한 예시입니다. 첫 날은 모든 사람들이 서있을 것입니다. 여러분은 누군가와 짝을 지어 있을 것입니다. 다음에는 그 중 절반은 앉고, 그리고 또 그 중 절반이 앉고 또 다음 절반이 앉습니다. 자 이제, 좀 더 흔한 경우를 생각해 봅시다. 2, 4, 6, 8, 10, 12로 가봅시다. 그러나 이론에 있어 사회적으로 안 맞는 건 없습니다. 이 연산에는 문제가 없습니다. 우리는 할 수 있을 것이고 여러분들은 이 방에 있는 사람들을 I보다 빨리 셀 수 있을 것입니다. 왜냐하면 내가 1, 2, 3 이렇게 하고 모든 CPU 주기 사이클과 세고 있으며, 여러분은 저와 반대로 모든 시계 방향의 반대로 CPU 주기 사이클을 세게 됩니다. 여러분 중 절반은 앉으세요. 여러분은 50% 그러니까 절반을 가져가게 됩니다. 그 반은 일단 방 밖으로 나갑니다. 제가 바깥으로 하나를 갖게 될 때. 따라서 이것은 매우 의미가 있습니다. 따라서 이 것은 훌륭한 방법입니다. 저는 이것을 엑셀로 만들겠습니다. 그럼 다음과 같은 아이디어를 묘사 할 수 있습니다. 따라서 X 축에 여기 일반적으로 문제의 크기를 참조 할 것입니다. 이 번호 N은 일반적으로 어떠한 문제에 대한 숫자를 나타내는데 쓰이는 숫자입니다. 예를 들어 전화 번호부에 몇 페이지가 있는지 나타낼 수 있습니다. 이를 N이라고 부르기로 합시다. 샌더스에 얼마나 많은 학생들이 있을까요? 이를 N이라고 부기로 합시다. 자 이제 나는 0부터 130 까지의 수를 가지고 있습니다. 그리고 다음으로 Y축에는 N에 대한 T라고 부르는 것이 존재합니다. 한 알고리즘이 즉 사이즈 N의 인풋을 가지고 있는 알고리즘이 작동하는데 걸리는 시간을 의미합니다. 따라서 이것은 그저 일반적인 작동 시간을 묘사하는 방법입니다. 알고리즘이 작동하는데 얼만큼의 시간이 소요되는지, 그리고 우리가 시간을 통해 무엇을 의미하게 되는지 말입니다. 단계들 또는 초, 분, 무엇이든지 우리는 그 통계에 동의하면 됩니다. 그리고 이 모두 다른 선들은 다른 작동 시간들을 나타냅니다. 따라서 왼쪽 꼭대기에 있는 것은 우리는 약간의 레전드를 그곳에 가지고 있게 됩니다. 이것은 일종의 작게 보는 것을 의미하는데요, 그렇지만 우리는 여기에 세 가지 종류의 그래프를 가지고 있습니다. 하나는 위로 올라갑니다. 따라서 왼손 쪽에는 우리는 매우 가파른 곡선을 가지게 되는 것이죠. 그렇지만 이것은 선입니다. 이것은 선 그래프에요. 그리고 이것은 A라는 인풋이 N개의 단계를 거쳐 작동하는 알고리즘을 나타내줍니다. 그리고 그것은 1, 2, 3, 그리고 이 선형 알고리즘을 세는 작동시간의 대표적인 것입니다. 그러나 우리는 위크 제로에서 우리가 더 잘 할 수 있다는 것을 깨달았습니다. 맞죠? 우리는 실제로 그것들을 더 빠르게 할 수 있습니다. 따라서 이 두 번째 그래프에서는 저쪽에 있는 두 번째 그래프요, 그 두 번째 선은 첫 번째 선보다 약간 오른쪽으로 치우쳐있는데, 그것은 내가 했던 2, 4, 6, 8의 결과가 될 것입니다. 그것은 실제로 두 배 빠릅니다. 이제 여러분의 대조적인 그래프를 봅시다. 즉 N에 대한 로그는 우리가 여러분의 알고리즘에서 그 날 묘사했듯이, 우리가 이 일반적인 나눔의 원리를 묘사했듯이 그렇게 작동합니다. 이것이 의미하는 것은 여러분의 알고리즘이 더 적은 시간이 걸려야 한다는 것입니다. 다시 말해서 그 방에 있는 더 많은 학생들이 몇 개의 단계 또는 얼만큼의 초, 몇 개의 요소 묶음 사이에서 여러분의 알고리즘과 선형 차트에 가까운 나의 알고리즘을 비교해 보았을 때 어떤 것이 더 적게 걸리는 지 비교합니다. 자 이제, 이건 뭘 의미하는 걸까요? 만약에 우리가 더한다면, 만약 한 명의 추가적인 학생이 이 방에 온다면 그것은 나에게 한 가지의 단계를 추가 해야 함을 의미합니다. 만약 한 명의 학생이 이 방에 추가적으로 오게 되면 그것은 여러분에게 라운딩 에러를 일으키게 됩니다. 왜냐하면 여러분은 하나의 추가적인 학생을 가정할 수 있기 때문입니다. 따라서 더 큰 것을 생각해봅시다. 점점 더 크게 해서 더 중요한 문제를 다뤄봅시다. 우리는 대략 2, 300명의 학생이 이 방에 있다고 가정합시다. 또 다른 200 또는 300명의 학생들이 이 방에 몇 분 뒤에 오게 됨을 가정합시다. 자, 이것은 나에게 두 배로 시간이 더 걸리게 만들 것입니다. 나는 이전에 N단계의 과정을 거쳤다면 이번에는 학생 수가 두 배가 됨으로써 2N단계의 과정을 필요로 하게 되는 것이죠. 자 이제 나와 대조적으로, 만약 200 또는 300명의 추가적인 학생들이 몇 분 후 이 방에 들어왔다고 가정했을 때 과연 몇 개의 단계 또는 과정의 시간이 여러분에게 추가적으로 필요하게 되겠습니까? 그냥 한 개이죠. 맞아요? 왜냐하면 그 첫 번째 반복에서 여러분의 알고리즘이 작동하기 때문에 같은 아이들은 곧바로 앉게 되는 것입니다. 그리고 그것은 이 문제에 대한 큰 점입니다. 내 알고리즘으로 계산하려면 많은 양의 단계가 증가 해야 하는 것과 반대로 말이죠. 그리고 기초적으로 반대되는 선형 그래프 사이의 어떤 것을 봅시다. 내 알고리즘과 같은 선형 그래프 말이에요. 그리고 로그 또는 적어도 수학적으로 더욱 흥미로운 점입니다. 또한 숫자가 압도하겠지만 그래도 일단 해봅시다. 구체적인 값을 이 곳에 넣어봅시다. 이것은 하나의 큰 차트인데 이 차트는 아주 특정한 기본 함수를 계산합니다. 그러므로 왼쪽에서는 그 세 번째 열, 여기 있죠. 그리고 내가 서 있는 오른쪽 위에는 이건 N입니다. 그래서 우리는 1, 2, 4, 8, 16을 가지게 되고 이것은 N에 대한 전체 묶음의 값입니다. 따라서 나의 알고리즘은 1, 2, 3, 4를 갖고 만약 우리가 백 만 명의 학생들이 이 방에 있고 또는 1,048,576명이라고 하였을 때 그것은 명백하게 나에게 1,048,576개의 단계를 필요로 하게 합니다. 그러나 나와 대조적으로 여러분의 스크롤이 왼쪽으로 갔을 경우, 그리고 여러분이 이것을 할 수 있다면 여러분도 알다시피 계산기와 또는 심지어 여러분의 머리로도 아마 그 같은 수의 학생들이 즉 백 만 명의 학생들이 샌더스에서 여러분에 의해 20개의 단계를 통해 세어지게 될 것 입니다. 그리고 따라서 시각적으로 이 그래프가 보여주듯이, 그리고 우리가 다시 이것을 방문할 것이고 여러분은 이것을 내가 소개하지 않은 다른 많은 알고리즘을 이용하여 다시 방문할 수 있습니다. 그것은 정확히 얼마나 이 요소들이 중요하고 잘 정돈된 알고리즘인지 보여줍니다. 그리고 우리는 더욱 축소 할 수도 있습니다. 여러분이 여기에 있는 이 세 가지의 다양한 그래프를 보면, 구체적으로 오늘 너무 재미는 없지만, 이 마지막 하나를 여기에서 확인할 수 있을 것입니다. 따라서 작긴 하지만 북쪽으로 큰 곡선은 지수 함수를 나타내는데 2부터 N이라고 불립니다. 2부터 N은 지수 함수입니다. 따라서 우리는 그것에 대해 일단 이야기를 할 것이고 나중에 만약 여러분이 다른 이론 수업을 CS에서 듣게 된다면 심지어 그냥 재미로라도 듣는다면, 또는 여러분이 CS를 부전공 하게 된다면 여러분은 그 매우 안 좋은 지수 알고리즘에 대해 배우게 될 것입니다. 왜냐하면 N이 증가함에 따라 그것들은 말도 안 되는 정도의 시간이 걸리기 때문입니다. 그러나 다시 우리가 배울 것에 대해 동기를 부여해보면, 오늘 우리는 암호화에 대해 배웠는데요. 우리가 큰 수들은 빨리 계산하기 어렵다고 말 할 때, 그건 무슨 소리냐 하면 필수적으로 그것은 큰 수를 요소화하는 것이 일반적으로 어떤 것을 낮추는 것인데, 그것은 지수적인 시간이 걸리게 됩니다. 선형이 아니고, 이차항도 아니고, 다항식도 아니고 말이죠. 만약에 여러분이 이 용어들을 다시 생각해본다면, 그래도 지수적입니다. 따라서 이러한 그래프는 매우 안 좋아요. 작동하는데 좋은 양의 시간이 걸립니다. 따라서 그렇다면 우리가 어떻게 알고리즘의 작동 시간을 묘사하기를 시작할 수 있을 까요? 맞아요? 그것은 일종의, 아 예를 들기는 굉장히 쉬워요. 어떤 것이 더 낫다고 말 해봐요. 왜 그것이 더 나은지, 그리고 그것에 필요한 단계에 대해 말해봐요. 그렇지만 우리는 일반화할 수 있습니다. 여러분은 여러분 자신의 코드 또는 여러분 자신의 프로그램을 보면서 시작하고 그러고 나서 이 알고리즘이 좋다고 말할 수 있습니다. 왜냐하면 그것은 이 만큼의 시간이 걸리고 또는 내가 지난 주에 쓴 시간이 일반적으로 어느 정도 걸렸는지 보기 때문입니다. 우리는 우리가 다른 언어로 작성한, 또는 다른 사람이 작성한, 서로에 대한 알고리즘을 비교하면서 시작할 수 있습니다. 음, 기본적으로 세 가지 구조가 있는데, 우리가 이 세 가지 구조를 통해 사용하기 시작합니다. 전문 용어의 세 가지 작은 조각이 있어요. 하나는 큰 O, 하나라고 합니다. 그리고 그 맨 위에 있는 사람입니다. 중간 남자는 세타라고 합니다. 그리고 바닥은 오메가입니다. 그리고 이러한 기호는 단지 일반적으로 알고리즘의 실행 시간을 표현하는 컴퓨터 과학 수학자에 의해 사용됩니다. 이제 이것은 무슨 뜻 이죠? 따라서 공식적으로, 그것은 이를 의미합니다. 그리고 당신이 수학적으로 속해 있음을 좋아하면 이 슬라이드가, 아이디어가 실제로 있기 때문에, 행에 있지만 오늘은 그들 몇 가지 상대적으로 간단한 아이디어로 줄일 수 있습니다. 당신이 최악의 경우에 N 개의 조치를 취하고 있는 알고리즘을 사용하고 있는 경우, 해당 알고리즘에 그런 말을 - 그래서 그 알고리즘은 N의 O입니다. 당신이 계산하려는 학생들의 시간을 선형 알고리즘의 시간을 실행하는 최악의 경우입니다. 그리고 이 쪽 측면으로는, 잔센과 마이크 생일 축하 합니다. 하지만 이 경우, 가장 좋은 경우에 알고리즘은 실제로 다음 오메가 표기법에 대한 이야기부터 잘 적은 단계를 수행 할 수 있습니다. 가장 좋은 경우에 얼마나 많은 단계가 N명의 학생들을 계산하기 위해 취하게 될까요? 이 것 때문에 지금 계산을 하려고 하는 학생들의 경우, 이 것이 정말 도움이 되지 않는 이유는 무엇입니까? 음, N입니다. 좋아요, 내가 모두 계산 해야 합니다. 가장 좋은 경우에서는? 제가 학생들을 모두 계산하고 싶다면, 그것은 여전히 N 단계를 받아 들여야 하는 것입니다. 그러나 임의로 다른 알고리즘을 가져 와 봅시다. 학생들이 방으로 왔다고 가정합시다. 난 그저 마이크라는 이름의 학생을 검색해서 찾고 싶습니다. 따라서 최악의 경우에, 얼마나 많은 단계들이 문을 파일로 마이크라는 이름의 학생을 찾기 위해 필요 하게 될까요. 좋아요, 따라서 N 단계입니다. 왜냐하면 최악의 경우에, 우리가 이번 학기 과정에서 갖게 된 마이크 또는 여러 명의 마이크들이 그저 단지 - 그냥 방으로 들어오는 마지막 사람이 되어야 발생합니다. 그냥 우연히. 그러나 가장 좋은 경우에는, 마이크 라인에 있는 것이 있을 수 있을까요? 먼저, 맞죠? 상식이죠. 그래서 가장 좋은 경우에 우리가 마이크를 검색하는, 마이크를 찾는 것에 대한 알고리즘은 가장 좋은 경우에 1 오메가에 하나의 단계를 필요로 합니다. 나는 질문을 해봅니다. 내가 바로 찾고 있는 해답은 떨어져 있습니다. 따라서 여러분이 N의 큰 O 도는 N의 오메가에 대한 각각의 알고리즘을 가지고 있을 때, 그래서 검색하는 것이 아니라 계산하는 것일 때, 그러면 여러분은 알고리즘이 N의 세타에 의해 묘사될 수 있다고 말할 수 있나요? 우리는 실행할 때 최악의 경우가 꼭대기에서 아래에 있는 시간을 실행하는 가장 좋은 케이스를 가지고 있고, 두 경우가 그냥 너무 동일하게 발생할 경우, 여러분은 알고리즘이 그 경우에까지 와서 어떤 수식의 세타에 적용해 그런 말을 할 수 있습니다. 좋아요, 그럼이 정확히 이건 무엇을 의미합니까? 따라서 전화 번호부의 경우, 또 다시 다시 전화 번호부를 찢고, 그리고 N 페이지를 가지고 있었던 전화 번호부에서 그 문제에 대해, 마이크 스미스를 찾거나 정말 사람을 찾는 실행 시간이 걸릴 때 얼마나 많은 단계가 최악의 경우 전화 번호부를 검색하면 됩니까? 내 알고리즘은 단지 첫 번째 페이지에서 시작하여 왼쪽에서 오른쪽으로 전화 번호부의 끝에 모든 방법을 이동하는 경우입니다. 좋아요, 그럼, N을 기록합니다. 그럼 한 가지가 구현 될 수 있으며, 이 전화 번호부의 선형 검색을 말할 수 있습니다. 하지만 우리는 더 잘할 수 있습니다. 내가 수행한 알고리즘에서 우리는 분열과 정복, 나눠서 최악의 실행 시간을 정복하는 것보다 지능적으로 비교하여 제로에서 수업을 시작하는 선형 알고리즘을 비교하려면 즉, 대신에 무엇입니까? 자, N 로그입니까? 우리는 최악의 경우 우리가 가는 것을 반복하고 우리가 마이크 스미스가 마지막으로 나열되어 한 페이지에 얻을 때까지 반 반으로 전화 번호부를 자르다가 유지해야 합니다. 그렇기 때문에 몇 번 우리는 자르고 할 수 있습니까? 이것이 우리가 로그라고 부르게 될 것입니다. 자, 전화 번호부는 알고리즘을 검색 시간을 실행하는 가장 좋은 경우는 어떻습니까? 그래요, 알았어요? 가장 좋은 경우 - 다시, 여러분은 알고리즘에 대해 이야기 할 때, 여러분은 일반적으로 입력에 대해 이야기 합니다. 우리는 마이크 스미스를 찾기 위한 알고리즘에 대해 이야기하지 않습니다. 우리는 사람을 찾기 위한 알고리즘에 대해 이야기 합니다. 음, 방금 일정한 시간에 선형 알고리즘 또는 로그를 궁극적으로 종기를 사용하는지에 대한 여부와 전화 번호부에 사람을 찾는 시간을 실행하는 최선의 경우가, 그렇죠? 여러분은 그냥 전화 번호부의 첫 페이지에 할 일이 애비게일 애덤스를 찾고 있기 때문이죠. 여러분은 다 했습니다. 여러분은 여러 번에 걸쳐 절반이라도 전화 번호부를 분할 할 필요가 없습니다. 그리고 우리는 한 단계가 걸리는지 두 단계가 걸리는지의 여부가 페이지에 남아 있기 때문에, 어쩌면 지금 페이지에 두 가지 조치를 취하고, 그 알고리즘 상수의 실행 시간을 알아볼게요. 그러나 그 단계는 단지 상수이며, 그래서 우리는 단지 일정한 시간을 일반화 할 수 있어요. 그러니까 이 요점이 뭡니까? 음, 우리는 이제 우리가 했던 것처럼 하는 것이 아니라 사과와 오렌지, 하지만 사과와 사과를 비교하는 것은 의미가 있습니다. 우리는 두 개의 다른 알고리즘, 선형 검색을 한 후 증식하여 전화 번호부에 적용하면 우리는 이제 하나의 실행 시간의 측면에서 나은 질적인 뭔가를 말 할 수 있습니다. 그리고 표기법은, 사람들이 정확히 사용하는 경향이 표기법으로 여기에 있습니다. 그냥 어디서든 볼 경우 일부의 전문 용어, 우리는 논의 일정 시간, 우리가 논의하는 로그 시간, 우리가 논의할 선형 시간을 말할 수 있습니다. 우리는 종종 이 실행 시간을 확인하고 N 로그 N을 봅니다. 솔직히 저는 12, 15년의 컴퓨터 과학 시간 동안 한 사람의 말 위에 선형을 들어 본 적이 없습니다. 하지만 그건 사실 정식 용어입니다. N 제곱, 우리는 오늘 또는 수요일에 그것을 다룰 것입니다. 그것은 이차식이라고 불립니다. 여러분이 N제곱 한 경우는 일반적으로, 그 다항식입니다. 그리고 이 N개의 요소는 그 어떤 것 보다 더 안 좋습니다. 하지만 알고리즘은 솔직히 분명한 바보라고 하지 않는 한 여러분은 그것을 표시하지 경향이 있습니다. 따라서 몇 몇의 발표가 있습니다. 오늘날 거의 코드를 이용 하지만 그럼에도 불구하고 거기입니다. 점심 식사는 잘 간 것 같기 때문에 그래서 우리는 응답에 의해 압도 되지요. 여러분의 급우 60명을 위한 바비큐 파티까지 마쳤습니다. 그래서 우리는 어떤 미래의 금요일 같은 또 다른 일을 해야 할 미래의 클래스에서 해당에 대한 자세한 것을 시도합니다. 만약 여러분이 아직 P 세트 0 의 해커 판에서 센서 보드를 반환하지 않은 경우, 이는 괜찮아요. 그저 그들에게 여기에 작은 구석에 있는 TFS 중 하나를 넘겨주세요. P 세트 2는 금요일에 문을 나갔습니다. 이를 통해 거리가 일요일에, 어제 촬영 한 그 비디오는 내일의 행으로 이동합니다. 근무 시간이 진행되었습니다, 그 것을 활용하고, 섹션은 이미 시작했습니다. 여러분의 할당 된 섹션은 그래서 여러분의 e메일로 통보되었을 것입니다. 여러분 중 어느 누군가가 어제 간 또는 섹션은 아마도 오늘 또는 내일이기 때문에 뿐만 아니라 그것을 활용 하지 않습니다. 그리고 우리는 또한 문제 설정을 하여 이번 금요일에 이 링크를 배포했습니다. 따라서 클릭하면 이런 식으로 보이는 작은 인터페이스에 로그인 됩니다. 지금 이렇게 게시판이 있습니다. 그리고 이 게시판은 몇 몇의 목적을 제공하기 위한 것입니다. 그 중 하나는, 그것은 우리가 한 번에 여러 사람들이 답변의 혜택에 대해 동일한 질문에 대답 할 수 있도록 한다는 것입니다. 그것은 여러분이 잠재적으로 우리가 다른 카테고리를 추가하고 크게 말하는 사람이 몇 가지 답변의 라인을 통과하지 않기 때문에 너무 오래, 서로의 질문에 대답 할 방향과 그리고 당신이 찾아내는 할 일은 해당 주에 할 수 있는 기회가 될 운명입니다. P 세트 2 게시판은, P 3을 설정하고, P 4를 설정하고 등등의 역할을 합니다. 그리고 게시판의 목적은 사람들이 누구나 내역을 볼 수 있는 것에 대한 답변을 들을 수 있을 거라 확신하고 있다는 질문을 하지만, 당신이 정말로 당신의 질문을 하면 우리에게 코드를 표시해야 한다고 판단되는 경우, 해당하는 CS. 50 에 도움을 계속 사용합니다. 하지만 처음에 로그인 할 때 무엇이 특히 편안함에 대한 더 중요한 것을 찾을 수 있습니다. 이 사용자 이름과 암호를 인증할 시간이 있지만, 우리는 학생들의 기본값으로 이름을 만들었습니다. 그래서 여러분은 여러분이 아닌 다른, 자신의 이름이나 뭔가 재미있는 다른 이름으로 변경할 수 있습니다. 즉 가명을 이용 할 수 있습니다. 그러나 게시판의 요점을 실현하려면, 익명은 당신이 두려워하는 것은 필요에 따라 직원 이외의 다른 사람들에게, 당신은 그런 질문을 해 주시기 바랍니다. 그것들을 게시 할 수 있도록 할 것 입니다. 그리고 더 많은 편안함을 주기 위해 모든 수단으로 그 방법으로 질문을 부탁 드립니다. 이제 우리 5 분 쉬었다 다시 합시다. 
 
[배경 잡음] 
네, 우리가 다시 왔습니다. 그래서 우리는 키 메모와 함께 다음을 수행하게 될 것입니다. 우리는 약간의 놀라움이 있는 뒤에 여기 여덟 개의 문을 갖추고 있습니다. 당신이 가만히 있으면 이 문 뒤에 무엇이 나타납니다. 하지만, 나는 무대에 올라 끊임없이 어색하게 자원 봉사자를 요청해야 합니다. 네? 이리 와요. 다시 말하지만, 당신은 순간에 영구적으로 즉시 권리를 로그인 해야 합니다. 어서 올라 와요. 당신의 이름은 무엇입니까? 
- 에드워드입니다. 
에드워드, 알았어요. 데이빗. 만나서 반가워요. 거기 팬 알았어요. 죄송합니다 - - (안 들리게) 놀라움을 만족시킵니다. 좋아요, 그럼 에드워드가 많은 게임 쇼처럼, 우리는 같은 문을 가질 수 있습니다. 그래서 우리는 신문이 조각 난 뒤에 여덟 개의 문을 갖추고 있습니다. 그래서 우리는 두 배열을 갖추고 있습니다. 그리고 괴짜 용어를 사용하기 시작할 거에요. 그래서 우리는 두 배열, 정수의 배열을 갖추고 있습니다. 각각의 크기는 8 입니다. 그리고 지금 매우 난처한 상황이 표시되어 있는 그냥 사람입니다. 위 배열에서 저는 3 번을 찾을 것입니다. 있는 목표지요. 그리고 우리의 관객이 배울 수 있도록 노력하겠습니다. 그렇게 하면 이 문제 해결에 대한 인간의 이동은 정확한 방법입니다. 당신이 맨 위 행에만 우리에게 3 번을 발견 할 경우 그러니까, 음. 숫자 2를 참조하세요. 아, 정말 잘 했어요. 번호 3을 참조하십시오. 좋아요, 그럼 당신이 찾을 경우, 당신이 번호 3을 발견하는 방법을 설명 할 수 있습니까? 
그냥 올라 갔습니다, 무작위로. 종이 조각. (안 들리게) 
좋아요, 그냥 기회라고 생각하므로, 그럼 바람에 낭패를 본 것이 아닙니다. 
맞아요. 체계적으로 가서 모든 종이를 확인합니다.  
그래요, 좋아요. 그래서 이렇게 빨리 찾아내어 내 데모를 망치고 이에 대해 먼저 감사합니다. 그래요, 하지만 우린 그럼에도 불구하고 질문을 물어 보겠습니다. 에드워드는 우리의 라벨을 비난 할 수 있는 것을 시도하는 알고리즘의 실행 시간은 얼마나 됩니까? 시간을 최고의 케이스를 통해 실행할 수 있습니다. 그것은 분명 하지만, 진정으로 최선의 경우는 하나이기 때문에 이 1 오메가에, 우리는 말합니다. 가장 좋은 경우에, 그 사람은 그냥 우연히 또는 좀 더 정교한 경험적으로, 오른쪽 번호를 직진하여 발생시킵니다. 그리고 최악의 경우에, 얼마나 번호 3을 찾기 위해 필요 했을까요? 좋아요, 8 이상. 그러니 다시 N이죠. 일반적으로 큰 O입니다. 우리는 하나의 큰 N의 O, 또는 오메가입니다. 알고리즘을 잘 갖추고 있습니다. 그래서 지금 제 손에 있는 질문은 우리가 그것보다 더 나은 일을 할 수 있는지에 대한 것입니다. 그럼 자 이제 봅시다. 우리가 어떻게 근본적으로 그 알고리즘에 대한 에드워드의 의견을 향상할 수 있을까요? 우리는 큰 O 사건보다 더 잘 할 수 있습니다. 큰 O 사건은 단지 8 일 때만 좋지만 그렇기 때문에 우리가 모르는 N에서는 정말 좋은 더 이상의, 논의된 N 처럼, 지금 4000000000입니다. 뭐라고요? 
(안 들리는 청중의 코멘트) 
좋아요, 그럼 우리는 이런 것들을 마우스 오른쪽으로 정렬할 수 있을까요? 우리가 전화 번호부의 위크 제로부터 이 시간을 보낸 장점이 있습니다. 다른 사람은 수직으로 또는 누구든지 우리가 특정 가정을 만들 수 있는 알파벳이 있도록 전화 번호부 정렬의 하드 작업을 완료했습니다. 나는 중간에 내려 가서 미스가 난 스미스 (Smiths), SS를 알고 NS에서 결국 같은 가정의 오른쪽에 있을 것입니다. 지금은 에드워드한테 그런 가정을 포기하지 않았고, 사실, 3은 여기에 있습니다. 아직 2가 여기입니다. 좀 이상하네요, 그리고, 어쩌면 이런 일이 그렇게 정렬되지 않은 것을 제안합니다. 그리고 사실, 8과 1이 있습니다. 그래서 맨 위 행은 사실에 정렬되지 않습니다. 지금 우리가 당신에게 8 자리 숫자의 하단에 배열되어 정렬된 사실에 있는 추가 가정을 어떻게 하단 배열에서 50 번째를 찾는지, 대답을 하지 않고 돌아 다니다가 수를 제공한다면. 하지만 다른 숫자들이 지금 정렬됩니다. 나는 171을 참조하십시오. 젠장! 좋아요. 좋아요, 아주 좋아요. 좋아요. 당신이 시간에 어떻게 한 것이죠? 
당신이 이 정렬된 말 때문에 글쎄요, 내가 그것 중 하나였어요. 가정 – 패턴이 있을 거에요. 그럼 하나 더 큰 숫자는 오른쪽이나 왼쪽에 있었을 것이지요. 그래서 저는 양쪽을 확인 했어요. 그래, 좋아요. 우리가 이 10 분을 소비 할 때 옆으로 이 데모는 작년보다 훨씬 더 효과적이었습니다. 당신이 정말 수업 오 분 전에 보드에 임의의 숫자를 기록했다면 몇 가지 트릭은, 아마도 발생했을 것입니다. 생각이 점점 나타납니다. 어떤 번호에 대해 시간과 생각을 많이 소비했기 때문에, 사실은, 약간 어색하지요. 그래서 당신은 훨씬 더 일을 잘 하고 있습니다. 그는 그것에 대해 좋은 경기였어요. 그래요, 그럼 하단 배열은 현재 정렬됩니다. 이에 대한 몇 가지 숫자를 한 번 보지요. 우수 사례의 현실에서, 분명 또 다시 반복이지만, 공식적으로 또는 점근적으로 우리는 큰 O와 오메가에 대해 얘기를 시작하는 시간을 가집니다. 우리는 점근적으로 얘기를 하게 되는데, 이 입력이 큽니다. 의미 있는 N이 큰지 어떤 것은 일반적으로 시간을 실행할 때 무슨 일이 일어 날까요? 따라서 최악의 경우에, 얼마나 오래 알고리즘은 실행된 것일까요? 좋아요, N입니다. 왜, 여기에 알고리즘을 무엇 때문이지요? 여러분은 우리가 다음에 할 수 없다는 걸 확인하지 않았습니다. 사실, 어디에 계속 있죠. 나한테 전화 번호 52을 찾아보세요. I 51를 참조하십시오. 그리고 I 61를 참조하십시오. 좋아요. 맨 위에 있습니다. 우리가 지금 알고 있기 때문에 좋아요, 그럼 거기서 멈추세요. 그러므로 이 알고리즘은 무엇입니까? 이제 우리는 조금 더 세게 밀어야 합니다. 그래서 그들이 숫자 정렬 된 가정이었습니다. 그래서 - 좋아요. 따라서 52 이후 새로운 50은 이미 아래에, 저는 그냥 같은 행에 갔습니다. 
그래, 좋아요. 그래서 짧은 것으로, 나는 요약 할 수 있습니다. 우리가 전에 찾았던 50, 번호 3과 확실히 상대적으로 꽤 큰 숫자이기 때문에 그래서 일단 높았습니다. 그래서 당신은 높은 것을 찾을 수 없습니다. 다음 정렬은 거기서 숫자 50를 찾아 갔어요. 내가 여러분을 어쩌면 혼란스럽게 했군요. 찾을 수 없습니다. 하지만, 여러분이 이 정렬 된 걸 알지 못했습니다. 그러므로 알고리즘의 나머지 부분은 시작에서 추측하는 작업을 한 후, 왼쪽에서 오른쪽으로 다음 반복하는 추측을 하는데, 그렇지 않으면 높은 곳에서, 낮은 곳으로 보세요. 좋아요, 그럼 우리는 여전히 이러한 접근 방식에 대한 몇 가지 형식도 골라낼 수 있습니다. 여러분이 말한 대로 최악의 경우 몇 단계가 걸릴 것입니다. N 단계요, 그렇죠? 그렇기 때문에 어쩌면 여기에 고했습니다. 좋아요, 50이 아니었습니다. 그럼 여러분은 낮게 갔는데, 아직 여기에 여러분은 N 에서 마이너스 한 나머지 요소, 그래요, 큰 O 사건을 통해 반복하고 결국 아닙니다. 그 경우에 단지 1 - 다시 한 번, 시간을 실행하는 가장 좋은 경우는 오메가입니다. 따라서 일정 시간을 따라서 이러한 종류의 시간은 어느 정도는 그 사람을 설정하고, 데려 갔어요. 실제로 이러한 값을 정렬하려면 다음 질문을 하고 있습니다. 그럼 우리가 할 수 있는 경우에 원형의 당신을 넣어 봅시다. (박수 갈채) 
법률 양식이 기다리고 있습니다. 자, 문제는 남아 있지요. 다음으로, 우리는 실제로 이러한 값을 정렬하려면 어떻게 해야 할까요? 그래요? 나는 사전에 구운 번호를 이용함으로써 클래스 종류 전에 했어요. 여러분이 방금 에드워드에 효과적으로 이어서 숫자의 무리를 넘기고, 나는 그 때 더 나은 알고리즘의 실행 시간으로 우리를 감동 시킬 수 있도록 그 값을 정렬하는 경우 시간이 얼마나 됩니까? 정렬하는 데 걸리는 시간이요. 글쎄, 그게 우리가 볼 수 있고, 대답 할 수 있는 훨씬 더 많은 질문과 훨씬 더 많은 시간이 소요되는 문제입니다. 그러나 지금 우리가 에드워드의 또는 이상적인 세계에서 정확히 할 수 없다는 걸 표현할 수 있는지 봅시다. 우리가 위크 제로에서 그랬던 것처럼, 우리는 이 알고리즘을 표현하거나 정말 모든 minutia을 기록하고, 비교적 C 코드에서뿐 아니라, 그 과정에서 앞으로 이동하는 알고리즘은 우리는 알고리즘의 아이디어를 전달하려면 우리의 의사 코드를 사용하여 이동할 수 있습니다. 의사 코드가 무엇인지에 대한 공식적인 표준은 없습니다. 다른 사람들은 다른 방법을 이용하지요. 하지만 중요한 것은 논리에 아무것도 추가하지 않고 당신의 생각에서 방해되는 세미콜론과 괄호 같은 바보 같은 세부 사항에 소강하기 없이 명확하게 아이디어를 의사 소통을 하는 것입니다. 그래서 다음과 같이 내 의사 코드를 정의하는 다소 전통적이긴 하지만 다소 임의적인 접근을 했습니다. 내가 말한, 이 같은 선형 검색에서 어떻게 세계는 일반적으로 각 요소에 대해 N 개의 요소 때문에 입력할 때 여기, 여기에, 여기에서 시작하는 알고리즘과 그리고 왼쪽에서 오른쪽으로 이동하는 N을 동일 면을 하는지. N은 사실 반환됩니다. 따라서 입력에 N을 하고, 각 요소에 대한 - 네. 그래서입니다 – 거기에 이 의사 코드를 구현하거나 작성할 수 있습니다. 여러 가지가 있지만 그것은 일종의 배열이 있다는 것을 의미하고, 구문과 우리가 이를 표현하는 방법은 중요하지 않습니다. 그래서 제가 동일한 N에게 무슨 일이 생긴다면 배열의 각 요소에 I에 대해 말하는 방식을 이용할 것입니다. 내가 찾는 문제는 반환됩니다. 내가 진짜 돌아 오지 않을 수 없다면 들여 쓰기에 따라 내 프로그램의 마지막 줄은 반환이 안 된다고 말합니다. 그리고 답변은 에드워드는 그냥 그 두 번째 배열에 없기 때문에 52를 찾지 못했습니다. 그것은 단지 사건이었고, 있지 않습니다. 하지만 내가 그가 원하던 것을 할 수 있지만, 괜찮습니다. 내가 혼자서 할 수 있고, 우리는 실제로 전체 분리의 직접적인 응용 프로그램을 이용합니다. 이 검색을, 전화 아이디어를 정복할지 구현할 수 있습니다. 이제 이 알고리즘은 선형 검색보다 확실히 더 복잡하게 보이기는 하지만 우리는 이미 검색하여 전화 번호부와 그런 식으로 일에 얼마나 많은 시간이 저장되는지 봤어요. 따라서 이론적으로, 여기 수 50이 검색되었습니다. 그리고 아마도 그런 일 때문에, 그러니까 내 말은 높이가 낮은 것의 경험적인 것이 없었어요. 하지만 에드워드는 추측을 만들어 50 보다 작은 값입니다. 그럼 이 경우, 우리는 여기에 50을 이용 했지만, 그 다음에 여기서 171이기 때문에, 실제로는 상대적으로 작은 값이었습니다. 이것은 영리한 속임수였고, 비록 마지막엔 그는 실제로는 궁극적으로 단지 선형 검색보다 더 나은 아래로 자신의 신용 카드, 알고리즘 자체에 매우 신속하게 문제를 해결하였지만요. 결국 현실 세계에서 분명히 우리에게 시간을 저장할 수 있습니다. 이 영리한 추론이 그에게 찬사를 얻고 있기 때문에 알고리즘의 나머지는, 그가 운이 없었습니다. 여전히 같은 선형 알고리즘입니다. 그래서 내가 대신 마이크 스미스의 접근 방식을 적용 할 경우를 보지요. 내 전화 번호부는 내 배열의 중간 중간에 이동합니다. 그리고 지금은 50 번째를 찾고 있어요. 음, 우리는 그래서 우리가 반올림 함수 또는 천장이나 바닥이든 뭐든 간에, 그래서 제가 임의로 여기에 갈 것입니다. 이와 함께 작업 할 수 있습니다. 확신이 있는 몇 가지 이상한 수학 반올림 오류가 있습니다. 이 숫자는 50? 아니, 숫자 105입니다. 하지만 전화 번호부의 문제를 떠날 수 있었다 했을 때 위크 제로처럼, 난 지금 내 대답은 확실히 오른쪽에 있지 않을 것을 알아요. 그래서 난 여기 남아있는 숫자에 집중할 수 있습니다. 난 다음에 어디로 가야 할까요? 글쎄요, 난 본질적으로 같은 문제라고 생각합니다. 아직도 숫자 50를 찾고 있어요. 난 아직 배열이 있고, 거꾸로 예전의 절반만큼 큰 것입니다. 내 성능의 장점은 현명함인데, 그럼 내가 그냥 중간에 정면으로 보내 그 것을 사용할 수 있습니다. 수학이 아름다운 이유입니다. 이 하나를 선택할 때 작동하지 않습니다. 그렇기 때문에, 오른쪽을 임의로 왼쪽으로 선택할 수 있지요. 51의 경우. 하지만 지금은 그게 이 방법을 알아요. 이제 나는 여기가 51 또는 61이 아니라는 걸 알아요. 그리고 제 원래 크기의 4 분의 1이 되었습니다. 문제를 떠난 거지요. 따라서 이미 근본적으로, 분명히 에드워드보다 빠르게 이동 하는 거에요. 우리는 더 많은 공간과 더 흥미로운 문제가 생기면 명확하게 하는 경우에 자신의 배열에 주어진 더 많은 요소를 이용 해야 합니다. 그래서 두 가지 요소 남았어요. 내가 연구 한대로 이 임의의 것은 오른쪽으로 이동합니다. 아하, 번호 50이군요. 지금, 이 실제로 전체 사용 권한이 부여되었습니다. 알고리즘은 에드워드보다 느립니다. 에드워드는 두 단계를 했어요. N이 증가할수록, 점근적으로, 점점 더 큰 N이 될수록 점점 더 당신이 실행하며 감동받게 됩니다. 그렇기 때문에 이 세 단계를 했을 때, 아직 제가 주장을 만들려고 해요. 오만하게, 그럼에도 불구하고, 제 알고리즘은 더 좋아요. 제 알고리즘, 그리고 에드워드의 알고리즘의 시간은 공평하게, 단지 검색 같은 생각이 매우 느리지만 올바른 구현에 다시 디볼스 되지요. 지금 옆으로 빈틈을 위해 당신이 CS 50 이전에 취할 자격이 있는 컴퓨터 과학 코스의 모든 것이 발생하게 됩니다. 따라서 쇼핑 조건에서 염두에 유지할 것은 - 쇼핑 기간 시간입니다. 하지만 지금 장면은 호텔에서 지금 우리가 이 일을 표현하는 방법이 필요하므로, 그들이 무엇을 말하고 있다면 매우 잠재적으로, 나도 알다시피, 아마 잠재 의식이 안됩니다. 그래서 우리가 이를 표현할 수 있는 방법에는 여러 가지가 있습니다. 이것이 내가 이 검색 구현을 반복하는 일입니다. 지금까지 수업 시간에 우리는 반복하는 거리에 절반을 던지는 방법으로 전화 번호부 및 분할 하는 것에 대해 이야기했습니다. 하지만 지금은 시작에서 여러분이 여러 종류의 기계와 프로그램 능력을 가지고 – 여러분은 보다 정확하게 자신을 표현하는 시작을 해야 합니다. 여러분은 그냥 내게 전화 번호 50 또는 52를 찾아 컴퓨터로 말할 수 없고, 어떻게 그렇게 할 방법을 알려줄 필요가 있습니다. 여러분은 다시 말하자면, 컴퓨터를 가르쳐야 합니다. 우리가 의사 코드에서 해당하는 것을 의미 할 수 있으므로 한 가지 방법은 다음과 같습니다. 우리는 N 마이너스 1로 배열 브래킷 열을 불러, 배열의 입력에 그렇게 우리가 지금 논의하는 대부분의 배열의 길이가 N이지만 가장 큰 요소 색인이 분명 N 마이너스 1이 있으며, 우리는 이에서 카운트를 제로로 시작하고, 그리고 입력 된 K, 즉 내가 찾고 있는 값 K를 나는 이 검색의 아이디어로 구현 해야 합니다. 그래서 여기 기울임 꼴로 먼저 변수를 정의 할거에요. 그리고 제로로 초기화합니다. 어제라는 또 다른 변수를 정의하고 N 마이너스 1로 초기화 할 거에요. 미래에 대한 문제를 설정해야 요청할 수 있습니다. 그리고 여러분이 이렇게 생각되는 경우 다음 단계는 어떻게, 매우 정확하게 이러한 접근 방식을 구현하기 위해 질문을 물을 거예요. 다음 요소에 N개가 있습니다. 저는 저의 오른쪽 변수로, 저의 왼쪽 변수로 내 왼쪽 손을 사용 하는 거에요. 그리고 그것은 첫 번째 단계에서 수행 해야 하는 것입니까? 음, 첫 번째는 보다 작거나 지속적인 평등에 있습니다. 이게 왼쪽이기 때문에 정말 좋은데, 나의 왼쪽 손은 내 오른 손보다 정말 작습니다. 어떻게 해야 합니까? 중간이 먼저 동일하게 하고, 플러스 한 다음 마지막으로, 2로 나눈 값입니다. 그래서 이 색인에 색인을 추가하면 나를 위해 수행한 것은, 2로 나누어 라운딩 처리를 하였고 그것은 나에게 중간 번호를 제공합니다. 자 이제, 지금은 105를 이야기 해봅시다. 그러니까 중간이 그 요소와 같습니다. K는 배열의 중간 요소보다 작다면, 그럼 마지막으로 같은 중간에 마이너스 1을 봅시다. 좋아요, 내가 50 번째를 찾고 있어요. 그래서 50 번 째 배열의 중간 요소보다 작은 것을, 그래서 어떻게 해야 하죠? 그럼 이 상태는 마지막으로 동일한 가운데 마이너스 1을 하게 합니다. 여기가 마지막이에요. 여기가 가운데입니다. 여기에 중간에서 마이너스 1을 한 것입니다. 그리고 이미 반복하면서 우리는 매우 간단한 아이디어를 적용하는 방법을 본 적이 있습니까? 여러분이 실제로 나노에서 코드를 입력할 수 있는데, 더 가까운 GCC는 무언가에 반의 반으로 문제를 분할하게 됩니다. 이는 논리에 따르면, 여러분이 찾을 수는 반복적인 (안 들리게). 그게 저기에 없어요. 저는 52에서 보면, 여러분도 알다시피, 저는 왼쪽으로 너무 멀리, 오른쪽으로 너무 멀리 갔어요. 거기뿐 아니라 이 때문에 내 손은 교차하였고, 아니면 내가 찾고 있는 번호의 상단에 정면으로 가볍게 두드리는 것을 종료하게 되지요. 그것은 50 또는 52인지의 여부를 지정합니다. 그런데 우리가 잃어버린 것은 원래 알고리즘의 아름다움입니다. 어떤 분할 및 정복에 대한 정말 멋진 것은 그렇게 설명하는 간단한 것입니다. 전화 번호부를 가져와서 요소를 보세요. 그것을 반으로 나눠 보세요. 그보다 어떤 경우는 오른쪽보다 더 큰 경우라면, 왼쪽으로 이동합니다. 이를 계속 반복합니다. 이것에 대해 이러한 우아함이 있지요. 방금 반으로 문제를 나누어 말한 곳에서, 반복하고 또 반복 한 후 무언가를 확인합니다. 이건 정말 그 알고리즘의 단순성의 일부를 보여주지요. 그러나 우리가 이 능력을 가지고, 그것은 C에서 밝힐 것인데, Java에서의 C + +, 이러한 언어의 모든, 당신은 재귀의 기능의 CS 51에 충당 할 수 있는 LISP 및 계획과 같은 것을 반복할 때마다 당신은 본질적으로 다시 동일한 알고리즘을 적용하여 반복 할 수 있다는 것이 밝혀졌습니다. 지금 여러분은 지금까지 C에서 어떻게 알고리즘을 구현했습니까? 글쎄요, 여러분은 몇 가지 알고리즘을 구현하여 암호화하거나 카이사르와 같은 함수를 쓰게 되지요. 우리가 반복의 생각을 표현 해야 하는 경우, 그래서 아마도 우리는 함수와 단지 퍼즐의 작은 조각에 다시 자신을 호출 할 수 있습니다. 음, 그게 무슨 뜻 이죠? 네, 이러한 아주 간단한 프로그램을 살펴 보시죠. 이 것은 시그마 1.C입니다. 그래서 이 오늘의 두 프린트 아웃 중 하나 인 출력의 코드 두 가지입니다. 그래서 이 것은 다음과 같습니다. 여러분의 수학 책에서 약간의 기호에 경의에서 정수는 그것이 시그마라는 것을 반환하였고, 단지 합류를 의미하는 함수가 될 것입니다. 그래서 이 일을 하고 싶습니다. 이러한 것은 그래서 I.의 M에 0이 동일한 것입니다. 고등학교 수학 책의 뒷면과 같이 표현하려면 M에 제가 0을 동일한 숫자로 모두 요약 해야 합니다. 그래요, 그럼 흥미로운 문제에 0까지의 모든 숫자의 합을 계산하지만, 우리가 해결 할 수 있는 방법은 흥미로운 것들이 있습니다. 그럼 여기에 약간의 정신적 검사를 해봅시다. 우리가 더 나은 자신의 오류 검사에 대한 프로그램을 위해서 우리의 습관에 들어가 지난 주에 이 같은 정신 검사를 수행합니다. 함수가 여기에서의 선언에 따라 최대로 될 수 있도록, 그 INT에 전달 될 예정입니다. 따라서 그게 여러분이 원하는 INT가 될 것 입니다. 이것은 의미하지 않는데, 음수가 될 수 있습니다. 이는 0이 될 수 있습니다. 우리는 만약 오로지 양수의 값만 더하기를 원한다면. 그래서 저는 그 정신 검사를 수행하여 무한대의 루프에 대한 위험을 피하고자 합니다. M이 만약 1 미만이라면 제로를 반환합니다. 따라서 이는 C와 많은 언어들에 대한 흥미로운 점입니다. 만약에 여러분이 어떻게 해서든 오류 조건과 일부 언어를 의미해야 하는 경우가 있다면, 고등학교에서 배워 여러분도 알다시피 자바와 같은 예외라고 불리는 것들을 갖게 됩니다. 여러분이 빨간 깃발을 마련하고 모든 값을 반환하는 귀찮음을 갖지 않을 수 있을 때. 그러나 C와 같은 언어는 함수가 일반적으로 값을 반환 해야 합니다. 여기에서 사건은 정수입니다. 그리고 때때로 여러분은 우리가 특별한 보초 값들은 함수가 올바르게 작동하는지 확인하려면 함수를 사람이 확인했다는 특별한 가치 같은 것을 반환 해야 합니다. 따라서 이는 단지 경고를 출력하고 함수에 대한 것이 충분한 게 아니라, M 이 1미만일 때 입니다. 어떻게 이 함수가 오류가 바로 발생했음을 알게 될 수 있게 하는 코드가 무엇인가요? 이 때문에 이것은 우리가 반환 값을 부작용과 함께 지난 주에 만들려고 노력하는 한 것입니다. 인간의 부작용을 볼 수 있습니다. 컴퓨터는 반환 값을 볼 수 있습니다. 우리가 이 함수를 호출하고 이런 오류가 발생하면 확인 할 수 있도록 내 코드를 원하는 코드로 작성하려고 한다면, 나는 인쇄 데프에 의존 할 수 없습니다. 나는 반환 값에 의존 해야 합니다. 그래서 입력이 안 되는 경우에 어떤 값을 반환 할 수 있을까요? 자, 내가 임의로 제로를 선택했습니다. 어떤 것은 본질적으로 오류를 의미로 돌아가 다른 적당한 값이 있었다고 생각합니까? 부정적이네요, 왜죠? 글쎄, 이것 때문입니다. 여러분은 부정적인 가치를 명확하게 하고 이 함수의 요점은 뭔가 잘못되었을 때 양수의 합류와 음수를 다시 다른 곳에서 추측 할 수 있으리라는 기능을 말합니다. 이렇게 반환하는 경우에 우리가 여기로 돌아 오면 이것이 있기 때문에, 다시 우리는 매우 간략하게 언급 하였던 지난 주를 생각해보면, 문자열은 때때로 허구의 값을 반환하거나 본질적으로 문자열을 반환 할 수 없습니다. 가끔은 어떤 특별한 보초를 반환 할 수 있을까요? 이것이 널 (null)이었고, Google에서 더 많은 시간을 볼 수 있습니다. 정말 오지 않았지만, 모두 대문자로 NULL이 의미하는 상수입니다. 나는 거기에 해당하는 어떤 문자열은 없습니다. 하지만 반환 값 함수입니다. 무언가를 반환 해야 합니다. 때로는 여러분과 함께 확인하기를 원하기 때문에 여러분은 여러분이 고용 할 수도 있는 새로운 기능에 대한 과정에서 나중에 사람이 페이지를 컨설팅 하기 시작할 때, 여러분은 이 기능이 무슨 상관이지 반환 값을 말하고 매뉴얼의 섹션을 확인 해야 합니다. 자신의 조건에서 나는 값을 돌리지 않았습니다. 음, 이 코드는 간단합니다. 지금 한번 내가 이 정신 검사를 해봤습니다. 내가 M을 통해, M을 통해 또는 equivalently가 0 또는 1에서 숫자를 요약하려면, 내가 이 일을 할 것입니다. 나는 변수의 합계를 선언하는 거에요. 그럴 것입니다. 유형 INT을 통해, 나는 제로로 초기화 합니다. M미만 또는 M과 같은 값으로 동일하게 - - 그럼 제가 M에 1과 모든 방법을 동일하게 반복할 것입니다. 그리고 + +, 다음 이 코드는 궁극적으로 무엇을 할까요? 제가 이 행동을 통해 여기서 터미널 창에 진행하게 볼 수 있도록 하면, 그냥 1에서 M 또는 M으로 될 것입니다. 모두 오른쪽에 있는 모든 숫자를 잘 표현하고 있습니다. 이 것들을 진행하고 새로운 하나를 열어, 제가 nice.fas.harvard.edu에 앞서 SSH를 놔두고 나의 CS 50 디렉토리로 이동하는 경우, 알았어요. 강의 3, 3번째 주, 알았어요. - 시그마 하나. 그래서 이는 이렇게 정확한 코드입니다. 주의할 것은 - 오, 내가 이 파일의 상단에 있는 이것이 있습니까? 거기에 프로토 타입으로 시그마를 선언합니다. - 여기서 중요한 핵심은 무엇입니까? 여러분은 그냥 파일에 나중에 구현 될 수 있지만 분명히 내가 함수를 호출하는 경우에는요, 네, 그래서 지난 주에 이걸 했던 기억이 슬라이드에 잠시 전하였지만, 확실히 - 그 바보 같은 세부 사항을 하게 됩니다. 여러분은 사전에 컴파일러라는 말이 있는데, 시그마라는 이 파일의 함수가 그 정수를 반환하고 그냥 정수에 걸립니다. 결국 기대하는 것을 알아요. 그리고 이 것도 알고 있습니다. 여러분이 함수에 대한 프로토 타입을 선언 할 때, 여러분은 변수의 이름을 제공 할 필요가 없다고 밝혔습니다. 모든 컴파일러는 인자로 가지고 있는 변수의 유형입니다. 그 시점에서 알아야 합니다. 그럼 여러분은 말 그대로 그냥 쓸 수 있습니다. 또는 두 개의 인수, 정수, 쉼표, 어쨌든 이 것들이 있다면. 따라서 두 방법은 유효합니다. 나는 INT-M으로 여기까지 변수의 이름을 지정할 수 있지만 그 것이 필요하지는 않습니다. 그래서 내가 코드를 쓸 때 매우 축소하는 경향이 있습니다. 이것이 그 기능입니다. 그리고 이에 대한 흥미를 유도 해 더 많이 할 수 있도록, 다른 세부 사항을 확인합니다. 이 질문을 했기 때문에 나는 이번 주말에 게시판에 확인할 것입니다.  
(안 들리는 청중의 코멘트)  
그래요, 따라서 논리적 오류는 모든 시간을 제로로 합계를 초기화하고, 정수를 선언합니다. 그럼 안 좋은데, 전에 내가 이러한 것을 하는 경우는 무엇일까요? 가끔 루프 내에서 값에 두 개의 변수를 초기화 할 수 있습니다. 그럼 괜찮아 질 것 같습니다. 그러나 어떤 종류의 오류가 난 다음에 실행 하려고 하고 있습니다. 여러분의 일부도 있을 수 있습니다. - 맞아요? 오, 이거에요. - 수업 중에 그와 같은 스트레칭은 하지 않도록 합니다. 좋아요. 그래. 뒤쪽에. 
 
(안 들리는 청중의 코멘트) 
그렇지요. 마지막 범위의 주 토론을 기억하십시오. 따라서 일반적으로, 여러분은 변수를 선언 할 때, 중괄호 안에 있는 말, 또는 이 경우에는, 내부 루프를 들어, 변수는 루프를 위해 내부에 살고, 어떤 계산이 완벽함을 의미합니다. 우리는 제로로 합계를 초기화하고, 만약 우리가 합계에 추가하여 유지하더라도 여기 제가 이 것을 반환하려고 하여 제 컴파일러는 범위 밖에 있기 때문에 이 경우에도 합계가 선언될 예정입니다. 이 범위 전체에 대한 시간이 남아있을 수 있도록 제가 루프의 변수 밖에서 선언했을 때 그 순간 전에 매우 신중해졌습니다. 그래요, 그러니 가서 여기에 저장하세요. 시그마 1을 봅시다. 지금 나에게 많은 것을 처리하기 때문에 GGC와 그를 입력 귀찮게 하지 않을 거에요. 내가 미리 와 이렇게 현재 디렉토리에 있는 보안상의 이유로 이것은 명확합니다. 입력하는 양의 정수, 희망하기를 10이라고 합시다. 운이 좋다면, 맞습니다. 9. 괜찮아요. 제가 신속하게 확인할 수 있습니다. 하나를 수행 해봅시다. 3! 네, 3 플러스 2 플러스 1, 사실 6과 같을 수 있다고 확신합니다. 이 코드가 올바른 것처럼 느껴집니다. 우리는 매우 다른 방식으로 이 작업을 구현할 수 밖에 없습니다. 하지만 그것은 이 함수를 먼저 어떻게 호출하는 것이지요? 자, 유용한 곳의 예입니다. 우리는 지난 주 말 - 우리는 여러분이 뭔가를 사용자에게 여러분이 할 수 있는 기회를 제공하고, 이를 제공하지 않을 경우 다시 물어야 할 때 종종 유용한데요, 그렇게 지난 주 말에 여러분은 찾고 있었습니다. 그래서 여기가 정확한 시나리오입니다. 나는 다음을 수행 할 거예요. N이라는 정수를 선언합니다. 사용자의 양의 정수를 알려주세요. 그럼 내가 INT를 얻기 위해 CS 50 라이브러리에서 INT를 사용 하는 거지요. 그리고 여기에 오히려 나는 다시 N 시점에 덜 한 것보다 이 경우, 그 구조 내에서 확인을 다시 할 것이며 그리고 그렇게 하고 있습니다. 그러니까 이것이 일반적인 방법입니다. 이를 명확하게 하기 위해 사용자가 입력하고 그 결과를 받고 하는 동안 어떻게 하면 내 컴퓨터를 엉망으로 시도하고 음수 123 또는 음수 6을 말하려고 하면, 그것은 그저 나를 계속해서 괴롭히는 것입니다. 하지만 잊지 마세요, 지난 주에 내 임의의 단어였던 원숭이. 왜 여기에서 양의 정수 대신 이걸 말하게 되었을까요? 그래서 이것은 (안 들리게) 얻을 수 있는 정수입니다. 이름이 INT라는 의미처럼, INT는 사용자의 INT를 위해 그것의 최선을 다할 것입니다. 그러나 그것이 양수이거나 음수 또는 그러한 것들과 같은 것이 될 거라고 보증하지 않습니다. 단지 여러분에게 정수를 얻을 수 있습니다. 우리가 이 것의 아름다움에 힌트가 재귀라고 하는 흥미로운 방식으로 이 같은 기능을 구현할 수 있게 된 것입니다. 그 자체를 호출하는 경우 함수는 재귀입니다. 이제 처음으로 보는 것 또는 처음으로 듣는 것은 아마도 조금 꺼림칙하게 될 수도 있습니다. 만약에 내가 함수이고, 나는 입력과 함께 불러졌다면, 그리고 내가 그 문제를 내 스스로 부름으로써 해결한다면 그것은 즉시 무한대의 루프가 될 것이고 좋지 않은 일들이 발생하게 될 것입니다. 그러나 바라건대 여러분은 영구적으로 자신을 호출하여 보관하지 않도록 하는 몇 가지 방법이 있을 것입니다. 그것은 기본 케이스라고 합니다. 따라서 Signa의 구현이 코드만 오로지 네 개의 선이라는 것을 알아차리세요. 그리고 솔직히 말해 만약에 내가 들여쓰기의 일부를 제거한다면, 전부 그것은 아마도 두 라인의 프로그램일 것이며 아마도 하나의 라인 프로그램일 것입니다. 그럼 어떻게 해야 하죠? 내가 스스로 입력 한 M은 0보다 작거나 같을 것입니다. 그렇다면, 그냥 0을 반환하세요. 왜냐하면 만약 내가 음수를 처리하려고 시작한다면 그다지 좋지 않은 일이 일어날 것이기 때문입니다. 지금 분명 나는 이 질문에 대답하기 위해 수행해야 할 모든 자신을 호출하게 됩니다. 그리고 이것은 여러분이 이 이상한 원형의 마법을 얻게 되는 곳이기도 합니다. 이것을 알아두세요. 내가 한 것 모두를 생각해봤을 때, 그렇게 하지 않았다면 나의 기본 케이스 다음에, 나의 정신 검사 이후에, M으로 결과가 반환되는지 그리고 내가 지나친 그 값 뿐만 아니라 M 마이너스 1의 시그마를 확인하세요. 이제 그것은 홀로 작동하게 됩니다. 만약에 내가 나의 터미널로 돌아가서 시그마 2를 컴파일 하고 그리고 시그마 2를 작동하고 그것을 숫자 3에 준 다음 6으로 돌아오는 경우, 만약 그것을 10으로 주면 나는 55를 얻게 됩니다. 사실 이것은 작동합니다. 그리고 어떻게 이게 아직도 작동하는 것일까요? 음, 같이 봅시다. 그러니까 그것은 이 문제에 0부터 M까지의 모든 숫자를 더하고 또는 M과 같은 수부터 0까지의 수를 더하는 것은 꽤 쉽지요. 정말 쉬워요. 만약에 여러분이 나에게 숫자 M을 주고 나서 나보고 M부터 M보다 작은 0까지의 수의 합이 뭐냐고 묻는다면, 글쎄요, 나는 아마 대답할 수 있을 거에요. 맞습니다. 좋아요. 그것은 M 더하기 M 마이너스 1보다 작은 수를 모두 합한 값입니다. 아주 좋아요, 그럼 여러분에게 다시 한 번 질문을 하게 해주세요. M 마이너스 1보다 작은 수를 모두 합한 값은 얼마일까요? 좋아요, 그것은 M 마이너스 1에 M 마이너스 2 보다 작은 수를 모두 합한 값을 더한 값입니다. 맞습니까? 여러분은 이것을 정말로 현명한 방법으로 해결할 수 있어요. 오, 그래요. 그것은 M 더하기 나머지 그 것들의 합이 바로 정답입니다. 네, 그럼 그 나머지 그 것들의 합은 무엇인가요? 그래요. 그건 나머지 그 것들의 값보다 아주 작은 값에 나머지를 더한 값이지요. 맞습니다. 여러분은 이것을 그저 계속 하기만 하면 퍼즐 조각에서 하나 남긴 상황까지 갈 수 있는 겁니다. 그리고 그것은 영원히 갈 것처럼 보이지만 사실은 그렇지 않아요. 왜냐하면 결국 저는 여기 이 것을 얻게 될 것이고 내 마지막 퍼즐 조각은 M과 같은 그 것으로 갈 것이기 때문이지요. 그게 뭐라고요? 0입니다. 그리고 그건 제가 소위 말하는 기본 케이스를 마무리 했을 경우인데, 나의 모든 답들이 이제 섞이기 시작하네요. 다시 말하면, 나는 이 질문을 하는 사람과 함께 이 게임을 재생하여 책임을 전달하는 것 같네요. 네, M 더하기 그 아래 숫자들의 합은 무엇인가요? 음, 그건 M 더하기 그 것보다 작은 숫자들을 모두 합한 값입니다. 그럼 그 합은 뭔가요? 맞아요. 결국 우리는 마지막 바닥에 0을 가지고 있지요. 그리고 다음으로 나는 마침내 유용한 대답을 다시 할 수 있게 되었지요. M이 그것과 같아 질 때까지. 그러나 여기서 무엇이 포인트가 되는 것인가요? 네, 그리고 다시, 이건 여러분이 아마도 궁극적으로 보기 시작하는 그것인데, 그리고 아마도 여러분이 지금까지 결코 보지 못했던 것이기도 합니다. 그러나 어떤 것을 표현하는 것에 대한 아름다움의 한 종류에요. 바보 같은 숫자에 대한 편집 시나리오 같긴 하지만. 그리고 이것은 매우 대표적인 접근이 될 겁니다. 더욱 크고 더욱 흥미로운 문제를 해결하기 위한 접근이요. 그렇지만 여기엔 함정이 있습니다. 나를 계속해서 100의 내 첫 번째 버전인 어떤 하나의 시그마를 작동하게 해주세요. 그것은 꽤 잘 작동합니다. 그럼 1000은 어떤가요? 역시 꽤 잘 작동하지요. 그럼 10000은 어떤가요? 여전히 작동합니다. 100000은요? 아주 좋아요. 그런 다음 궁극적으로 내가 int를 소진하기 위해 시작하겠습니다. 좋아요. 그럼 이제 나는 int를 소진합니다. 그러나 우리는 그것을 기대할 것입니다. 나를 이제 시그마 2를 작동할 수 있도록 해주세요. 그럼 그건 더욱 훌륭한 해결책이 될 겁니다. 이것은 마치 심지어 더 빠를 것이라고 느끼게 되는데, 왜냐하면 솔직히 말해서 코드에 대한 더 적은 선이 있기 때문이지요. 네, 어떻게 되었는지 살펴 봅시다. 어머나, 10이네요. 그건 작동을 하였습니다. 그럼 100은요? 네 작동하였습니다. 그럼 1000은요? 여전히 작동하죠. 그럼 10000은? 아주 좋아요. 다음 100000은요? 네, 여기네요. 멈추었습니다. 오, 이제 여러분 중 일부는 이 문제를 역시 보게 되었습니다. 그리고 우리는 결국 웃고 있지요. 그래서 이 분석에 대한 모든 공평함은 학생들이 게시판에 질문을 하게 합니다. 내 프로그램이 멈추었는데 실수라고 말함으로써 이게 괜찮은 것이냐고 말이죠. (안 들리게) 덤프. 아니에요. 그러니까 이건 안 좋은 것입니다. 질문하는 여러분에게 축복이 가득하길. 그러나 이건 그 문제에 대한 해결책이 아니에요. 이건, 내가 게시판에서 말한 대로, 솔직하게 말하자면 또는 아마도, 실제로 아마 이건 개인적인 e 메일인데, 내가 나의 답변으로 말했듯이 이건 마이크로 소프트 워드와 동등한 리눅스의 일종입니다. 또는 여러분의 Mac 프로그램에서 그저 얼어버린 것 또는 예기치 않게 종료된 것, 굉장히 짜증나는 그 것이지요. 이것은 LINUX 세계에서 가장 상응하는 일종의 것 입니다. 하지만 운 좋게도 지금 우리가 프로그래머이고 우리가 사용자가 아닌 걸, 그 투기 핵심이라는 사실은, 말하자면, 실제로 유용합니다. 오늘의 목적을 위해 세분화하고 나쁜 기억에 대해 무슨 일이 있었던 것을 의미합니다. 컴퓨터의 메모리는 일반적으로 세그먼트의 무리로 모델링 되어 있기 때문에, 그래서 세분화가 잘못 된 메모리에 관하여 틀리게 간 것을 의미합니다. 핵심은 유용한 무언가가 내 현재 디렉토리에 남아 있다는 의미입니다. 내가 핵심이라고 생각하는 이 파일이 있는지 I목록 형 LS를 발견합니다. 코어는 실제로 내 컴퓨터를 망쳐 순간적인 시간에 꽤 많이 컴퓨터의 RAM의 내용을 포함하는 파일입니다. 지금 그 보안 문제와 내 개인 정보 보호 문제 때문에 이 시스템의 모든 사용자의 메모리는 아닙니다. 하지만 유용하게 우리는 일주일 정도면 우리가 그 파일의 내부를 해부하기 시작하면서 표시됩니다. 그러나 지금의 질문은 매우 간단히 이런 일이 생긴 이유에 대한 것 입니다. 왜 처음 버전으로 제로의 동일한 수를 처리 할 수 표시되지 않을까요? 이제, 첫 번째 버전을 부여하면 여전히 깨지지만, 궁극적으로는 전과 같은 끔찍한 방법으로 망가지지 않습니다. 그래서 분명히 시그마 1 일이 없었고 시그마 2에 일어나고 있습니다. 그리고 다시, 여러분 중 몇 몇은 모든 코어가 찼다고 합시다. 학기 말까지 솔직히 걸려 넘어와 있습니다. 이유는 무엇입니까? 무슨 일이 잘못 갈 수도 있을까요? 그래서 메모리로 표시 할 수 있습니다. 메모리는 이 프로그램에 사용 된 곳을 받고 있습니다. 이 함수 M이라는 매개 변수 이외의 지역 변수조차 표시되지 않습니다. 그러니까 메모리가 이용된 곳이 어딘지 같은 것 말이죠. 이와 같이, 저는 왜 메모리 문제를 가지게 된 걸까요? 네, 그러니까 내가 M을 가져올 때, 나는 시그마를 통해 언제 어떻게 해야 하는 걸까요? 
 
(안 들리는 청중의 코멘트) 
그래서 이것은 만듭니다. - - 그래서 조금 더 많은 메모리를 할당합니다. 사실, 제가 지난 주로부터 이 작은 사진으로 기억하게 해주세요. 그리고 우리는 이것으로 돌아왔다고 말합니다. 이건 컴퓨터의 RAM을 나타내는 사각형을 기억해 불러옵니다. 그러나 지난주로부터 더 중요한 사항은 여러분이 하나의 함수를 부를 때마다 작은 메모리의 기억은 함수를 위한 소위 스택이라고 불리는 것을 할당한다는 것입니다. 그리고 그 메모리의 작은 기억은 우리는 프레임이라고 부르는데요, 그러니까 만약 시그마가 이름으로 불려지고 그 다음 시그마가 누군가의 버전 2로 불려진다면? 시그마입니다. 그리고 그러고 나서 시그마는 시그마를 부르고, 그리고 시그마는 또 시그마를 부르는 것이죠. 여러분도 알다시피 이 사진에는 비록 여러분이 할당할 수 있는 메모리의 양보다 많은 것을 담지는 못했지만 내가 현실에 있다는 것을 암시했습니다. 전형적인 시스템에서는, 주어진 프로그램이 종종 2 기가 바이트 이상의 메모리를 사용하지 못하는 경우도 있습니다. 이제 그것은 많은 메모리이죠. 그러나 불필요한 프로그램, 포토샵과 같은 프로그램과 또 거기에 있는 실제 흥미로운 현실 세계들 몇 몇이 여기에 있습니다. 그렇지만 요점은 이 직사각형이 궁극적으로는 그것의 꼭대기를 가지고 있다는 것입니다. 그리고 만약 당신이 계속해서 더 많은 것을 여러분의 스택 프래임이 넣으려고 노력한다면 결국 여러분은 그것이 필요로 하는 것보다 더 많은 것을 어떤 것과 함께 오버랩 되게 될 것입니다. 사실, 우리가 지난주에 이야기했던 그 직사각형의 꼭대기를 간단하게 어떻게 말 할 수 있을까요? 뭐라고요?  
 
(안 들리는 청중의 코멘트) 
따라서 여기 한 묶음이 있습니다. - - 전역 변수들이 있습니다. 그러나 거기에는 또한 텍스트 세그먼트도 있지요. 우리가 그 것을 부르듯이 그 프로그램 자체가 작용합니다. 여러분의 제로와 여러분의 프로그램 자체의 것들 말입니다. 자 이제 이것은 여러분이 여러분의 프로그램을 디스크에 덮어 썼다는 것을 의미하지 않습니다. 이것은 여러분의 코드를 여러분이 지우고 있다는 것을 의미하지 않습니다. 그러나 그것은 그 운영되는 시스템이 단지 여러분이 이미 다른 곳에 속하는 메모리를 사용하려고 하면 모두 다같이 없어진다는 것을 의미합니다. 따라서 계속해서 끝으로 가봅시다. 그리고 수요일에 우리는 어떻게 이것들이 작용하는지에 대한 해결 방법을 알아보겠습니다.
* 이 스크립트가 작성완료되었다면 스크립트 작성완료 요청하여 주십시오.
 
펼쳐보기

히스토리

프린트

 
>> Welcome back to CS 50. This is Week 3. And on the evaluations at the end of last fall we got a comment from a student about how they apparently were in incentivized to come to class early simply because we started most every lecture with a little something stupid. So I thought we'd begin two minutes early so that we can squeeze in two such minutes of motivation. This one related, of course, to Problem Set 2, which for those of you doing the hacker edition challenges you not to implement ciphers but to do the reverse, cryptanalysis, and actually decrypt some known people's passwords. So with that, I give you this perhaps famous clip.  
 
>> What's going on, what are you doing to my daughter?  
 
>> Permit me to introduce the brilliant young plastic surgeon, Dr. Philip Slotkin, the greatest nose job man in the entire universe and Beverly Hills.  
 
>> Your Highness.  
 
>> Nose job, I don't understand, she's already had a nose job. It was her sweet 16 present.  
 
>> No, it's not what you think. It's much, much worse. If you do not give me the combination to the [Inaudible] Dr. Slotkin will give your daughter back her old nose!  
 
>> No! Where did you get that?  
 
>> All right, I'll tell, I'll tell.  
 
>> No, daddy, no, you mustn't.  
 
>> You're right, my dear. I'll miss your new nose, but I will not tell him the combination no matter what.  
 
>> Very well. Dr. Slotkin, do your worst.  
 
>> My pleasure.  
 
>> No! Wait, wait! I'll tell. I'll tell.  
 
>> I knew it would work. All right, give it to me.  
 
>> The combination is 1.  
 
>> One.  
 
>> One.  
 
>> Two.  
 
>> Two.  
 
>> Two.  
 
>> Three.  
 
>> Three.  
 
>> Three.  
 
>> Four.  
 
>> Four.  
 
>> Four.  
 
>> Five.  
 
>> Five.  
 
>> Five.  
 
>> So the combination is one, two, three, four, five.  
 
>> That's the stupidest combination I ever heard in my life, that's the kind of thing an idiot would have on his luggage.  
 
>> Thank you, your Highness.  
 
>> What did you do?  
 
>> I turned off the [Inaudible] --  
 
>> No you didn't, you turned off the whole movie.  
 
>> I must have pressed the wrong button.  
 
>> Put it back on, put the movie back on. Got to get that thing fixed. We're back, and we have the combination.  
 
>> What?  
 
>> We're done with you. Go back to the golf course and work on your putts.  
 
>> Let's go, Arnold, come Gretchen. Of course you know I'll still have to bill you for this.  
 
>> Bet she gives great helmet.  
 
>> Did it work? Where's the key?  
 
>> It works sir, we have the combination.  
 
>> Great. Now we can take every last breath of fresh air from plant [Inaudible] What's the combination?  
 
>> One, two, three, four, five.  
 
>> One, two, three, four, five?  
 
>> Yes.  
 
>> That's amazing. I've got the same combination on my Luggage! Prepare, Space Ball One for immediate departure.  
 
>> Yes sir.  
 
>> And change the combination on my luggage.  
 
>> Okay, it really doesn't get stupider than that. So this is CS 50. We left off last week looking at cryptography, the motivation for which ultimately was to introduce a problem domain for Problem Set 2. But more than that, it was to make clear this reality that if you've already sat down to tackle P Set 2, or will soon this week, what's ultimately a fairly interesting idea, taking plain text, converting it to cipher text, and generally doing something useful, encrypting information, it really reduces to some things that are very, very simple. You're going to find that taking in plain text is a matter of calling something like get string, which of course returns to you a string, which of course is just an array of characters. Well, encrypting text, then, is really going to reduce itself to just iterating over that array from I equals 0 on up on the length of the string, and then doing some kind of manipulation of each of the characters. Maybe in the case of Caesar, some addition. But there's a problem with the Caesar cipher. So the Caesar cipher is this -- this algorithm via which you take some text and quote unquote rotate each of the characters by some number of places. And rot 13 [Assumed spelling] was a very specific instance of that, where the secret rotational value, the so-called key was in that case 13. But we can generalize. It can be anything, from 0 on up to infinity. But of course only a few of those, say 26, actually have some utility. How would you go about cracking, that is figuring out someone's password, if it were encrypted with the Caesar cipher? If I hand you a string of text, it looks like nonsense because it's been encrypted with rot 13, not twice, but once. What would you do?  
 
[ Inaudible audience comment ]  
 
>> What's that? Okay, so frequency analysis. So a fancy way of saying, well, there's some letters in the alphabet that are more popular than others. If you've ever watched Wheel of Fortune, you'll realize that most contestants know this. So maybe you look for the most frequently reoccurring letter in the cipher text and realize, hmm, Q, Q appears an awful lot. But wait a minute, this has been encrypted. It's probably the case that Q is the result of encrypting a more common letter, maybe E, for instance, and getting Q as a result. So you might be able to reverse engineer what the secret key is by making some inferences. Or even if you're not that clever and you've never heard this term frequency analysis, but you know it's been encrypted at least with Caesar, I mean, what is another approach, a correct approach, if naive approach, even. Yeah?  
 
[ Inaudible audience comment ]  
 
>> Yeah, that's only 26 keys that might have been used if we're talking about Caesar. So yeah, might be a little tedious, but it's not going take forever just to try all possible keys. And in fact, you don't have to try all possible keys on the entire message, especially if this is an entire letter or paragraph or whatever that's been encrypted. It will try the first few letters, and if you start seeing English pop out, or maybe French or Spanish or anything that can be expressed with A through Z, odds are if it looks like a word, if it looks like a sentence, bam, you found a key. So Caesar is not all that strong, and maybe it was in fact used back in the day, but there have been certainly improvements on it since. Because even we with a pace of paper and a pencil could crack the Caesar cipher. Well, the Visionaire [Assumed spelling], cipher, which came along some years later is a little for sophisticated. It takes the approach of Caesar, of rotating letters in the alphabet by some number of places, but of rotating different letters by a different number of places. So instead of using K, the key, the numeric key, to encrypt every single letter in your plain text, it uses a different key for each successive letter. Now that doesn't go on forever, you usually pick a fixed number of keys, and in fact, if you just need a fixed number of keys, you just choose what we call a keyword. So something like foobar. Now, as an aside, if you've wondered why I constantly resort to fu and bar and all Baz and all of these strange names for variables, you'll find that this is just a silly computer science thing, a silly programming thing, a convention. Whenever you need to whip out a random variable for the sake of discussion, fu is typically one's first instinct. Bar, is followed by that, and then ucks [Phonetic], and then there's a whole bunch of silly ones after that. So foobar is sort of a conical example of a random word that we might use. But we just have to realize that each letter in foobar in this case just represents a different key. So F represents one key, O represents another. O happens to represent the same. B is another key, so in other words you take your keyword, you line it up under your plain text, and you rotate each of the plain text characters by the number of places implied by the key. So now what is F? Well, let's see, if we start counting as zero as we typically do, A is zero, so then it's B, C, D, E, F. So F represents the number, the key 5. So what does that mean? Well, if my plain text P is hello world, and I need to rotate H by F, that is by 5 places, I go H I J K L M. Okay, so the resulting cipher text letter is M, and then I repeat that same process using different keys. Now presumably, I might -- plain text, the message I want to encrypt, is hopefully going to be longer than the key. If you're remembering a key that's longer than your actual message you're losing some efficiency there, perhaps. So foobar is only six letters. So what if our plain text is longer than six letters? Well, you just start repeating again and again and again. So let's ask the question for just a moment, then. If there are 26 possible keys for Caesar, how many possible keys are there for Visionaire, by contrast? Little louder, little more confident. Okay, infinitely many, certainly, because we can pick any possible keyword of any length. But let's generalize. Suppose we have N letters in our keyword for Visionaire. How many end letter key words are possible for Visionaire? Right, so 26 to the end. So if every -- you have an N letter keyword, six in this case, and each of those letters can be A through Z through any of 26 possible letters, you've got 26 options times 26 option, times 26, so that's 26 on the N. And then if I relax the constraint that the key is six letters, and I say ehh, the key is any number of letters, then you have even more. You have 26 to the 2, plus 26 to the 3, plus 26 to the 4, so in short, the key space is a lot larger. Now ultimately you could still crack the Visionaire cipher by a few ways. You could do some intelligent manipulation, you could look for patterns, for instance, you could do frequency analysis. Some fairly sophisticated heuristics, or you could try all possible keys. Start with all the one letter keys, then once you've tried all those and gotten back non sense, try all the two letter keys, the three letter keys. And that algorithm, though naive, would eventually work, at least in theory. If you have enough time to wait around. Unfortunately, these days, when you've got two gigahertz of power underneath your own desk or your laptop, you can churn through a lot of keys very quickly, and in fact there's this algorithm called DES, D-E-S, and this is actually an algorithm that's used in the function that's typically used on a Linux or UNIX or Mac os system, still today, to encrypt your own passwords. So you've got a user name and password, maybe on your own computer, certainly on Nice dot F A S dot Harvard.edu now, and your password, fortunately, is stored in encrypted fashion, and this is why, for instance, the user assistants, beg them as you might, cannot tell you your password if you forget it, because the system stores it in encrypted fashion. So this algorithm, this function called DES was used for some time, many years after Visionaire, but in more recent modern times, and there were with DES 72 quadrillion possible keys because of the number of bits used to encrypt something with this particular algorithm. Now we won't go into the specifics, I put this little snippet from a text book to just kind of hit at the relative complexity of this. Visionaire is very simple, you can do it paper-pencil. DES starts to take a computer or calculator, as all of these arrows and this flowchart generally implies. But a computer can compute DES-encrypted text fairly quickly. Unfortunately, too quickly. So the reality is these days if you encrypt something with DES, you know, if someone has enough time and enough CPU cycles at their disposal they can crack your password. And that's in fact, exactly what Problem Set 2's hacker edition is all about. Now this is you know, interesting maybe fun in the context of passwords on some random university's system. It's a lot more worrisome, if random people, students in CS 50 with a laptop on their lap, can crack information that has been encrypted with something like DES. DES is not very secure any more. 56 bit keys, as it once used, no longer very secure. So there are variants. In fact, someone came up with the bright idea of not just using DES, but let's run DES three times, call it tripped DES or 3 DES. And that actually is a little more secure, but not terribly so. So the world has come up with more sophisticated algorithms. And if you take or have time to take over your years here computer science 120, and there's a cryptography class, and there's some graduate level ones, it's really interest space. But the funny thing is a lot of the security of today's cryptographic mechanisms ultimately boil down to assumptions. The safety of them boils down to assumptions. In other words, there is this algorithm called R S A, and you might have seen this listed to various web sites, you might have heard of this algorithm before. It basically boils down to a really fancy way of allowing web sites to communicate with browsers securely, but that's just a specific case. You can use it for far many more interesting purposes; ATM machines, bank transactions, a whole bunch of interesting stuff. But it ultimately, the security of R S A, whether you're using keys that are 56 bits long, which is pretty short these days, or 128 bits long, or 1,024 bits long, ultimately, whether or not this algorithm actually works reduces to whether mankind can come up with a fast way of factoring large numbers. So again, long story short, this algorithm called R S A boils down to assuming that mankind, and their computers, cannot take a really big number and factor it really quickly into two large prime numbers. So put another way, if you want to encrypt some information and you want to use an algorithm like R S A, you take two really big prime numbers, and it's not hard to generate prime numbers, even big ones, it's not hard to multiply them together. But it is much harder to undo that process, when all you do is hand an adversary or hand a computer a really big number and then say hey, this just so happens to be the product of two really big primes, tell me what they are. We, thus far, have not come up with a relatively fast way of figuring that out. It will take more units than we have in our lifetimes, for instance, to make sweeping generalizations. But the key is, no pun intended, that there is a lot of interesting opportunities to improve upon or even break some algorithms that the world itself is now entrusting our money, our security, and a whole bunch of things too. To give you a sense of what a bigger key looks like. So this is intentionally rather small and deliberate, this is a key, a really big number, that happens to be represented with alphabetical characters and numbers, just for efficiency's sake, that represents a key one might use with an algorithm like R S A. This is a lot bigger than a number from 1 to 26, this is a lot bigger than a word like foobar. So this hints at the types of security that's actually in use today. And so that's where we pick off -- pick up today. So we spent a lot of time in the past couple of weeks talking about syntax and C and programming, now finally that we've gotten some of the minutia out of the way, what a for loop is, what a while loop is, and granted, you might still need another week or two of practice to get comfortable with even those syntactical details, we finally now have the ability to start talking at a slightly higher level about how you actually start to think more effectively, as the syllabus and course catalog claims, how you can solve problems more efficiently, as is the other promise made. And we started this course with this sort of visually interesting example of taking a really big phone book, and I claim I could find Mike Smith much faster than say a completely naive person would, by starting at the front and flipping through the As, and then the Bs, and then the Cs. Because I took this approach of dividing the problem in half and conquering only half of it. And then I realized, oh, if Mike I know is in the right-hand side of the phone book, let me do this again, and split the problem again and again. And our take away was that if that phone book, and it pretty much was, a 1,000 pages or 1,024 pages, how many times would I actually have to split that problem in half to find someone like Mike Smith. So just ten, right? If you have 1024 pages, and you just do the math in your head or on a piece of paper, you can divide that number in half ten times. Now there might be some interesting rounding issues at the end when you get to the last page, but ten times, instead of 1024 pages. Suppose that phone book, as we said in week 0, were not 1,000 pages, but 4 billion pages, that's a hell of a phone book, with a lot of names in it. But how many pages would I actually have to look at. How many times would I have to chop a 4 billion page phone book in half. 32 times. Why? Well, you can take 4 billion and divide it in half roughly 32 times. And that speaks to the power of actually designing algorithms intelligently, that speaks to the power of what you can do with this basic device and just a modicum of intelligence inserted into your algorithm. Right, if I told you to search a phone book right know, you could certainly recently through how you might implement, divide, and conquer, but by far the simplest way to implement search for a phone book using the syntax and the capabilities of C you have now is what, like, write a for loop, I gets zero, I less than or equal to 4 billion, and then just check from I on up to 4 billion whether or not someone is in the current variable or in the current array or however you actually code it up. You could implement that with just a few minute's time. But that thing's going to take a while to run. By contrast, put a little more thought up front and the algorithm itself will execute far more quickly. So we're not going to stand up and indulge in this again, but this is an instance of the same idea. The first day you all stood up, you paired off with someone, and then half of you sat down, then half of you sat down, then half of you sat down. Now, granted, that turned into a bit of a disaster, as is often the case. Took way longer than for me to just go 2, 4, 6, 8, 10, 12. But in theory, had there not been the social awkwardness, had there not been the problems with arithmetic, we would have been able to -- you would have been able to count the people in this room so much more quickly than I, because whereas I'm sort of going like this, 1, 2, 3, so with every CPU cycle I'm doing one thing, you, by contrast, with every toll of the clock, with every CPU cycle, half of you were sitting down. You were taking a half -- 50% of the problem out of the room at once. Where I was just taking one nth of it out of the way. So this too has implications. So this is just a fancy way -- I whipped this up with Excel -- to depict the following idea. So on the X axis here is this number N, which generally is going to refer to the size of the problem, how many pages are in the phone book. Let's call it N. How many students are in Sanders. Let's call it N. So I have from zero on up to 130. And then on the Y axis I have what I call T of N, the running time of an algorithm whose input is of size N. So it's just a general way of describing the running time, how much time does it take for an algorithm to run, and what do we mean by time? Like steps or seconds, minutes, whatever, so long as we all agree what the metric is. And these different lines represent different running times. So at the top left, we have a little legend there. It's kind of small to see, but we have three graphs here. One is this one up top. So on the left-hand side we have a very steep curve, but this is a line, this is a linear graph. And this represents an algorithm that given A inputs takes N steps to run. And that is representative of the running time of 1, 2, 3, this linear algorithm of counting students. But we realized in Week Zero we can do better, right? We can actually sped those up. So the second graph there, the second line that's a little bit to the right of the first one, that would be the result of my doing 2, 4, 6, 8. It's actually twice as fast, now contrast this with your line, so log of N, as we described your algorithm that day, as we described this general principle of divide and conquer. What this means is your algorithm should take way less time. In other words, the more students are in the room, look at the contrast between how many steps or how many seconds, how many units much time your algorithm should take versus mine, which is literally off the charts. Now what does this mean? If we add -- if one more student comes into this room that takes me one more step. If one more student comes into this room, that's kind of rounding error for you. Because you can kind of assume that one additional student. So let's actually take a bigger -- let's increase the problem more significantly. Suppose we have roughly 2, 300 students in this room. Suppose another 200 or 300 students come into this room within the next few seconds. Well that's going to take me literally twice as long. If it took me N steps before, it's going to take me 2 N steps by doubling the size of the room. Now my contrast, if 200 or 300 more students enter this room in the next few seconds, how many more steps or unit of time does it take you to count those additional students? Just one, right? Because within the first iteration of your algorithm, those same kids will sit down right away. And that's a huge bite out of the problem, whereas mine has grown significantly. And that's the fundamental contrast between something that's linear, like in my case, and something that's logarithmic, or at least mathematically more interesting. And not to overwhelm with numbers, but just to give -- put concrete values on what the implications here are, this is just a big chart that computes some very basic functions. So in the left-hand, the third column here, right above where I'm standing, this is N, so we arbitrarily have 1, 2, 4, 8, 16, a whole bunch of values of N. So my algorithm, 1, 2, 3, 4 -- if we have let's say 1 million students in this room or 1,048,576, that's obviously going to take me 1,048,576 steps. But my contrast, if you scroll back to the left, and you can do this, you know, with a calculator or even in your head perhaps, that same student body of a million students in Sanders could be counted by you all in just 20 steps. And so the take away visually of a graph like this, and we'll revisit this or you can revisit this as we introduce yet more algorithms, is exactly how significant the implications are of well-designed algorithms. And we can zoom out even further, if you look at various graphs like these three here, the specifics are not so interesting today, but notice this last one here. So it's small to see, but that big curve that's going to the north there is called 2 to the N. 2 to the N being an exponential function. So we'll talk about it at times and in future classes if you take other theory classes in CS, even just for fun or if you're minoring in CS, you'll find that exponential algorithms, very bad. Because as N increases they take a ridiculous amount of time. But back to our motivation today of cryptography, when we say it's really hard to factor large numbers quickly, what we mean, essentially, is that factoring large numbers generally boils down to something that takes exponential time, not linear, not quadratic, not polynomial, if you recall the terms, but exponential. So graphs like that, very bad. Takes a good amount of time to run. So how can we start to describe the running times of algorithms. Right? It's sort of -- it's easy enough to pick a few examples, talk about which one's better, why it's better, and steps it takes. But can we generalize. Can you start to look at your own code or your own programs and say this algorithm is good because it takes this amount of time, or this implementation I wrote last week sucks because it takes this much time in general. Can we slap some labels or some formalities on just so we can start comparing algorithms against one another, even in different languages or written by different people. Well, there's three basic constructs, three little pieces of jargon we'll start using. One is called big O, one -- and that's the guy at the top. The middle guy is called theta. And the bottom is omega. And these symbols are just generally used by mathematicians in computer science to express the running time of algorithms. Now what does this mean? So formally, it means this. And these slides are on line, if you like the mathematical formalities, because there's actually some juicy ideas in there, but for today, they reduce to some relatively simple ideas. If you have an algorithm that in the worst case takes N steps, you say that that algorithm is in -- you say that that algorithm is in big O of N. So this is the worst case running time of time linear algorithm of counting students, and as an aside, happy birthday to Jansen and Mike. If, though, your algorithm in the best case might actually take fewer steps, well then you start talking about omega notation. Now in the case of counting students, this really doesn't help us, because in the best case how many steps is it going to take to count N students? Well, N. Right, I kind of have to count everyone. In the best case? Well, if I want to count all of the students, it's still going to take N steps. But let's pick another algorithm arbitrarily. Suppose students file into the room, I want to search for a student named Mike, just because. So in the worst case, how many steps will be take me to find a student named Mike as they file in the door. All right, so N steps. Because in the worst case, the Mike or the several Mikes we have in the course this semester are just -- just so happen going to be the last people coming into the room. Just by chance. But in the best case, where might Mike be in the line? First, right? Common sense. So in the best case there we say that algorithm of finding Mike, searching for Mike, is in omega of 1 in the best case, just takes one step, bam, I ask the question, I get the answer I'm looking for right away. So when you have an algorithm that's both in big O of N or omega of N, so not the searching but rather the counting, then can you say that that algorithm is described by theta of N. So in short, we have worst case running time up top, we have best case running time at bottom, and if those two just so happen to be the same, then you can say that the algorithm is in theta of whatever formula you've come up with, and in that case. All right, so what does this mean exactly? So in the case of a phone book, when I tore the phone book again and again and again, and what was the running time of finding Mike Smith or really finding anyone, for that matter, in a phone book that happens to have N pages? In the worst case, searching a phone book takes how many steps? Okay, so log N, if my algorithm is to just start at the first page and go from left to right all the way to the end of the phone book. So that might be one implementation, and this will be say, linear search of a phone book. But we can do better. In other words, if I want to compare one algorithm, the linear algorithm that we started class within Week Zero versus the more intelligent one of divide and conquer, divide and conquer worst case running time is instead what? Log N, right? Because we said multiply times now that in the worst case we're going have to keep chopping the phone book in half and half and half, until we get to one page where Mike Smith is finally listed. How many times can we do that chopping? Log in time, so this is something that we'll call logarithmic. All right, what about the best case running time of the phone book searching algorithm? Yeah, right? Because in the best case -- and again, when you talk about an algorithm, you talk about a general input. We don't talk about an algorithm for finding Mike Smith, we talk about an algorithm for finding someone. Well, the best case running time of finding someone in a phone book whether you use the linear algorithm or the logarithmic one ultimately boils down to just constant time, right? Because you might be looking for Abigail Adams, who just so happens to be on the first page of the phone book. Bam, you're done, you don't even have to divide the phone book in half multiple times. And we'll call the running time of that algorithm constant, whether it takes one step, maybe it takes two steps, because there she is on the page, now I have to find what row she's in on the page. But those are just a constant number of steps, so we're going to generalize as just constant time. So what's the point of all this? Well, we now, just as we did, have this means of comparing not apples and oranges, per se, but apples and apples. If we have two different algorithms, linear search and then divide and conquer for the phone book, we can now say something qualitatively about which one is better in terms of its running time. And the notation folks tend to use for exactly that, is this notation here. So just to toss out some jargon in case you see it anywhere, constant time we discussed, logarithmic time we discussed, linear time we discussed. We'll see this running time often, N log N. Frankly, in 12, 15 years of computer science I've never heard one human say supra linear, but that is in fact the formal term. N squared, we'll see today and-or Wednesday. That's called quadratic. More generally, if you have N raised to some power, that's a polynomial. And then there's N factorial, which is even worse than any of those, but you tend not to see that unless your algorithm is frankly downright stupid. So couple of announcements. There's one hand out today, very little code, but nonetheless, it's out there. Lunch seems to have gone well, so we were kind of overwhelmed by responses. We ended up having a barbecue for 60 of your classmates. So we'll try to do another such thing some future Friday, more on that in a future class. If you've not yet returned sensor boards from the hacker edition of P set 0, that's fine, just hand them to one of the TFs in our little nook over here. P set 2 went out the door on Friday. The walk through was filmed yesterday, on Sunday, that video will go on line by tomorrow. Office hours have been in progress, do take advantage of those, and sections have already begun. So your assigned section, you should have been informed of by e-mail. Either you went last night or your section is probably today or tomorrow, so do take advantage of those as well. And we also deployed per Problem Set 2 this link on Friday. So there is now the bulletin board, which if clicked will log you into a little interface that looks like this. And the bulletin board is meant to serve a couple of purposes. One, it's meant to allow us to answer the same question once for many different people to benefit from the answer. It's meant to be an opportunity for you to potentially field each other's questions, so long as it doesn't cross that line of outright telling someone some answer, and what you'll find is that week to week we'll add another category to the bulletin board for P set 2, P set 3, P set 4 and so forth, and the goal of the bulletin board is to ask questions that you're pretty sure anyone can hear the answer to, anyone can see the specifics, but if you find that asking your question really requires that you show us your code, then continue to use help at CS.50 for that, but what you'll find more importantly, especially for those less comfortable, when you log in for the first time although it does authenticate you with user name and password, we have made your name the default value of students. So you can have that pseudonym, you can change it to something other than that, your own name or something fun. But realize the point of the bulletin boards, anonymity is so that you can post what you fear is the proverbial dumb question, and no one else, other than the staff as necessary, is going ask that you even asked that question. So if that gives you more comfort, by all means, ask for questions in that way. That was a lot to absorb, let's take our five minute break.  
 
[ Background noise ]  
 
>> All right, we are back. So we do the following with key note. We have eight doors here, behind which are little surprises. To reveal what's behind these doors, though, I need to solicit the ever-awkward volunteer to come up on stage, if you will. Yeah? Come on down. Again, you'll need to sign your rights away in perpetuity in a moment. Come on up. What is your name?  
 
>> Edward.  
 
>> Edward, okay. David. Nice to meet you. Got a fan over there. All right, so Edward, much like a game show, we have the same doors -- oops -- [Inaudible] will spoil the surprise. So we have eight doors behind these pieces of paper here. So we have two arrays. So I'm going start using the geek terminology. So we have two arrays, arrays of integers. Each is of size eight. And you are now just a human who's been presented with a very awkward situation. The goal of which in this top array is to find me the number 3. And what we the audience hope to learn from this is exactly how you the human go about solving this problem. So if you would, on the top row only, find us the number 3, please. See the number 2. Oh, that was very good. See the number 3. Okay, so if you would, can you explain how you found the number 3?  
 
>> Just went up, [Inaudible] pieces of paper at random.  
 
>> Okay, so that was just chance, then, it was not spoiled by the wind.  
 
>> Right. Systematically go through and check all the paper.  
 
>> Okay, good. So thank you, first, for spoiling my demo by finding it so quickly. So -- but let's ask the question nonetheless. What is the running time of the algorithm that Edward just tried, can we slap a label on this. Best case running time. It's apparently two, but one in the truly best case, so this is in omega of 1, we'll say. In the best case, he just happens to go straight for the right number, just by chance or by some more sophisticated heuristic. And in the worst case, how long would it have taken you to find the number 3? Okay, 8 or more, generally big O of N. So again, we have an algorithm that's big O of N, or omega of 1. So the question now at hand is can we do better than that. So let's see. How could we fundamentally improve upon that algorithm, any suggestions for Edward. Could we do better than big O event. Because big O event is great when it's only eight, but if N is now 4 billion, as we've discussed, N, not so good any more. Sorry?  
 
[ Inaudible audience comment ]  
 
>> Okay, so we could sort these things, right? There is an advantage that we had all this time since Week Zero of a phone book. Someone else, Verizon or whomever, has done the hard work of sorting that phone book alphabetically so that we can make certain assumptions. An assumption like when I go down the middle and end up at the Ms or the Ns I know the Smiths, the Ss, are going to be to the right. Now I didn't give Edward any such assumptions, and in fact, it's a little weird that 2 is over here, and yet 3 is over here, kind of suggests that maybe these things are not so sorted. And in fact, there's 8, there's 1. So the top row is not in fact sorted. So if we now give you the added assumption that the bottom array of 8 numbers is in fact sorted, how might you go about, without answering, just doing, finding the number 50 in the bottom array. Different numbers, but they are now sorted. I see 171. Dammit! Okay. Okay, very good. Okay. So what did you do this time?  
 
>> Well, since you told me it was sorted, I assumed it meant it was either -- there was going to be some sort of pattern. So either the larger numbers were on the right or on the left. So I checked both sides.  
 
>> Okay, good. So as an aside, this demo was far more effective last year when we spent like 10 minutes on this. It was somewhat awkward, actually, because your predecessor spends a lot of time thinking about which number to reveal, thinking there was perhaps some trick to this, when really, five minutes before class I had written random numbers on the board. So you're doing much better. He was a good sport about it. Okay, so bottom array is now sorted. Let's slap some numbers on this. Best case is apparently two again, in reality, but formally or asymptotically, any time we start talking about big O and omega, we're talking asymptotically, which means as inputs get large, as N gets large, what generally happens to running time. So in the worst case, how long would you algorithm have taken. Okay, N, because why, what was your algorithm here? You said I went high, I went low, but we didn't really get to see what you would have done next. In fact, let's continue this. Find me the number 52. I see 51. I see 61. Good. Back on top. Okay, so pause there, because we know you're going to struggle now. So what was your algorithm? Now we have to push a little harder.  
 
>> So I was assuming they were sorted numerically. So that --  
 
>> Okay.  
 
>> So when you said 52, since I new 50 was already down there, I just went to the same row.  
 
>> Okay, good. So in short, I can summarize. So at first you went high because 50 is a pretty big number, certainly relative to the number 3 we looked for before. So you went high, didn't find it, then sort of thought maybe I was messing with you, so went left to look for the number 50 there. Didn't find it, but you did know it was sorted. So the rest of your algorithm after this guess work at the beginning, try high, if not high, try low, was presumably to iterate then from left to right. Okay, so we can still slap some formality on this approach too. In the worst case, how many steps would that take, as you said. N steps, right? Because maybe you went high here. Okay, that wasn't 50. Then you went low, not here still, then you end up iterating over the N minus 1 remaining elements, okay, big O event. But again, best case running time is omega of -- in your case there, is just 1. So in constant time. So this sort of begs the question then, how long did it take me, the person setting this up, to actually sort these values. So let's put you out of your awkward [Inaudible] round of applause if we could.  
 
[ Applause ]  
 
>> Legal form awaits. Okay, so that begs the question, then, how do we actually go about sorting these values. Because I kind of did it for free. Right? I did it before class, kind of cheated by having the numbers pre-baked. But if you're just handed a bunch of numbers as Edward effectively was, and I left it to him to sort those values so that he could then impress us with the running time of his better algorithm, how much time does it takes to sort these numbers. Well that, we'll see, is a much harder question to answer and a much more time consuming problem to solve. But let's see if we can express now what Edward kind of did or in an ideal world would have done exactly. We can express this algorithm, or really any algorithm moving forward in the course, not just in C code which gets fairly pedantic, writing out all the minutia, we just want to convey the idea of an algorithm, just like we did in Week Zero and One, we can go with pseudo code. There is no formal standard for what pseudo code is, different people take different approaches. The only important thing is to communicate your idea clearly without getting bogged down in stupid details like semicolons and parentheses, which add nothing to the logic and only distract from your idea. So I took the somewhat conventional but somewhat arbitrary approach of defining my pseudo code as follows. For linear search, as I called it, and this is what the world generally calls an algorithm where you start from here to here to here to here, and move from left to right, so on input N, for N elements, for each element I, if I equals, equals N, return true. So on input N, for each element -- yup. So this is -- there are many different ways you can implement this pseudo code or write it, but it implies that there's an array of some sort, but syntactically, doesn't matter how we express this. So I'm going to take the approach of saying for each element I in my array, if I happens to equal N, the thing I'm looking for, go ahead and return true. But then per the indentation, if I never return true, the last line in my program says return false. And the answer is no, as was the case when Edward failed to find 52 because it just wasn't in that second array. But we can do what I was hoping he could do, but it is okay, I can do it myself, we can implement what we might call binary search, which is actually direct application of the whole divide and conquer idea. Now this algorithm looks at first glance certainly more complicated than linear search, but we've already seen how much time it saves on things like searching phone books and what not. So in theory, if I were searching for the number 50 here and I didn't have this heuristic of going high or going low, because maybe that would work, but even Edward had to make a guess, is 50 big or is it a small value. Well in this case, it was actually relatively small value, because we had 50 here, but then 171 here. And in the end, although it was a clever trick, and he actually solved that problem very quickly to his credit, the algorithm itself, ultimately boiled down to no better than just linear search. Because in the end these clever heuristics, which in the real world clearly saved us some time, and garnered him some applause, the rest of the algorithm, had he not been so lucky, is still the same linear algorithm. So what if I instead apply the Mike Smith approach. I go into the middle of my phone book, the middle of my array. And now I'm looking for the number 50. Well, we have some weird mathematical rounding errors that I'm sure we can work out with the rounding function or ceiling or floor or whatever, so I'm going to arbitrarily go here. Is this the number 50? No, it's the number 105. But just like in Week Zero when I was able to tear away the problem of the phone book, I now know that my answer is definitely not going to be to the right. So I can focus only on the remaining numbers here. Where do I go next? Well, I think essentially the same problem. I'm still looking for the number 50, I've still got an array, upside is half as big as it once was. I can use that to my advantage performance-wise, so let me just go smack-dab into the middle. I've got to pick left or right arbitrarily, because the math isn't working out beautifully, so let's pick this one. 51, not the case. But now I know it's this way. So now I know it's not here, 51 or 61. And I'm left with a problem that's a quarter of my original size. So already, fundamentally, I'm definitely moving faster than Edward would have, given many more elements in his array, which clearly is going to the case when we have more room and more interesting problems. So I've got two elements left. I arbitrarily go right, as I've been doing. Aha, the number 50. Now, granted, and this is actually a use full take away, granted, my algorithm was slower than Edward's. Edward took two steps. I took three steps, and yet I'm going to make the claim, arrogantly, nonetheless, my algorithm is better because as N increases, asymptotically, the bigger and bigger N gets, the more and more you'll be impressed by the running time of my algorithm, and more and more Edward's algorithm, in all fairness, just devolves back into a very slow but correct implementation of the same idea of search. Now as an aside, for the astute, this just so happens to be all of the computer science courses you're qualified to take after or before C S 50. So keep that in mind at shopping terms -- shopping periods time. But for now, the take away is that very subliminal, I know, maybe it's not subliminal if I tell you what they are, so for now we just need a way of expressing this. So there's many different ways we can express this. This is what I would call an iterative implementation of binary search. Thus far in the class we've only talked about phone books and splitting them in half, throwing half away, repeating. But now you have this ability to program a machine, you kind of start -- you need to start expressing yourself more precisely. You can't just tell the computer find me the number 50, or 52, you need to tell it how to do that. You need to teach the machine, so to speak. So one way we might imply that in pseudo code is as follows. On the input of an array, where we call it array bracket zero on up to N minus 1, so the length of most any array we ever discuss now is N, but the largest element index is obviously N minus 1, we start counting from zero, and input K, where K is the value I'm looking for. I kind of need to implement this idea of binary search. So I'm going to define in italics here a variable called first. And initialize it to zero. I'm going to define another variable called last, and initialize it to N minus 1. And what the subsequent steps do, if you think it through, as a future Problem Set may ask you to do, it's going to ask you to implement very precisely this approach. Here's N elements, I'm going to use my left hand as my left variable, my right hand as my right variable, and what is it telling me to do on the first step? Well, while first is less than or equal to last. So good, my left hand is indeed less than my right hand, because it's to the left of it. What do I do? Let middle equals first, plus last, divided by 2. So what that math does for me is if I add this index and this index, divide by 2 and take care of the rounding, that gives me a number in the middle. Let's say 105 for now. So middle equals that element there. So if K is less than the middle element in the array, then let last equal middle minus 1. All right, so I'm looking for the number 50. So 50 is indeed less than the middle element of the array. So what do I do? Well the then condition says then let last equal middle minus 1. Here's last, here's middle, here's middle minus 1. And already in one iteration we've seen how to translate a very simple idea, right? Split the problem in half, in half, to something much closer to what GCC could understand, much closer to what you could actually code up in nano. And if you follow the logic there, what you'll find is that iteratively [Inaudible] my right hand, keep moving closer to my left, sometimes my left goes closer to my right, if my hands ever cross what's the implication, presumably? That it's not there. I'm looking for 52, and you know, I went too far to the right, too far to the left, my hands cross because it's just not there, or I end up smack dab on top of the number I'm looking for. Whether it's 50 or 52. But what we've sacrificed here is this beauty of the original algorithm. What's really cool about divide and conquer is it's so damn simple to explain. Take the phone book, split it in half, look at the elements. If it's less than, go left, if it's greater than, go right. Repeat. There's this elegance about this, where you just say divide the problem in half, check for something, and then repeat, repeat. This really clouds some of the simplicity of that algorithm. But we have this ability, it turns out, in C, and in Java, in C++, and all of these languages, particularly ones like Lisp and Scheme, which you could cover in C S 51, of this feature of recursion. So it turns out that whenever we've said something like repeat, you can repeat by essentially applying the same algorithm again. Now thus far in C, how do you implement an algorithm? Well, you write a function like cipher or Caesar that implements some algorithm. So if we ever have to express this idea of repeat, maybe we can have a function just invoke itself again on a smaller piece of the puzzle. Well, what do we mean by that. Well, let's take a look at this very simple program. So this is sigma 1.C, this is one of today's two print outs, two pieces of code that's printed out. So this is going to be a function that returns that an int it's called sigma in homage to the little symbol from your math book that looks like this, and just implies summation. So I want to do this. I want to sum up all of the numbers from I equals 0 to M. So if I want to express this like the back of a high school math book which, this is I equals 0 on up to M of I. So I just want to compute the sum of all the numbers from 0 up to M. Okay, so not an interesting problem, but it's interesting how we can solve it. So here's one little sanity check. When we said last week you better get into the habit for your own sake and your program's sake for error checking, you've got to do sanity checks like this. Just because the function is going to be passed in int per the definition, per its signature, so to speak, per its declaration up here, that doesn't mean it's going to be an int you want. It might be negative. It might be zero. Neither of which we want if we're trying to sum up positive values only. So I'm going to avoid the risk of an infinite loop by just doing a sanity check. If M is less than 1, return zero. So here's an interesting feature of C and a lot of languages. If you have to somehow signify an error condition, some languages, as you may know from high school, like Java, have this thing called exceptions where you can kind of raise a red flag and not bother returning a value at all. But languages like C require that a function return a value, generally. In this is case an int. And sometimes you need to return what we called last week a special sentinel value, a special value that the person calling your function had better check for if they want to see if your function worked correctly. So it's not sufficient for a function like this to just print out warning, M is less than 1. Because how is the code that called this function going to know that an error occurred, right? This is the point we were trying to make last week with side effects versus return values. A human can see side effects. A computer can only see return values. So if we're trying to write code that calls this function and I want my code to be able to check if an error happens, I can't rely on print def, I have to rely on return values. So what value could I return in the event that the input just doesn't make sense? Well, here I arbitrarily chose zero. What might have been another reasonable value to return to signify essentially error? Negative 1, why? Well just because. If you return a negative value clearly the caller, the function that called this function can infer by getting back a negative number when the whole point of the exercise was summation of positive numbers, that something went wrong. So think too, back to last week when we mentioned very briefly, because we'll come back to it, that get string sometimes can return a bogus value or not return a string per se. It can sometimes return a special sentinel called what? This was null, so we'll see this many more times, it hasn't really come up, but N-U-L-L in all caps is a constant that signifies, there is no string, but I'm a function with a return value, I have to return something. So when you start consulting man pages later in the course for new functions that you might want to employ, you'll need to check the section of the manual that says what return values does this function have, because sometimes you want to check with your own little if condition, did I get back a value I care about. Well, this code is easy. Now once I've done this sanity check and I want to sum up the numbers from 1 through M or equivalently 0 through M, I'm going to do this, I'm going to declare a variable called sum, it's going to be a type int, and I'm going to initialize it to zero. I'm then going to iterate from I equals 1 all the way up to M -- equals, less than or equals to M -- and then I++, and then what does this code ultimately do? It just sums up all the numbers from 1 to M or 0 to M. All right, so if I see this in action, let me go ahead to a terminal window here. I've got -- let's go ahead and open a new one, let me go ahead and SSH to nice.fas.harvard.edu, and if I go into my CS 50 directory, okay, Lecture 3, Week 3, okay, sigma one. So this is the same exact code. Notice -- oh, why do I have this at the top of this file? What's the point of significant -- declaring sigma as a prototype up there? Yeah, so remember from last week, if you are calling a function that just so happens to be implemented later in the file but you're trying to call it from main, which apparently I am, so this was not on the slide a moment ago, but apparently I am calling sigma from main -- it's a stupid detail, but you've got to proactively tell the compiler hey, there is a function in this file called sigma, it returns an int, it takes an int, just know to expect it eventually. And realize this too. It turns out that when you declare a prototype for a function, you don't have to provide the names of the variables, all the compiler needs to know at that point in time is what types of variables it has as arguments. So you can literally just write inter, or if it takes two arguments, int, comma, whatever. So either approach is fine. I could have specified the name of the variable up here with int-M, but it just isn't necessary. So I tend to be fairly minimalist when I write the code. All right, so here's the function down there. And notice one other detail, just to make this more compelling. Why did I not do this, because this was a question asked, I think on the bulletin board this weekend. Why did I not do -- say, this. Probably a couple problems here. What's one, yeah?  
 
[ Inaudible audience comment ]  
 
>> Yeah. So there's a logical error, declaring int, reinitializing sum to zero every time. So that's not good. What if I did this, as I've seen before. I can sometimes initialize two variables to a value in my for loop. So that seems to be okay. But what kind of error am I going to run into next. Some of you may have -- yeah? Oh, this is -- don't stretch like this during class. Okay. Yeah. In the back.  
 
[ Inaudible audience comment ]  
 
>> Exactly. Remember last week's discussion of scope. So generally, when you declare a variable, say inside curly braces, or in this case, inside the for loop, that variable only lives inside of that for loop, which means this math is perfect. We initialize sum to zero, we keep adding to sum I, but the moment down here I try to return sum, my compiler is going to complain to me sum not declared, even though it is, because it's outside of the scope. So it was very deliberate a moment ago when I declared this variable outside of the loop so that it would remain in scope the entire time. All right, so let's go ahead and save this. Let's make sigma 1. I'm not going to bother typing GGC and all that, because this handles a lot of the magic for me now. I'm going to go ahead and dot slash sigma 1. Be ever so clear for security reasons that it's in this current directory. Enter, positive integer please, let's say 10. Hopefully, that's correct. 9. All right. Let's do one I can check quickly. 3. Yes, I'm pretty sure that 3 plus 2 plus 1 equals in fact 6. So feels like this code is correct. But turns out we can implement this in a very different way. How it this function get called first? Well, here is an example of where do while is useful. We said last week -- we said last week that do while is often useful when you want to ask the user for something, give them a chance to give it to you, and then reprimand them or ask them again if they fail to provide what you're looking for. So here's exactly that scenario. Declare an int called N. I'm going to do the following. Tell the user positive integer, please. I'm going to then use get int from the CS 50 library to get the int. And then right here rather elegantly am I going to check within my while construct, if N is at this point in time less than 1, do it again, and do it again. So this is a general approach, do while, to getting user input and the result to be clear is if I try messing with the computer and say negative 123 or negative 6, it's just going to keep pestering me. But remember, my random word of last week, monkey, why does it say retry instead of positive integer here? So this is [Inaudible] to get int. So as the name get int implies, get int will do its best to get an int from the user, but it doesn't guarantee it's going to be positive or negative or anything like that. It just gets you an int. So turns out we can implement this same function in a really interesting way that hints at the beauty of this thing called recursion. A function is recursive if it calls itself. Now on first glance or first hear that might be a little worrisome. If I'm a function and I got called with an input, and I try to solve that problem by calling myself, that should immediately should infinite loop, bad stuff happens. But hopefully there's some way of making sure that you don't keep calling yourself in perpetuity, and there is. It's called the base case. So notice this implementation of Signa is only four lines of code, and frankly, if I got rid of some of the indentation, all that, it's maybe like a two line program, maybe a one line program that implements exactly the same function, exactly the same formula of adding numbers together. So what do I do? On input M I ask myself is M less than or equal to 0. If so, just return 0, because bad things will happen if I start trying to deal with negative numbers. Now apparently all I need to do to answer this question is call myself. And this is where you get this weird sort of circular magic. Notice that all I do otherwise, after my base case, after my sanity check, is return the result of M, the value I was passed, plus sigma of M minus 1. Now that alone actually works. If I go back to my terminal and I compile sigma 2, and I run sigma 2, and I give it the number 3, I get back 6. If I give it 10, I get 55. In fact, it works, and yet how is it doing that? Well, let's see. So it turns out that this problem of adding all the numbers from 0 on up on M, or equivalently M all the way down to 0 is pretty easy, even conceptually. If you hand me the number M and ask me what's the sum from M down to 0, well, I could say, all right, well, it's M plus the sum of all the numbers from M minus 1 on down there. All right, so let me ask you again. What is the sum of M minus 1 on down to 0. Well, it's M minus 1 plus the sum of M minus 2 all the way down to 0. Right? You can be this really argumentative human pushing back on the person in wise-ass form, oh, well, it's just the answer of M plus the rest itself. Well, what's the rest of it. Well, it's a little bit less than the rest of it, plus the rest of that. Right, you just keep taking this bite, this bite, minus 1 out of each piece of the puzzle. And that would seem to go on forever, but not quite. Because eventually when I get over here, my last piece of the puzzle is going to be M equals what? Zero. And that's when I hit the so-called base case, when all of my answers now start to bubble up. In a sense, I was kind of passing the buck by playing this game with the person asking the question, well, what's M plus all the numbers below it? Well, it's M plus the sum of all the numbers below it. What's the sum of that, right. Eventually, we bottom out at zero, and then I finally start getting useful answers back until the M result is precisely the same. But what's been the point of all of this? Well, and again, this is something that you perhaps begin to see eventually, and maybe you never see, but there's kind of a beauty about expressing something as silly as addition of numbers with just this recursive scenario. And this will be a very representative approach to solving much bigger, much more interesting problems. But there is a catch. Let me go ahead and run sigma of one, my first version, on 100. That works pretty well. How about 1,000. Works pretty well. How about 10,000. Still working. 100,000. All right, then eventually I'm going to start to exhaust an int. Okay, so now I exhausted the int, but we would expect that. Let me try now to run sigma 2. So it's a more elegant solution, feels like it should be even faster because there's just frankly fewer lines of code, well, let's see what happens. Sigma 2 -- oops, 10. That works, how about 100. That works. How about 1,000. Still working. 10,000. All right. 100,000. Okay, come on, break. Oh, now some of you have seen this problem too. And we actually smiled. So in all fairness to the anonymized student asking the question on the bulletin board, is it okay if my program quits by saying segmentation fault, [Inaudible] dump. No, so this is a bad thing. Bless your heart for asking, but this is not a solution to the problem. This is, as I said in the bulletin board post, frankly -- or maybe -- actually, maybe this was a private e-mail, as I said in my response -- as I said in this response this is sort of the LINUX equivalent of Microsoft Word just hanging, or your Mac program just freezing or unexpectedly quitting, which is ever so annoying. This is sort of the equivalent in the LINUX world. But fortunately, now that we're the programmer and we're not just the user, the fact that it's dumping core, so to speak, is actually useful. So for today's purposes, segmentation fault means something bad happened with respect to memory. Because memory in your computer is generally modeled as a bunch of segments, so a segmentation fault means something went awry with regard to memory. Core dumped means that something useful was left in my current directory. If I type LS for list, notice that I have this file called core. Core is actually a file containing pretty much the contents of the computer's RAM at the moment in time when my computer screwed up. Now it's not all of the memory from all users on the system, because that would be a security concern or privacy concern, but it's diagnostically useful, we'll see in a week or so once we start dissecting the insides of that file. But for now the question is quite simply why it this happen, why did it not appear capable of handling the same number of zeros as the first version. Now granted, the first version, still broken, but it doesn't ultimately choke in the same horrific way. So what is happening in sigma 2 that's not apparently happening in sigma 1. And again, some of you have tripped over this, and frankly, by the end of the semester you will all have core dumped. Why? What might be going wrong here? So it has to do with memory. Where is memory getting used in this program. I don't even see any local variables other than the parameter called M for this function. So where's the memory getting used. Like, why do I have memory problems? Yeah, so when I call M -- when I call sigma does what?  
 
[ Inaudible audience comment ]  
 
>> So it makes -- so it allocates a bit more memory. In fact, let me remind of this little picture from last week, and we said we'd come back to this. This recalls the rectangle that represents your computer's RAM. But recall the more important point from last week that any time you call a function a little chunk of memory does get allocated on the so-called stack for that function. And that chunk of memory we call a frame, so if sigma is called by name and then sigma calls who in version 2? Sigma. And then sigma calls sigma, and sigma calls sigma, you know, even though on this picture I've not implied that there is an upper bound on the amount of memory you can allocate, but in reality there is. On a typical system, a given program often cannot use any more than say 2 gigabytes of memory. Now that's a lot of memory, but not necessarily for programs like Photoshop, and so there actually are some interesting real world implications here. But the point is that rectangle eventually has a top to it. And if you keep trying to put more and more stack frames on your memory stack, eventually you're going to overlap with something else that needs it more. In fact, what did we say is at the very top of this rectangle, if briefly, last week? Sorry?  
 
[ Inaudible audience comment ]  
 
>> So there's a bunch of -- there's global variables, but there's also the text segment, as we called it, the program itself. Your zeros and ones of your program itself. Now this doesn't mean that you're overwriting your program on disc, it doesn't mean you're erasing your code. But it does mean that the operating system is just going to bail all together if you try using memory that already belongs to something else. So let's go ahead and end there, and on Wednesday we'll figure out how to work around this.  
 
[ Background noise ]  
 
==== Transcribed by Automatic Sync Technologies ==== 
 
펼쳐보기

작성참여하기  자막참여 히스토리 자막다운로드 

펼쳐보기
총 19강
  • 1강 : CS50 / 0주차: 수요일

    1강 : CS50 / 0주차: 수요일

    2강 : CS50 / 0주차: 금요일

    2강 : CS50 / 0주차: 금요일

    3강 : CS50 / 1주차: 수요일

    3강 : CS50 / 1주차: 수요일

    4강 : CS50 / 1주차: 금요일

    4강 : CS50 / 1주차: 금요일

    5강 : CS50 / 2주차: 월요일

    5강 : CS50 / 2주차: 월요일

    6강 : CS50 / 3주차: 월요일

    6강 : CS50 / 3주차: 월요일

  • 7강 : CS50 / 3주차: 수요일

    7강 : CS50 / 3주차: 수요일

    8강 : CS50 / 4주차: 월요일

    8강 : CS50 / 4주차: 월요일

    9강 : CS50 / 4주차: 수요일

    9강 : CS50 / 4주차: 수요일

    10강 : CS50 / 5주차: 월요일

    10강 : CS50 / 5주차: 월요일

    11강 : CS50 / 5주차: 수요일

    11강 : CS50 / 5주차: 수요일

    12강 : CS50 / 7주차: 월요일

    12강 : CS50 / 7주차: 월요일

  • 13강 : CS50 / 7주차: 수요일

    13강 : CS50 / 7주차: 수요일

    14강 : CS50 /  8주차: 월요일

    14강 : CS50 / 8주차: 월요일

    15강 : CS50 /  8주차: 수요일

    15강 : CS50 / 8주차: 수요일

    16강 : CS50 /  9주차: 월요일

    16강 : CS50 / 9주차: 월요일

    17강 : CS50 / 9주차: 수요일

    17강 : CS50 / 9주차: 수요일

    18강 : CS50 / 10주차: 월요일

    18강 : CS50 / 10주차: 월요일

  • 19강 : CS50 / 12주차: 월요일

    19강 : CS50 / 12주차: 월요일

강의 댓글 [ 1 ]

댓글 폼
       
( 0 / 800byte )
번역중입니다.
[2013/02/01 13:04.07]
처음페이지이전페이지1다음페이지마지막페이지
관련 동영상 강의
컴퓨터 프로그램의 구조와 해석 (18)

컴퓨터 프로그램의 구조와 해석 (18)

응용과학 / 컴퓨터 과학
버클리대학

[컴퓨터 프로그램의 구조와 해석 : 18 강]

컴퓨터 프로그램의 구조와 해석 (19)

컴퓨터 프로그램의 구조와 해석 (19)

응용과학 / 컴퓨터 과학
버클리대학

[컴퓨터 프로그램의 구조와 해석 : 19 강]

컴퓨터 프로그램의 구조와 해석 (20)

컴퓨터 프로그램의 구조와 해석 (20)

응용과학 / 컴퓨터 과학
버클리대학

[컴퓨터 프로그램의 구조와 해석 : 20 강]

컴퓨터 프로그램의 구조와 해석 (15)

컴퓨터 프로그램의 구조와 해석 (15)

응용과학 / 컴퓨터 과학
버클리대학

[컴퓨터 프로그램의 구조와 해석 : 15 강]

컴퓨터 프로그램의 구조와 해석 (16)

컴퓨터 프로그램의 구조와 해석 (16)

응용과학 / 컴퓨터 과학
버클리대학

[컴퓨터 프로그램의 구조와 해석 : 16 강]

Sitemap