DAVIDマラン：すべての権利。 我々は戻ってきました。 プログラミング上のこのセグメントのだから何 私たちは物事のミックスで行うだろうと思っていました。 一つは、少しを行います 何かのハンズオンの、 もっと遊び心を使用してもかかわらず プログラミングenvironment-- の実証である1 アイデアの正確種類 我々は、について話してきました しかし、もう少し正式に。 二つの一部を見て より技術的な方法 プログラマは、実際に解決するだろうということ 検索の問題のような問題 私たちは前に見たと また、より根本的に 仕分けの興味深い問題。 私達はちょうど取りに行くからと仮定します その電話帳がソートされたことを、 それだけでそれが実際にある種類の 多くの異なる方法で困難な問題 それを解決します。 だから我々は、これらを使用します 問題のクラス その物事の代表 一般的に解決される可能性があります。 そして、我々は話しましょう いくつかの詳細には約何 データと呼ばれstructures-- リンクリストのような手の込んだ方法 ハッシュテーブルや木々こと プログラマは、実際に希望 使用して、一般的に使用 ホワイトボードにペイントします どのような彼または彼女の絵 実装するための思い描きます ソフトウェアのいくつかの作品。 それでは、最初のハンズオン部分をやらせます。 だからと汚い手を取得 環境と呼ばれるscratch.mit.edu。 これは、我々が使用するツールです 私たちの学部クラスインチ それは設計されていますにもかかわらず、 12歳以上のため、 我々は最高のためにそれを使用します そのかなりの部分 それは素晴らしい、楽しいので、 学習のグラフィカルな方法 プログラミングについて少し何か。 だからここであなたは、そのURLに向かいます 非常にこのようなページが表示されます、 そして、先に行くとクリック 右上のスクラッチに参加 ユーザ名とAを選択 パスワード、最終的に自分自身を取得 account-- scratch.mit.edu。 私は私のようにこれを使用しようと思いました 最初にこれを示す機会。 質問はハーフタイムに思いつきました コー​​ドが実際にどのように見えるかについて。 そして、私たちは話していました Cについてブレーク中、 でparticular--特に 古い言語の下位レベル。 そして私はちょうどクイックをしました Cコードを見つけるためにGoogle検索 バイナリサーチのため、アルゴリズムは、我々 以前その電話帳を検索するために使用されます。 この特定の例は、もちろん、 電話帳を検索しません。 それはちょうどの全体の束を検索します コンピュータのメモリ内の数字。 しかし、あなただけのビジュアルを取得したい場合 どのような実際のプログラミングの意味 、それが見えるように言語が見えます このような少し何か。 だから、約20プラスです コー​​ドの30行程度、 しかし、会話我々 休憩の上に持ちました 実際にどのようにこの程度でした 0と1にモーフィングされます あなたはちょうどそれを元に戻すことができない場合 処理し、0と1から行きます バックコードに。 残念ながら、プロセス そう変革であります それは非常に簡単だと口で言います。 私は先に行って、実際になりました そのプログラム、バイナリ検索、 を介してゼロと1へ プログラムは、私のコンパイラと呼ばれます 私のMac上で右ここに持って起こります。 そして、あなたは画面を見れば ここでは、具体的に焦点を当て これらの中間の6つの列にのみ、 あなただけの0と1が表示されます。 そして、それらは0と1であること 正確に検索プログラムを構成しています。 そして、そのように5ビットの各チャンク、 ここでは0と1の各バイト、 いくつかの命令を表します 典型的には、コンピュータの内部。 そして、実際には、あなたが聞いた場合 マーケティングのスローガン "インテルインサイド」 - つまり、 もちろん、あなたが持っていることを意味 コンピュータ内部のインテルCPUや脳。 そして、それは、CPUがあることを意味するもの あなたは、命令セットを持っていること、 いわば。 多くの世界のすべてのCPU、 それらは、これらの日、インテル製の、 有限を理解します 命令の数。 そして、それらの命令は非常に低いレベルであります これら二つの数字を追加します。 一緒にこれらの2つの数値を乗算し、 ここからのデータのこの部分を移動 ここでは、メモリ内に、これを保存します ここからの情報は、メモリにここまで そのため、非常に、非常にそうforth-- 低レベル、ほとんどの電子詳細。 しかし、数学的なものと 結合された操作 我々は前に述べたもので、 データの表現 0と1のように、することができます あなたはすべてを構築します コンピュータがいるかどうか、今日行うことができます それは、テキスト、グラフィカル、ミュージカルです もしくはそうでないか。 だから、これは得ることは非常に簡単です。 迅速の雑草で失われました。 とがたくさんあり​​ます 構文上の課題 それによってあなたが最も簡単にする場合は、 プログラムのタイプミスなしの愚かな 全く動作します。 だから代わりに使用して、 Cのような言語今朝、 私はそれがだろうと思いました 実際に行うにはもっと楽しいです より視覚的な何か、どの 子供たちのために設計されている間 実際には完璧な現れであります 実際のプログラミングの language--だけに起こります テキストの代わりに画像を使用します これらのアイデアを表現します。 だから、あなたは確かに持っていたら、 scratch.mit.edu上のアカウント、 [作成]ボタンをクリックします。 サイトの左上にあります。 そして、あなたはのような環境が表示されます 私は私の画面上に表示しようとしてよ1 ここに。 そして、私たちはほんの少しを過ごすだろう ここで遊んで少しの時間。 我々は、すべてのいくつかを解決することはできませんどうかを見てみましょう 以下の方法で問題が一緒に。 それでは、あなたはこの内表示されます environment--と実際にちょうどましょう 私は一時停止します。 誰もがここにいないですか？ ここではありませんか？ OK。 だから、私はいくつかを指摘してみましょう この環境の特性。 画面の左上にあるだから、我々 スクラッチのステージを持っている、いわば。 スクラッチはない名前だけです このプログラミング言語の、 それはまた、猫の名前だこと あなたはそこにオレンジ色にデフォルトで表示されます。 彼は、ステージ上にあるので、 ずっと私が説明したような であるとして、以前のカメ 長方形のホワイトボード環境。 この猫の世界は完全に閉じ込められています そこにその矩形までトップに。 一方、右側の ここで手側は、それはです ただ、スクリプトエリア、 白紙状態可能ならば。 これは、私たちが書くしようとしているところであります 一瞬で我々のプログラム。 その私たちはものとし、ビルディングブロック このパズルをprogram--書き込むために使用 ピース、あなたがwill--されている場合 途中で右ここのもの、 そして、彼らは分類しています 機能別に。 だから、例えば、私が先に行くつもりです これらの少なくとも一つを示します。 私は先に行くとクリックするつもりです トップアップ制御カテゴリ。 したがって、これらは、トップアップカテゴリです。 私は制御カテゴリをクリックするつもりです。 むしろ、私がイベントをクリックするつもりです カテゴリ、非常に最初の1までトップ。 そして、あなたも一緒に従うしたい場合 我々はこれを行うように、あなたはに非常に歓迎しています。 私はこれをクリックしてドラッグするつもりです 第1、「緑の旗をクリック。 " そして、私はちょうどそれをドロップするつもりです 大体私の空白のスレートの上部にあります。 そして、スクラッチのいいものです で、このパズルのピース、ときに 他のパズルと連動 作品は、文字通り何をするつもりされています これらのパズルのピースを行うに言います。 だから、例えば、スクラッチは権利であります 今彼の世界の真ん中インチ 私は先に行くと選択するつもりです 今、のは言わせ、モーションカテゴリー、 あなたは何したい場合は モーションカテゴリをsame--。 そして今、私は、全体を持って気づきます ここにパズルのピースの束 それは、再び、一種の彼らが言う何をすべきか。 そして、私は先に行くと、ドラッグして、するつもりです 右ここの上に移動ブロックをドロップします。 そして、それとすぐにあなたが得るように注意してください 「緑の旗の下に近接しています 」ボタン、通知をクリックしました どのように白い線が表示され、 それはほとんどだかのように 磁気、それはそこに行きたいと考えています。 ただ手放す、それがスナップされます 一緒にと形状が一致します。 そして今、あなたはおそらく、ほとんどすることができます 私たちはこれを行っているところだと思います。 あなたがスクラッチステージを見れば こっちとその上部に見て、 あなたは、赤色光を参照してくださいよ、 記号、緑の旗を停止します。 そして、私は先に行くつもりです そして、私のscreen--を見ます あなたができれば、ちょっと。 私はクリックするつもりです 今緑の旗、 彼は10のステップであると思われるものを移動しました または、画面上の10ピクセル、10ドット、。 そしてその結果、エキサイティングではありません、 しかし、私が提案してみましょう だけでも、これを教えることなく、 自分独自のintuition--レットを使用して、 私は、あなたがどの​​ように把握することを提案します 右ステージからスクラッチ散歩をします。 彼は右側のための方法を作る持っています 画面、右にすべての方法。 私はあなたに瞬間を挙げてみましょう またはようにと格闘します。 あなたが見てみたいことがあります ブロックの他のカテゴリで。 大丈夫。 だから私たちが持っているときに、要約します 緑色のフラグはここをクリック そして、10の手順をされている移動 命令だけ、毎回私が 緑の旗をクリックして、何が起きているのでしょうか？ まあ、それは私のプログラムを実行しています。 だから私はこれを行うことができます 多分手動で10倍、 これは少し感じています いわば、少しハック、 それによって、私は本当にないんだけど 問題を解決します。 私は再びしようとしていると 何度も何度も何度も 私は一種の誤っまで ディレクティブを達成 私は以前に達成するために着手しています。 しかし、我々は我々のから知っています 擬似コード以前があること ループのプログラミングでこの概念、 何度も何度も何かをすること。 そして、私はそれをあなたの束を見ました どのようなパズルピースのために達し？ まで繰り返します。 だから我々は何かを行うことができます 以下のようになるまで繰り返します。 そして、あなたは正確になるまで何を繰り返しましたか？ OK。 そして、私はだ1で行こう ちょっとやや単純。 私が先に行くと、これを実行してみましょう。 あなたが持っている可能性があるため、それを注意してください コントロールの下で発見され、 この反復ブロックは、そこにあります それは大きいですようには見えません。 ではない多くの部屋があります これら二つの黄色の線の間。 しかし、あなたのいくつかは持っている可能性がありますように あなたはドラッグ＆ドロップすれば、気づきました、 それは形を埋めるために成長する様子がわかり。 そして、あなたはさらに多くを詰め込むことができます。 それはちょうど場合に成長しておこう あなたはドラッグして上にカーソルを合わせます。 そして、私は何かわかりません ここで最高の、そうしましょう 私は、少なくともために、5回繰り返します 例えば、その後、ステージに戻って そして、緑の旗をクリックします。 そして今、それはかなりありません注意してください。 今、あなたのいくつかは、提案された、として ビクトリアはちょうど、10回繰り返しました。 そして、それは一般的にありません 彼にすべての方法を取得し、 しかし、より堅牢な存在ではないでしょう 任意に考え出すより道 どのように多くの動きを作るには？ 何より良いブロックかもしれません より10倍はあることを繰り返しますか？ ええ、なぜ永遠に何かをしていませんか？ そして今、私はこのパズルのピースを移動させましょう そこに内側と、この1を取り除きます。 今どんなにスクラッチに気付きます 開始、彼は端に行きます。 そしてありがたいことに、MIT、 人だけで、スクラッチを作ります 必ず彼は決してことになります 完全に消失します。 あなたはいつも彼のしっぽをつかむことができます。 そして、ちょうど直感的に、 なぜ彼は動き続けるのでしょうか？ ここで何が起こっていますか？ 彼が停止しているようだが、 その後、私がピックアップし、ドラッグした場合 彼はあそこに行きたいし続けます。 何故ですか？ 本当に、コンピュータは文字通りです あなたがすることを教え何をするつもり。 あなたがそれを言ったのであれば、以前の実行 永遠なものを、次の、10のステップを移動し、 行くと続けるために起こっています 私は赤のストップサインを打つまで そして、完全にプログラムを停止します。 だから、あなたがしなかった場合でも、 これを行うには、どのように私でし より高速なスクラッチを動かします 画面上？ より多くのステップ、右か？ だからではなく、10を行います 一度、なぜ我々はしないでください 先に行くと、それを変更to-- あなたは、50は何propose--でしょうか？ だから今、私は緑をクリックするつもりです フラグは、実際、彼は本当に速い行きます。 これは、もちろん、単にあります アニメーションの現れ。 アニメーションとは何ですか？ それはちょうどあなたの人間のaを示しています 本当に静止画の全体の束、 本当に、本当に速いです。 だから私たちは言っている場合 彼はより多くのステップを移動し、 私達はちょうど効果がになる持っています 彼が画面に表示されている変更 すべてのより迅速に単位時間あたりの。 私が提案した今、次の課題 彼はエッジを跳ね返ることでした。 そして、何パズル知らず 結構ですので、作品はexist-- あなたがに取得しない場合 何challenge--のステージ あなたは直感的に何をしたいですか？ どのように我々は彼が立ち直るだろうと 前後、左右の？ うん。 だから我々はいくつかの種類を必要とします 条件、および私たちの のように、条件を持っているように見えます 制御カテゴリの下で、話します。 これらのブロックのどの 我々は、おそらくしたいですか？ うん、多分」であれば、その後。」 だから、黄色のブロック間のことに気付きます 私たちは、この「場合」があり、ここにあります その意志またはこの "であれば、他の"ブロック 私たちはこれを行うための意思決定を行うことができ またはそれを行うには。 そして、あなたはそれらを巣を均等することができます 複数の物事を行います。 それともあなたはまだここに行っていないしている場合は、 センシングカテゴリに先に行きます and--それがここにある場合を見てみましょう。 それではブロックは、ここで役に立つかもしれません 彼はステージからだかどうかを検出するには？ うん、これらのブロックのいくつかに気づきます いわば、パラメータ化することができます。 これらは、一種のではなく、カスタマイズすることができます HTMLとは異なり、昨日の属性を持ちます、 ここで、それらの属性の種類の タグの動作をカスタマイズ。 同様にここで、私はこの感動をつかむことができます ブロックと変化と質問を、 あなたは、マウスに触れています カーソルなどのポインタ または、エッジに触れていますか？ だから私はで行くと、これをやらせます。 私は一瞬ズームアウトするつもりです。 私はこのパズルのピースをつかむしてみましょう ここでは、このパズルのピースこの、 そして、私はまぜこぜするつもりです それまでちょっと。 私は、これを移動するつもりです エッジに触れることに変更し、 これを行うと私は運動するつもりです。 そこでここではいくつかの成分です。 私は私が望むすべてを持っていると思います。 誰かがどのように私を提案したいと思います これらは多分上から下へ接続することができます 有するの問題を解決するために スクラッチ移動に右へ左へ右 それぞれ、左へ左から右へ 時間はちょうど壁に跳ね返っ？ 私は何をしたいですか？ どのブロック私はに接続する必要があります 「グリーンフラッグが最初にクリックされましたか」？ OK、それでは始めましょう "永遠に。」 次に何が内側に行きますか？ 他の誰か。 OK、ステップを移動します。 大丈夫。 じゃあ何？ それでは場合。 そして、それが見えていても、気付きます しっかりと一緒に挟まれ、 それだけで埋めるために成長します。 それはちょうど私がそれをしたい場所にジャンプします。 そして、私は間に何を置きますか であれば、その後？ おそらく「場合のエッジに触れます。」 そして、通知は、再び、それはあまりにも大きいです それのために、それが埋めるために成長します。 そして、15度を回しますか？ どのように何度？ うん、だから180が回転します 私の周りのすべての方法。 だから私はこの権利を得た場合を見てみましょう。 私はズームアウトしてみましょう。 私はスクラッチアップをドラッグしてみましょう。 そこで彼は、少し歪みました 今、それは大丈夫です。 どのように私は簡単に彼をリセットすることができますか？ 私は少しカンニングするつもりです。 だから私は別のものを追加しています ブロックは、単に明確にすること。 私は彼が90度を指すようにしたいです デフォルトでは右に、 私はちょうど彼に言うつもりです プログラムでそれを行うには。 さあ、いくぞ。 私たちはそれを行っているように見えます。 それはので、少し奇妙なことです 彼は逆さまに歩いています。 バグことを呼ぶことにしましょう​​。 それは間違いです。 バグはA、プログラム内の誤りです 私、人間は、作られた論理エラー。 なぜ彼は逆さまに起こっていますか？ MITは、台無しにまたは私がやったのか？ ええ、私は意味、それはMITのではありません 障害が発生しました。彼らは私にパズルのピースを与えました それは、度のいくつかの数を回すと言います。 ビクトリアの提案で、 私は180度回転です、 これは右の直感です。 しかし、文字通り180度回転 180度回転手段、 それは本当にありません 私が欲しいもの、明らかに。 少なくとも彼は中だから この2次元の世界、 そのように回転が本当に起こっています 逆さまに彼を反転します。 私はおそらく何のブロックを使用したいです 代わりに、あなたがここで見るものに基づいて？ 我々はこれをどのように解決するのでしょうか？ ええ、私たちは指すことが 反対方向インチ そして、実際にあっても、それはです 十分であることを行っていません、 我々は唯一のハードコードすることができるので 左または右向きに。 あなたは、私たちは何ができるか知っていますか？ 我々が持っているように見えます こちらの都合ブロック。 私が見るにはズームインしている場合、参照してください。 何かここでは好きですか？ MITが持っているようなので、それが見えます 抽象化は、ここに建てられました。 このブロックは、同等であると思われます これに他のブロック、複数の？ この1ブロックは、同等であると思われます このブロックの全体のトリオへ 私たちがここに持っています。 だから、私は私を簡素化することができ判明します そのすべてを取り除くことにより、プログラム そして、ここだけでこれを置きます。 そして今、彼はまだ少しです バギー、それは今のところ大丈夫です。 私たちは、それがあることに残しておきます。 しかし、私のプログラムは偶数であります 単純な、この、あまりにも、 代表になります programming--でゴール 理想的としてあなたのコードを作ることです 単純な、可能な限りコンパクトなように、 まだのようでありながら できるだけ可読。 あなたはそれがとても簡潔にする必要はありません それは難しいことを理解します。 しかし、私が交換しまし気付きます 1と3のブロック、 それは間違いなく良いことです。 私は概念を抽象化しました あなたがしているかどうかをチェックします わずか1ブロックとエッジで。 今、私たちは、実際には、これで楽しみを持つことができます。 これは、あまり追加しません 知的値ではなく、遊び心の値。 私は先に行くつもりです ここでこの音をつかみます。 だから私は先に行かせて、私を聞かせて 瞬間のためのプログラムを停止します。 私は次のように記録するつもりです、 私のマイクへのアクセスを可能にします。 さあ。 痛いです。 それでは、もう一度これを試してみましょう。 さあ。 [OK]を、私は間違ったことを記録しました。 さあ。 痛いです。 痛いです。 大丈夫。 今、私はそれを取り除くために必要があります。 大丈夫。 だから今私が持っています ただの記録「痛いです。」 だから今、私は行くつもりです 先にこの「痛い。」と呼んで 私は戻って行くつもりです 今、私のスクリプト、およびへ 通知と呼ばれるこのブロックがあります 「痛い。 "音"ニャー "を再生したり、サウンドを再生 私はこれをドラッグします。また、どこです 私はコミカルな効果のためにこれを置く必要がありますか？ うん、だから今は一種のです 今、このblock--のでバギー、 気づくどのようにこの "エッジであれば、 バウンスは、「自己完結型の一種です。 だから私はこの問題を解決する必要があります。 私が先に行くと、これを実行してみましょう。 私は、このを取り除くしようと戻って 私たちの元に、より計画的な 機能性。 「エッジに触れる場合は、「だから私はしたいです ビクトリアが提案されているように、オンにし、 180度。 そして、私はプレーしたいです 音が「痛いですか」？ うん、それは外だ気付きます その黄色のブロック。 だから、これは、あまりにも、だろう バグが、私はそれを気づきました。 だから私はここにそれをドラッグするつもりです、 予告は今では内部のだ」であれば。」 したがって、この一種である "場合" 以下のようなアーム状ブロットの それだけに起こっています その中に何を行います。 だから今私がズームアウトした場合 annoying--のリスク COMPUTER：痛い、痛い、痛いです。 DAVIDマラン：そして、それ ただ永遠に移動します。 今だけの事を加速します ここでは、私が先に行くと開いてみましょう、 それでは、私はいくつかに行こうsay--う クラスから自分のものの。 とのは、このことを言わせて、私が開いてみましょう 私たちの指導員のいずれかによって作られたもの 数年前。 だからの一部が思い出すかもしれません 往年からこのゲーム、 そしてそれは実際に顕著です。 私たちがやったにもかかわらず 今、プログラムの最も簡単な、 それでは、どのようにこれを考えてみましょう 実際のように見えます。 私はプレーをヒットしてみましょう。 だから、このゲームでは、我々が持っています カエル、矢印を使用してkeys-- 彼は私よりも大きなステップを取りますremember-- 私は、このカエルを制御することができます。 そして目標は、忙しい渡って取得することです 車に実行せずに道路。 そして、私はここに行けばのはsee--ましょうI ログがによってスクロールするのを待つ必要があります。 これはバグのように感じています。 これはバグの一種です。 大丈夫。 私は、ここではこれによ そこに、次にあなたが保ちます あなたはすべてを取得するまで行きます ユリのパッドにカエル。 さて、これは見えるかもしれません すべてのより複雑な、 しかし、それでは、破るために試してみましょう 精神的にこのダウン そして、口頭でそのコンポーネントブロックへ。 だから、おそらくパズルがあります 我々はまだ見ていない作品 それはキーストロークに応答しています、 物事に私はキーボードで打ちます。 だから、おそらくいくつかの種類があります キーがアップ等しい場合、言いブロック、 その後Scratch--で何かを 多分10の手順をこのように移動します。 ダウンキーを押すと、10段階を移動 この方法、または左キーは、10ステップを移動します このように、10は、ステップ。 私ははっきりとカエルに猫になってきました。 だから、ちょうどどこです スクラッチ・コールit--我々として衣装、 ちょうどカエルの絵を輸入しました。 しかし、他に何が起こっているのでしょうか？ 他にどのようなコードの行、 どのような他のパズルのピース ブレイクした、私たちの指導員、 どうやら、このプログラムで使用？ 何がすべてのものを作っていますmove-- どのようなプログラミングが構築しますか？ モーション、sure--ので、 確かに、ブロックを移動します。 そして、その移動ブロックは何ですか 内側に、最も可能性が高いですか？ うん、ループのいくつかの種類、多分 永遠に多分繰り返し、ブロックblock-- ブロックされるまで繰り返します。 そしてそれは、ログを作っているものだと ユリ、パッドと他のすべての動き 行ったり来たり。 それだけで無限に起こっています。 なぜ車の一部です 他より速く移動しますか？ これらのプログラムについて異なるとは何ですか？ ええ、おそらくそれらのいくつかは、服用しています 一度、そのうちのいくつかでより多くのステップ 一度に少ない工程。 そして、視覚効果 遅い対高速です。 起こったあなたはどう思いますか？ 私は私のカエルを持ってすべての方法 通りや川を渡って ユリパッド上に、何か 注目すべきは起こりました。 何が、すぐに私はそれをしたとして起こったのか？ それは停止しました。 そのカエルを止め、 私は2番目のカエルを得ました。 だから何の構築物でなければなりません そこに使用され、どのような機能？ うん、そうのいくつかの種類があります あまりにも、そこまでの状態」であれば」。 そして、それは我々がthis--表示されませんでしたout--なります それそこに他のブロックがあります あなたが触れている場合は、言うことができます 画面上の別の事、 あなたはユリパッドに触れている場合、「その後」。 そして、それはときに我々のです 第二のカエルを表示させます。 だから、このゲームは確かにあるにもかかわらず 一見にもかかわらず、非常に時代遅れ そんなにそこon--行くとブレイクの 2分でこれをかき立てるていませんでした、 それはおそらく、いくつかの彼を連れて行きました このゲームを作成するための時間 彼の記憶やビデオに基づきます それの往年のバージョンの。 しかし、これらのささいなことのすべて 分離して画面上に行きます これらの非常にシンプルに煮詰めます constructs--動きまたは文 我々が議論してきたように、ループし、 条件、それはそれについてです。 他のいくつかの愛好家の特徴があります。 それらのいくつかは、純粋です 美的や音響、 音のように私はと遊びました。 しかし、ほとんどの部分は、あなた この言語、スクラッチを持っています、 基本のすべて そのあなたのビルディングブロック CやJava、JavaScriptで持っています、 PHPやRuby、Pythonの、 そして、他の言語の任意の数。 スクラッチについてのご質問？ 大丈夫。 だから我々は、スクラッチに深くに飛び込むません あなたはこの週末歓迎しているものの、 あなたが子供を持っている場合は特に、または 姪と甥など、 スクラッチにそれらを導入します。 それは実際に素晴らしく遊び心です 環境と、その著者が言うように、 非常に高い天井。 我々は、使用を開始にもかかわらず 非常に低レベルの詳細、 あなたが実際にはかなりビットを行うことができます これで、これはおそらくです まさにそれのデモ。 しかし、それでは、いくつかの詳細に移行しましょう 洗練された問題、可能ならば、 「検索」として知られており、 より一般的には「ソート」。 我々は、この電話帳を持っていたearlier--ここです ちょうどdiscussion--のための別の1 我々は検索することができたこと より効率的理由 重要な仮定の。 そして、ちょうど、明確にするもの 仮定私が作っていました この電話帳を検索するとき？ マイク・スミスはしていたこと 電話帳、Iかかわらず 扱うことができるだろう 彼なしシナリオ そこに私は途中で停止した場合。 本はアルファベット順です。 そして、それは非常に寛大なです 仮定、その理由 私は親切だsomeone--意味 コー​​ナーを切断します、 私は誰かので、速くていますように 他には、私のために多くのハードワークをしました。 しかし、どのような場合は、電話 この本は、ソートされていないでしたか？ 多分Verizonは怠け者だ、ただ投げました そこにすべての人の名前と番号 多分にある彼らの順序で 電話サービスにサインアップしました。 そして、どのくらいの時間それは私を取るん マイク・スミスのような人を見つけるには？ 千ページの電話はどのように多くのbook-- ページには、私は一読する必要がありますか？ それらのすべて。 あなたは、ソートの運の尽きです。 あなたは、文字通りすべてのを見ています ページ電話帳だけである場合 ランダムに並べ替え。 あなたは幸運を得るとマイクを見つけるかもしれません 非常に最初のページに、彼のため 最初の顧客でした 電話サービスを注文します。 しかし、彼はあまりにも、最後だったかもしれません。 だからランダムな順序は良くありません。 だから我々は、ソートすることがあるとし 電話帳や一般的なソートデータで 私たちは与えられてきたこと。 我々はそれをどのように行うことができますか？ まあ、私はちょうど試してみましょう ここでは簡単な例。 私が先に行くと投げてみましょう ボード上のいくつかの数字。 我々が持っている数であると仮定し、 のは、4、2、1、および3をしましょう​​。 そして、ベンは、私たちのためにこれらの数字を並べ替えます。 いいよ。 どうやったの？ 大丈夫。 だから、最小で始まります 値と最高、 それは本当に良い直感です。 そして、我々を実現 人間は実際にはかなりあります 問題を解決するのが得意 このように、少なくとも、 データが比較的小さい場合。 すぐに数百を持って始めると 数字、数字の数千人の、 数字の何百万人、ベンは、おそらく それほど速いそれを行うことができませんでした、 あったと仮定すると 数字のギャップ。 万人にカウントするのは簡単 それ以外の場合は、ちょうど時間がかかります。 だから、このアルゴリズムは、それが聞こえます ベンはちょうど今使用のように 最小数の検索がありました。 だから我々人間が取ることができるにもかかわらず、 視覚的に多くの情報で、 コンピュータが実際にあります もう少し限られました。 コンピュータができる唯一の 一度に1バイトを見て time--時または多分4バイト time--で、これらの日は、多分8バイト しかし、非常に少ない数 与えられた時間でのバイト。 だから私たちは本当に持っていることを考えます 4つの別々の値here-- あなたが持つとベンと考えることができます 彼はそのようなコンピュータであれば上の目隠し 彼は他の何かを見ることができません time-- 1つの数より 私たちは、一般のように、前提としています 英語では、我々は右から左に読んであげます。 したがって、最初の数ベンはおそらく見えました で、非常に迅速に、その後4だったと それはかなり大きいです実現 number--私が探し続けてみましょう。 2があります。 ちょっと待って。 二つは4未満です。 私が覚えているつもりです。 二つは、現在最も小さいです。 今選ぶ - それはさらに良いです。 それはさらに小さいです。 私は約2を忘れるつもりです そしてちょうど今1を覚えています。 そして、彼は見ることをやめるだろうか？ まあ、彼はベースの可能性 この情報について、 彼はより良い検索をいただきたいです リストの残りの部分。 リストには何がゼロの場合であったため？ どのような負の1がリストにありましたか？ 彼は彼の答えを知っています 彼は徹底的な場合は、正しいです 全体のリストをチェックしました。 だから我々は、このの残りの部分を見てください。 そのThree--時間の無駄でした。 不運得たが、私がいました そうすることが正しいまだ。 そして今、彼おそらく 最小の番号を選択 そしてまだ始まったばかりでそれを置きます リストの、私はここでやるように。 今、あなたはあっても、次の何をしました あなたはほとんどそれについて考えていませんでした この程度まで？ プロセスを繰り返し、 ループのようにいくつかの種類。 おなじみのアイデアがあります。 そこでここでは4です。 それは、現在、最も小さいのです。 それは候補者です。 もう違います。 今、私は2つを見てきました。 それは次の最小要素です。 それはそう、小さくないですThree-- 今ベンは2を引き抜くことができます。 そして今、我々はプロセスを繰り返し、 もちろん3次引き出されます。 プロセスを繰り返します。 4つが引き出されます。 そして今、我々は数字の外出します、 そのようにリストをソートする必要があります。 実際、これは正式なアルゴリズムです。 コンピュータ科学者だろう "、選択ソート「これを呼び出します アイデアは、ソートAであること 再びiteratively--を一覧表示します そして、何度も何度も選択します 最小数。 そして、何それについての素晴らしいのはあります それはちょうどので、とても直感的です。 それはとても簡単です。 そして、あなたは同じことを繰り返すことができます 操作何度も何度も。 それは簡単です。 この場合、高速であったが それは実際にどのくらいかかりますか？ のは、それが見えるようにしましょう​​と もう少し退屈な感じ。 そのように、一つ、二つ、三つ、四つ、5~6、 7つ、8つ、9、10、11、12、13、14、 15、16--任意の数。 私はこの多くを望んでいました わずか4以上の時間。 だから私は、全体を持っている場合 それnow--数字の束 でも、問題ではありません。 彼らは何をしましょう​​are-- 何これについて考えます アルゴリズムは本当に好きです。 そこに数字があるとします。 ここでも、何が問題ではありません。 彼らは、彼らはランダムです。 私はベンのアルゴリズムを適用しています。 私は最小の番号を選択する必要があります。 私は何をしますか？ そして、私は物理的に行きますよ それはそれを行動するために、この時間を行います。 見て、見て、 見て、見て、見て。 唯一の私は取得時まで リストの最後にすることができます 私は最小を実現します 数は2この時間でした。 一つは、リストにありません。 だから私は2を下に置きます。 私は次に何をしますか？ 見て、見て、見て、見て。 今、私はので、番号7を発見しました これらnumbers--にギャップがあります ちょうど任意。 大丈夫。 だから今、私は7を下に置くことができます。 探して、探して探しています。 今私は、のと仮定しています ベンはないことをもちろん、 余分なRAMを持っている、余分な メモリはもちろん、なぜなら、 私は、同じ番号で探しています。 確かに私が覚えている可能性が これらの数字のすべて、 それは絶対に本当です。 しかし、ベンはすべて覚えている場合 彼は見ています数字の、 彼は本当に行われていません 基本的な進展 彼はすでに持っているので 検索する機能 ボード上の数字を通じ。 のすべてを思い出します 数字は、助けにはなりません 彼はコンピュータとしてまだすることができますので、 のみ、私たちが言った、1の数を見て 一度に。 だからチートのない並べ替えはありません そこにあなたが活用できる​​こと。 だから現実には、私のように リストを検索保ちます、 私は文字通り続けるために持っています 前後にそれを介して、アウト摘採 次の最小数。 そして、あなたは推論の種類をできる限り 私の愚かな動きから、 これはちょうど、非常に取得します 非常に迅速に退屈、 そして、私は戻っているように見えると 前後、前後にかなり。 今公正であることを、私は行く必要はありません ほど、よく、のが公正であることをsee--せ、 私はかなり歩く必要はありません など多くのステップ毎時間。 もちろん、私のように、ため、 リストから番号を選択し、 残りのリストが短くなってきています。 そしてそうのは、考えてみよう どのように多くのステップ、私は実際によ 毎回を通してtraipsing。 非常に最初の状況では 我々は、16の数字を持っていました そしてこれだけしてみましょうmaximally-- discussion--のためにこれを行います 私は16に目を通す必要がありました 最小を見つけるための番号。 しかし、かつて私は摘み取ら どのように最小数、 長いコースの残りのリストは、でしたか？ わずか15。 だから、どのように多くの数ベンまたは私が持っていました 二度目の周りに目を通すには？ 15は、ただ行くと最小を見つけることができます。 しかし、今、もちろん、リストがあり、 あまりにも、それは以前よりも小さいです。 私はやったので、どのように多くの手順 次の時間を取る必要がありますか？ 14、次に13、次に12、プラスドット、 私はちょうど1を残しているまでのドットは、点在しています。 だから今、コンピュータ科学者は、希望 すべて同じことを何、よく、頼みますか？ これは、実際にいくつかの具体的に等しいです その私たちは確かにできた数 算術行うが、我々は話をしたいです アルゴリズムの効率化について もう少しformulaically、 リストがあるどのくらいの独立しました。 だから、あなたは何を知っていますか？ 、これは16ですが、私は前に言ったように ちょうど問題のサイズを呼ぶことにしましょう nはいくつかの数であるnは、。 多分それは多分それはだ、16です 3は、多分それは万人です。 知りません。 私は気にしない。 私が本当に欲しいのはあります 式私ができます このアルゴリズムを比較するために使用 他のアルゴリズムに対する 誰かが主張する可能性があること 良くも悪くもです。 だから、判明、と私だけ 小学校からこれを知って、 これは実際には同じということになりますことを nはプラス2分の1以上のnは事。 そして、これは、等しいことを起こります コー​​スは、プラスnは2以上の二乗のn。 私は式を望んでいたので、もし どのように多くのステップのため 全く見に関与していました 何度も何度もそれらの数の そして、何度も何度も、私は言うだろう それは、n乗プラスnは2以上です。 しかし、あなたは何を知っていますか？ これは単に乱雑に見えます。 私は本当にしたいです 物事の一般的な意味。 そして、あなたはから思い出すかもしれません 高校その存在 最上位の用語の概念です。 これらの用語のどれ、n個 、N、または半二乗、 時間をかけて、ほとんど影響を与えていますか？ 大きなNは、その取得します もっとも、これらの問題の？ 言い換えれば、私はプラグ場合 万人であり、n乗 最も可能性が高いとしています 支配的要因、 なぜなら万回 それ自体は多くの大きいです 以上に加えて、追加百万。 だからあなたは何を知っていますか？ これは、このようなくそが大きいです 数は数を二乗場合。 これは本当に重要ではありません。 私達はちょうど十字を行っていること アウトし、それを忘れます。 それでコンピュータ科学者は言います このアルゴリズムの効率は、その n個のオーダーでありますsquared-- 私は本当に近似を意味します。 それは一種のおおよそのn乗です。 時間が経つにつれて、より大きな そして、大きなnが、これを取得します 何のために良い推定で 効率や効率性の欠如 このアルゴリズムの実際です。 そして、私はもちろんのことを引き出します、 実際に数学をやってから。 しかし、今私はちょうど手を振っています 私の手、私はちょうどので、 このアルゴリズムの一般的な意味を求めています。 そう一方、同じロジックを使用して、 のは、別のアルゴリズムを考えてみましょう 我々はすでに線形検索at--見えました。 私が探していたとき 電話用book-- 検索、それを並べ替えていません 電話を通してbook-- 我々はそれがあったことを言い続け 千段階、または500段階。 しかし、ここではそれを一般化してみましょう。 中のnページがある場合は 電話帳、何 走行時間または 線形探索の効率？ それはのためにです どのように多くの手順見つけるために マイク・スミスは、線形探索を使用して 最初のアルゴリズム、または偶数秒？ 最悪の場合、マイクで 本の最後にあります。 電話帳は、1,000ページを持っているのであれば、 我々は、最悪の場合には、最後の時間を言いました それは大体どのようにかかることがあります 多くのページには、マイクを見つけるには？ 千のように。 それは上限です。 それは最悪の状況です。 しかし、再び、私たちは離れて移動しています 今千のような番号から。 それはちょうどn個です。 だから、論理的な結論は何ですか？ 電話でマイクを見つけます nページを持っている書籍 非常に最悪の場合には、かかることがあり、 どのように多くのステップn個のオーダーの？ そして実際コンピュータ 科学者は言います 走行時間、またはその パフォーマンスや効率性 アルゴリズムのようなのか、非効率、 線形探索は、nのオーダーです。 そして、我々は同じように適用することができます 何かを通過するロジック 私はちょうど第二に行ったように アルゴリズム我々は、電話帳としていました ここで、我々は、一度に2つのページに行きました。 だから、千ページ電話帳のかもしれません 500ページのターン私たちを取る、プラス1 我々は少し戻って倍増場合。 そのように電話帳がnページがある場合、しかし 私たちは、一度に2つのページをやっています それは大体何ですか？ 2以上のN、そのためには、2以上のn個のようなものです。 しかし、私は主張aを作っ two--にわたってそのn個前の瞬間 それはちょうどnと同じのようなものです。 それは、単に一定の係数です コンピュータ科学者は言うでしょう。 のだけに焦点を当ててみましょう 変数、really-- 式の最大の変数。 1を行うかどうかだから線形探索、 当時のページまたは一度に2ページ、 ソートの基本的に同じです。 これは、n個のオーダーではまだです。 しかし、私は、以前の私の写真と主張しました 第3のアルゴリズムではなかったこと リニア。 これは、直線ではありませんでした。 それは、その曲線とし、 代数式何がありましたか？ N--のログは、そのようにn個のベース2を記録します。 そして、我々はあまりにもに行く必要はありません 対数上の多くの詳細は本日、 しかし、ほとんどのコンピュータ科学者はいないだろう でもベースが何であるかを教えてください。 ので、それだけですべてです いわば一定の要因、 ただ若干の数値の違い。 そして、これは非常に一般的であろう 特にフォーマルなコンピュータのための方法 ボードの科学者や ホワイトボードのプログラマー 実際に主張しています 彼らが使用するアルゴリズム またはどのような効率 それらのアルゴリズムです。 そして、これは必ずしもものではありません あなたは、任意の非常に詳細に議論します 良いプログラマは人です 人は、固体、正式なバックグラウンドを持っています。 彼はに話すことができます 道のこの種で、あなた 実際に作ります 定性的な引数として なぜ1つのアルゴリズムのか 1つのソフトウェア 別のいくつかの方法で優れています。 あなたは確かに可能性があるため、 たった一人のプログラムを実行します そして、秒数を数えます それはいくつかの数字を並べ替えるのにかかります、 あなたは、いくつかを実行することができます 他の人のプログラム そして、数を数えます 秒のかかります。 しかし、これは、より一般的な方法があること あなたはアルゴリズムを分析するために使用することができ、 可能ならば、ちょうど 紙または単に口頭で。 なくてもすることなく、それを実行しています でも、サンプルの入力をしよう あなたはそれを介して推論することができます。 そのため、開発者を雇うと場合、または 彼またはあなたに主張の彼女の並べ替えを持ちます なぜ彼らのアルゴリズム、彼らの秘密 十億を検索するためのソース あなたのWeb​​ページの 同社は、これらの、優れています 引数の種類があり、それら 理想的に作ることができるはずです。 または、少なくともこれらは、 物事の種類 それはでは、議論の中で出てくるだろう 非常にフォーマルな議論の中で最低。 大丈夫。 だから、ベンは何かを提案しました 選択ソートと呼ばれます。 しかし、私はそこだと提案するつもりです あまりにも、これを行うための他の方法。 私が本当に好きではなかったです ベンのアルゴリズムについて 彼は歩き続けたということですか、 私は前後に、歩きました そして前後にし、前後に。 代わりに私がした場合にどのような ここでは、これらの番号のようなもの そして、私はそれぞれに対処するました 私はそれを与えているように順番に番号？ つまり、ここです 数字の私のリスト。 四一三二つ。 そして、私は次のことをするつもりです。 私は数字を挿入するつもりです 彼らはむしろ属している場所 1回につき1つずつ選択するよりも。 つまり、ここで4番です。 ここに私の元のリストです。 そして、私は維持するつもりです ここでは、本質的に新しいリスト。 だから、これは古いリストです。 これは、新しいリストです。 私は数4が最初に参照してください。 私の新しいリストは、最初は空です それは些細なケースです その4は今盛り合わせリストです。 私はちょうど私が与えられている番号を取っています、 そして、私は私の新しいリストでそれを入れています。 この新しいリストがソートされていますか？ うん。 ちょうど1がありますので、それは愚かです 要素、それは絶対にソートされています。 場所のうちは何もありません。 それは、このアルゴリズムより面白いです、 私は、次のステップに移動したとき。 今、私は1つを持っています。 それで一つは、もちろん、に属し 始まるか、この新しいリストの最後？ 初め。 だから私は今、いくつかの作業を行う必要があります。 私はいくつかを取ってきました 私のマーカーとの自由 物事を描くことにより、 私はそれらを配置したい場所、 それは本当にありません コンピュータで正確な。 私たちが知っているように、コンピュータは、持っています RAM、またはランダムアクセスメモリ、 それは1バイトだと 別のバイトおよび別のバイト。 そして、あなたはのギガバイトを持っている場合 RAMは、あなたが億バイトを持って、 しかし、彼らは一箇所に物理的にしています。 あなただけの周りのものを移動することはできません ボード上に描画することにより、 あなたが好きな場所。 だから、私の新しいリストを持っている場合 メモリ内の4箇所、 残念ながら4は、 すでに間違った場所インチ だから番号を挿入する1 私はここでそれを描画することはできません。 この記憶場所は存在しません。 それは浮気されるだろう、と私はされています 数分間絵浮気 ここに。 だから本当に、私はここに1を入れたい場合は、 私は一時的に4をコピーする必要が そしてそこ1を置きます。 それは大丈夫です、それは正しいです、 それは技術的には可能だが、 しかし、それは余分な作業だ実現しています。 私はちょうど場所に番号を入れていません。 私が最初に移動しなければなりませんでした 番号、その後、場所に置き、 私は一種の仕事の私の量を倍増しました。 だから、心に留めておきます。 しかし、私は今、この要素で終わりです。 今、私は数3をつかむしたいです。 もちろん、それはどこに属しているのでしょうか？ 間で。 私はもうカンニングすることはできません ちょうど、そこにそれを置きます なぜなら、再び、このメモリ 物理的な場所です。 だから私は4をコピーする必要が ここの上に3を入れました。 ではない大したこと。 それはちょうど1つの余分なステップです again--非常に安価な感じ。 しかし、今私は2つに移動します。 2は、当然のことながら、ここに属しています。 今、あなたはどのように見え始めます 仕事は積み上げることができます。 今、何を私がしなければならないのですか？ ええ、私は4を移動する必要があり、 私は、3をコピーする必要があり、 そして今、私は2を挿入することができます。 そして、これでキャッチ アルゴリズム、興味深いことに、 それは、我々はより極端があるとされています それはのは8、7を言わせていた場合、 6、5、4つ、三つ、2個、一つ。 これは、多くの状況で、あります 最悪の場合、 くそ事理由 文字通り後方です。 それは本当にありません ベンのアルゴリズムに影響を与え、 ベンの選択であるため ソート彼は維持するつもりです リストを前後に行きます。 そして、彼はいつも見ていたので、 全体の残りのリストを、 それは問題ではありません どこの要素があります。 しかし、この場合は私の挿入と approach--のは、これを試してみましょう。 そのように、一つ、二つ、三つ、四つ、 5つ、6つ、7つ、8つ。 1 2 3 4、 5つ、6つ、7つ、8つ。 私は、8を取るつもりです どこ私はそれを置くのですか？ さて、私のリストの先頭に、 この新しいリストがソートされているので。 そして、私はそれを横切ります。 どこで7を置けばいいの？ それをくそ。 それは、そこに行く必要があるので、 私はいくつかのコピーを行う必要があります。 そして今、7がここに入ります。 今私は6に移動します。 今ではさらに多くの仕事です。 エイトは、ここに行かなければなりません。 セブンはここに行かなければなりません。 今6は、ここに行くことができます。 今、私は5をつかみます。 今8は行かなければなりません ここで、7はここに行かなければなりません、 6は、ここに行く必要があり、 今5を繰り返し。 そして、私はかなりよ 常にそれを動かします。 それで終わりに、このalgorithm--我々はよ 実際sort--挿入それを呼び出します あまりにも、多くの仕事を持っています。 それはちょうど違います ベンのより作業の種類。 ベンの仕事は私が行く持っていました 前後にすべての時間、 次の最小を選択 要素何度も何度も。 だから、仕事のこの非常に視覚的なものでした。 まだこの他のアルゴリズム、 それは仕事を取得しますcorrect-- done-- ちょうど仕事の量を変更します。 最初にあなたがしているように見えます あなただけだから、省 各要素を扱います すべて歩いなしフロントアップ ベンのようなリストを方法でした。 しかし、問題は、特にこれらの中で、あります それはすべて後方だ狂った例、 あなただけの種類のです ハードワークを延期 あなたはあなたの過ちを修正する必要がありますまで。 そして、あなたはこれを想像することができる場合 8と7と6と5 以降4と3と2 リストを介して自分の道を移動し、 我々だけ変更しました 私たちがやっている仕事のタイプ。 代わりにそれを行うの 私の反復の開始、 私はちょうどでそれをやっています 各反復の終わり。 だから、このアルゴリズムことが判明します あまりにも、一般的に呼ばれる挿入ソート、 n個のオーダー乗にもあります。 それは、何より良い実際ません 良いまったくありません。 しかし、第三のアプローチがあります 私は、検討する私たちを励まします これはこれです。 だから簡単にするために、私のリストを考えます 再び、ある4つ、いずれか三つ、 ちょうど4つの数字をtwo--。 ベンは良い勘を持っていました、 良い人間の直感 前に、我々は全体を固定することにより、 eventually--挿入ソートを一覧表示。 私たちに沿ってなだめ。 しかし、それでは、考えてみましょう このリストを修正する最も簡単な方法。 このリストはソートされません。 どうして？ 英語では、理由を説明 それは実際にはソートされていません。 それはソートされていない何を意味するのでしょうか？ 学生：それは連続していないのです。 DAVIDマラン：連続していません。 私の例を与えます。 STUDENT：順序でそれらを置きます。 DAVIDマラン：OK。 私はより具体的な例を与えます。 STUDENT：昇順。 DAVIDマラン：昇順ません。 より正確に。 私はあなたが上昇することによって何を意味するのか分かりません。 どうしましたか？ 学生：最小 数字は、第一の空間ではありません。 DAVIDマラン：最小数の ない最初のスペースインチ より具体的に。 私がキャッチし始めています。 我々は数えるが、しています ここで順不同で何ですか？ STUDENT：数値の配列。 DAVIDマラン：数値の配列。 保管のみんなの種類 それは非常に高いレベルをhere--。 ただ、文字通り何を教えて 5歳のかもしれないような間違いました。 STUDENT：プラス1。 DAVIDマラン：それは何ですか？ STUDENT：プラス1。 DAVIDマラン：あなたは何を意味するのプラスワンのですか？ 私に異なる5歳を与えます。 間違って、お母さんは何ですか？ お父さん、何が悪いのでしょうか？ あなたはこれがソートされていないとはどういう意味ですか？ 学生：それは右の場所ではありません。 DAVIDマラン：何が ない適切な場所にありますか？ 学生：フォー。 DAVIDマラン：OK、良いです。 それがあるべき場所だから4ではありません。 具体的には、この権利はありますか？ 四一、第 私が見る二つの数字。 これは正しいですか？ いいえ、彼らは右、順不同でいますか？ 実際には、今思います あまりにも、コンピュータに関する。 それだけで、多分1で見ることができます once--で多分二つのこと 実際に一つだけ 同時に、それは、少なくとも その後、一つのことを見て 右隣に次の事。 したがって、これらは順になっていますか？ もちろん違います。 だからあなたは何を知っていますか？ なぜ我々は、赤ちゃんを取ることはありません この問題を修正する手順 代わりに、これらの空想をしているの ベンのようなアルゴリズム 彼は一種のことで、それを固定しています リストをループ その代わりに、ここで私がやったことの 私たちが行くように私はちょうど種類のそれを修正しますか？ ちょうど文字通り分解してみましょう order--番号順の概念、 あなたはwant--何でもそれを呼び出します これらの対比較に。 四一。 これは、正しい順序ですか？ それでは、これを修正しましょう​​。 1および4、その後 私達はちょうどそれをコピーします。 すべての権利、良いです。 私は1と4つの固定しました。 スリーと2？ いいえ。 私の言葉は私の指を一致しましょう​​。 四三？ それは順序ではありませんので、私は行きますよ 1、3、4、2を行います。 いいよ。 今4と2？ 私たちも、この問題を解決する必要があります。 だから、1、3、2、4。 だから、ソートされていますか？ いいえ、それはソートに近いのですか？ 我々はこれを固定するのでそれは、あります 間違い、私たちは、この間違いを修正しました 私たちはこの間違いを修正しました。 だから我々は間違いなく3ミスを修正しました。 まだ実際にソートされた見ていませんが、 それは、ソートに客観的に近いです 我々は、これらのミスの一部を固定しているため。 今、私は次に何をしますか？ 私は種類のリストの最後に達しました。 私は、固定されているように見えました すべてのミス、ありません。 この場合には、いくつかの数値ため、 近いバブルアップしている可能性があります 他の番号へ 順不同で残っています。 それでは、もう一度やってみましょう、と私はよ だけの場所では、この時間は、それを行います。 1と3？ 大丈夫だよ。 スリーと2？ もちろん無いので、のはそれを変更してみましょう。 そう二つ、三つ。 3と4？ そして今、ちょうどであるとします ここでは特に知識をひけらかします。 それはソートされていますか？ あなたの人間は、それがソートされています知っています。 私はもう一度試してみてください。 だから、オリビアは、私はもう一度試して提案しています。 どうして？ コンピュータは持っていないので 私たち人間の目の贅沢 ちょうどback-- OKかすめる、私は終わりです。 どのようにコンピュータが決定しません リストは、現在ソートされていますか？ 機械的に。 私は通過する必要があります もう一度、と私だけの場合 私は間違いを見つける/ことができますことはありません。 その後うん、コンピュータとして結論付け、 我々は行ってもいいです。 だから、1と2、2と 3、3と4。 今私は決定的にこれがあると言うことができます 私は何も変更を加えていないので、ソート。 今、それはバグだろうとだけ 愚かな私の場合、コンピュータ、 再び、同じ質問をしました 異なった答えを期待。 起こるべきではありません。 そして今リストがソートされます。 残念ながら、時間を実行しています このアルゴリズムでもあるのn乗。 どうして？ nを番号を持っているので、とで あなたはn個の数字を移動する必要があり、最悪の場合 n回あなたが続けるために持っているので、 バックチェックして、潜在的に修正します これらの数字。 そして、我々はより多くを行うことができます フォーマル解析、あまりにも。 だから、これは私たちが撮影したと言うことすべてであります 3異なるアプローチ、1 それらのすぐに直感的な ベンからバットオフ 私の提案の挿入へ この1へソート あなたは親切なのを見失うところ 最初にツリーの森。 しかし、その後、あなたは、バックステップを取る場合 出来上がり、私たちはソート概念を修正しました。 だから、これは、あえて言う、あります おそらく、より低いレベル それらの他のいくつかより アルゴリズムが、レッツ 我々は視覚化することができないかどうかを確認 これらの本を介して。 だから、これはいくつかの素晴らしいです ソフトウェア誰か カラフルなバーのを使って書きました 私たちのために以下のことをするつもり。 これらのバーのそれぞれは、数を表します。 背の高いバー、大きな 数、小さいバー、 数より小さい。 だから理想的に、私たちは素敵なピラミッドを望みます それは小さな始まり、大きな取得する場所、 それはそれを意味します これらのバーがソートされています。 だから私は先に行くと選択するつもりです、 例えば、ベンのアルゴリズム first--選択ソート。 そして、それはやっているものに気づきます。 彼らが選んだ道 このアルゴリズムを可視化 それは私がしただけのようであり、 私のリストを歩いて、 このプログラムは、歩いています 番号のリストを通じ、 ピンクのそれぞれにハイライト それは見ての番号。 そして今起こることについては何ですか？ その最小数 Iまたはベンは突然発見しました リストの先頭に移動します。 そして、彼らは追い出しをしたに気付きます あった数、 それは完全に罰金です。 私は細部のそのレベルに取得できませんでした。 しかし、我々は、配置する必要があります その数はどこか、 私たちはちょうどにそれを移動しました 作成されたオープンなスポット。 だから私はこれを高速化するつもりです アップ、それ以外の場合理由 すぐに非常に大変な作業となります。 アニメーションがspeed--私達は行きます。 だから今同じ原理 I適用したが、あなた もしあれば、アルゴリズムを感じるように開始することができます 意志、あるいはもう少し明確にそれを参照してください。 このアルゴリズムは、効果を有します 次の最小の要素を選択し、 あなたはを開始するつもりです それは左のランプアップを参照してください。 また、各繰り返しで、私は、 提案された、それは少し作業を行います。 これは、すべての道を行く必要はありません。 バックリストの左端に、 すでにので、 ソートされているものが知っています。 それはだようなので、それは一種の感じ 各ステップであっても、加速 同じだけの時間を取ります。 残りわずか少ない手順があります。 そして今、あなたは一種の感じることができます このアルゴリズムは、それの終わりをクリーンアップ 実際、今それがソートされています。 だから、挿入ソートはすべて完了です。 私は配列を再ランダム化する必要があります。 そして、ちょうど私ができる気付きます それをランダムに保ちます、 そして我々は、の近似値を取得します 同じアプローチ、挿入ソート。 私はここにそれをスローダウンしてみましょう。 のはそれを最初からやり直しましょう​​。 やめる。 それでは、4をスキップしてみましょう。 そうしよう。 それらの配列をランダム。 そして、ここでは挿入ソートをgo--。 遊びます。 それは各扱っていますことに注意してください それはすぐに遭遇した要素、 しかし、それはに属している場合 間違った場所の通知 起こることがありすべての作業。 私たちは、より多くのシフト維持する必要があります そしてより多くの要素が部屋を作るために 1のために我々は場所に置きたいです。 だから我々は、に焦点を当てています リストのみの左端。 私たちも、at--私たちを見ていません注意してください ピンク何で強調表示されていません 右の方へ。 私達はちょうどを扱っています 問題我々が行くように、 しかし、我々は多くのを作成しています まだ自分自身のために働きます。 そして、私たちはこれをスピードアップする場合 今完了に行くために、 それは確かにそれとは異なる感触を持っています。 それはちょうど左端に焦点を当てていますが、 needed--としてもう少し仕事をして 平滑どのような種類のもの オーバー、物事を固定し、 しかし、で最終的に扱います 一度に各要素1 私たちがよくthe--するために取得するまで、我々 すべてはこれが終了しようとしている方法を知って、 それはおそらく、少しがっかりです。 しかしend--中リスト spoiler--がソートされようとしています。 それでは、最後の1を見てみましょう。 私達はちょうど今スキップすることはできません。 私たちはほとんどがしています。 どこへ行くか二つ、行くために1。 出来上がり。 優れた。 だから今のは、最後のいずれかを実行してみましょう、 再ランダム化バブルソートと。 そして、私はそれを遅らせる場合は特に、ここに気付きます ダウン、これは貫通急降下続けるん。 しかし、それだけでペアごとになります気づきます 局所解のcomparisons--一種。 しかし、すぐに、我々はに取るにつれて ピンクで、リストの末尾、 何が再び起こるしているつもりですか？ ええ、しているつもりです それだけであるため、最初からやり直します 固定ペアごとのミス。 そして、それはまだ他の人が明らかになっている可能性があります。 あなたがこれをスピードアップするそうなら、あなたはよ 、名前が示す限り、それを参照してください。 elements--小さいかではなく、 より大きなelements--が開始されています バブルへ戻るまで、可能ならば。 小さい要素があります ダウン左にバブルに始まります。 そして実際、それは一種のです 同様に視覚効果。 そして、これは仕上げてしまいます 非常に類似した方法で、あまりにも。 私たちは住む必要はありません この特定の1に。 私も、今これを開いてみましょう。 他のいくつかのソートアルゴリズムがあります 世界では、そのいくつかの ここで捕捉されます。 特にありません学習者のための 必ずしも視覚的または数学的、 我々の前に行ったように、我々はできます またaudiallyこれを行います 私たちはこれで音を関連付ける場合。 そして、ちょうど楽しみのために、ここです いくつかの異なるアルゴリズム、 あなたがしている、特にそれらの一つ 呼ばれて気づくことだろう "マージソート。」 それは実際に基本的です より良いアルゴリズム、 その結果、マージソート、の1 あなたが見しようとしているもの、 乗n個の順序ではありません。 これは、n回のオーダーでの対数い 実際に小さいので、あるnは、 他の3よりも速いです。 そして、他のカップルがあります 我々が表示されます愚かなもの。 そこでここではいくつかの音で行きます。 これには、もう一度、挿入ソートであります それだけの要素を扱っています 彼らが来るように。 これは、バブルソートであるので、それはです 一度にペアを考えます。 そして再び、最大の要素 トップに湧き上がっています。 次に選択ソートアップ。 これはベンのアルゴリズムであり、 再び彼が反復的に選択することです 次の最小の要素。 そして再び、今、あなたは本当にそれを聞くことができます それが唯一のこれまでのところでスピードアップです それが少なくをやっているように 各反復に取り組みます。 これは、速いものであり、マージソート 数のクラスタをソートしています 一緒にし、それらを組み合わせます。 だから、左をlook-- 半分はすでにソートされています。 今では右半分を並べ替えていますし、 今では1にそれらを組み合わせることが起こっています。 これはと呼ばれるものである」ノームソート。」 そして、あなたは一種のそれを見ることができます それは、前後になるだろう 少しここで仕事を固定し、 そこにそれが新しい仕事に進みます。 以上です。 別のソートは、あります 本当にただ学術目的のために、 かかる「愚かなソート」と呼ばれます あなたのデータを、ランダムにそれをソートし、 それがソートされている場合、次にチェックします。 そうでない場合、それは再ソートし、それを それはソートいた場合、ランダムに、チェックし、 繰り返すない場合。 そして、理論的には、確率的に これは、完了します しかし、かなりの時間後。 これは、ほとんどありません アルゴリズムの効率的。 それらの上だからご質問 特定のアルゴリズムか何か あまりにも、そこに関連しますか？ さて、今何すべてを離れていじめるしましょう これらの行は、私が描画されてきたことがあります そして、私はコンピュータを仮定しているもの フードの下に行うことができます。 私はこれらの数字のすべてのことを主張するだろう 私は、彼らが取得する必要がありdrawing--続けます メモリのどこかに保存されています。 我々はあまりにも、今、この男を取り除くでしょう。 メモリのだから作品 そうRAM DIMMがありますcomputer-- 私たちは、デュアル、昨日検索 インライン・メモリ・module--は次のようになります。 そして、これらの小さな黒いチップの各 一般的に、バイトのいくつかの数です。 そして、金のピンは似ています それをコンピュータに接続するワイヤ、 そして、緑のシリコン基板だけです 何がすべて一緒にすべてを保持します。 だから、これは本当に何を意味するのでしょうか？ 私は一種のこの同じ絵を描く場合は、 のは、簡単にするために仮定しましょう このDIMM、デュアルその インラインメモリモジュール、 RAMの1ギガバイトの1ギガバイトです どのように多くのバイト数の合計であるメモリ、？ 1ギガバイトは何バイトですか？ それ以上。 1124は、キロ千です。 メガは百万円であります。 ギガは十億です。 私は嘘をついていますか？ 私たちも、ラベルを読むことができますか？ これは実際には128です ギガバイトは、それはより多くのです。 しかし、我々はこれをふり ちょうど1ギガバイトです。 だから、億がありますことを意味します 私には利用可能なメモリのバイト 80億ビットが、我々はつもりか 今バイトの観点で話をします、 前進。 それでは、それが意味することは、これはされています 1バイトは、これが別のバイトであり、 これは別のバイトであり、 そして私たちは本当にたい場合 具体的には我々がしなければなりません 億少し正方形を描きます。 しかし、それは何を意味するのでしょうか？ まあ、私はちょうどズームインしてみましょう この画面上インチ 私が何かを持っていればそれが見えます このように、今、それは4バイトです。 だから私はここで4つの数字を入れることができます。 1 2 3 4。 または私は4つの文字や記号を置くことができます。 「おい！」右そこに行くことができ、 文字の各ので、 我々は先に述べました、 表すことができます 8ビットまたはASCIIまたはバイトと。 換言すれば、次のことができます 内部80億ものを入れます メモリのこの1スティックの。 今では戻って物事を置くために何を意味しています このようにメモリに背中合わせにするには？ これはどのようなプログラマです 「アレイ」を呼んで コンピュータ・プログラムでは、あなたは思いません 基盤となるハードウェアについては、それ自体が。 あなただけのものとして自分自身を考えます 億バイトの合計へのアクセス、 あなたは何でもあなたはそれを望むことができます。 しかし、便宜上 それは一般的に便利です あなたの記憶の権利を維持します このような隣同士に。 だから私はthis--をズームインするとき、 我々は確かにつもりはないので、 億少しsquares--を描画します それでは、このボードが表すと仮定してみましょう 今メモリのスティック。 そして、私は同じように多くの私のように描きます マーカーは、ここで私を与えてしまいます。 だから今、私たちは棒を持っています ボード上のメモリの それは、1つ、2つ、3つ、4つ、5を持っています、 6、一つ、二つ、三つ、四つ、五つ、六つ、 のように42バイトをseven-- 画面全体の上のメモリ。 ありがとうございました。 はい、私の算術右ました。 そこでここでは、メモリの42バイト。 だから、これは実際に何を意味するのでしょうか？ まあ、コンピュータープログラマー 実際に、一般的だろう アドレス指定可能なように、このメモリを考えます。 換言すれば、これらの一つ一つ メモリ内の位置、ハードウェアで、 固有のアドレスを有しています。 それは一つのガタガタ音を立てるような複雑なものではありません スクエア、ケンブリッジ、マサチューセッツ州、02138。 その代わりに、それだけの数です。 これは、このは、バイト数はゼロです 一これが2である、これは3であり、 これは41です。 ちょっと待って。 私は一瞬前42を言ったと思いました。 私は、ゼロからカウントを開始しました そのためには、実際に正しいのです。 今、私たちは実際にそれを描画する必要はありません グリッドとして、あなたはグリッドとしてそれを描く場合 私は実際に物事を考えます 少し誤解を招く取得。 どのようなプログラマだろう、 彼または彼女自身の心の中で、 一般的と考えます メモリちょうどテープのようなものであるとして、 マスキングテープの一片のような それはただの、永遠に行きます またはあなたがメモリ不足になるまで。 描画するので、より多くの一般的な方法 そして、メモリだけを考えます これはバイトゼロ、1であるということでしょう、 2つ、3つ、その後ドット、ドット、ドット。 あなたも、42そのようなバイトの合計持っています 物理的に、それは実際にかもしれませんが もっとこのようなものになります。 ですから、今、あなたの考える場合 ちょうどテープのように、このようなメモリ、 これは、どのようなプログラマ再びです メモリの配列を呼び出します。 そして、あなたが実際に保存したいとき コンピュータのメモリで何か、 あなたは、一般的に店舗の物事を行います 背中合わせ背中合わせします。 だから我々は、数字の話をしてきました。 そして、私は問題を解決するために望んでいたとき、 様4、ある三、2つの 私は描いていたにもかかわらず、 数字のみ4、1、3、 ボード上の2つの、希望のコンピュータ 本当にメモリで、このセットアップを持っています。 そして隣に何でしょう コンピュータのメモリ内の2つの？ まあ、それに対する答えはありません。 私たちは本当に知りません。 そして限り、 コンピュータはそれを必要としません、 それは次の何であるかを気にする必要はありません。 数字には気にしません。 そして、私はコンピュータことを先に言ったとき 一度に一つのアドレスを見ることができ、 これはなぜの一種です。 いないレコードとは異なり、 プレーヤーと読み取りヘッド のみ、特定のを見てできること 物理的な古い学校レコードの溝 一度に、同様に コンピュータのおかげですることができます そのCPUへとその インテル命令セット、 その命令のうち、 メモリから読み出され またはmemory--への保存 コンピュータにのみ見ることができます time-- 1つの場所で 時々それらの組み合わせ しかし、実際に一度に一つだけの場所。 だから我々がやっていたとき これらの様々なアルゴリズム、 私はちょうどに書いていませんよ vacuum-- 4、1、3、2。 これらの数字は、実際に属しています メモリ内の物理どこか。 だから、小さな小さながあります トランジスタまたはいくつかの種類 下にエレクトロニクスの フードは、これらの値を記憶します。 そして、合計で、どのように多くのビットであり、 ただ明確にすることが、今の関与？ だから、これは4バイトである、または 今では32ビットの合計です。 だから、実際には32のゼロがあると これら4物事を構成するもの。 あり、さらにここではオーバーだが、 再び、我々はそれについて気にしません。 だから今のは別のものを尋ねてみましょう メモリを使用した質問、 その末尾の理由 一日の差異です。 どんなに私たちががどう処理されますか 一日の終わりに、コンピュータ、 ハードウェアはまだあります ボンネットの下に同じ。 どのように私はここに単語を保存するのでしょうか？ さて、コンピュータ内の単語のように 「ちょっと！」ちょうどこのように格納されます。 そして、あなたは長いを望んでいた場合 言葉は、単にすることができます それを上書きして何かを言います 「こんにちは」のような、そのここに格納します。 ので、ここでは、あまりにも、この連続性 利点は、実際に コンピュータはちょうどことができるので、 右から左に読みます。 しかし、ここで質問です。 この単語の文脈において、 H-E-L-L-O、感嘆符、 どこでどのようにコンピュータが知っているかもしれません 単語が始まり、言葉が終わるところ？ 数値の文脈では、 どのようにコンピュータがありません どのくらいのシーケンスを知っています 数字であるか、またはそれが始まりますか？ まあ、それはout--なります 私たちはあまり行くことはありません detail--のこのレベルに コンピュータは、メモリ内の周りのものを移動させます 文字通り、これらのアドレスを介して。 コンピュータ内だから、あなたがしている場合 物事を格納するためにコードを書きます 言葉のように、何をしています 実際に入力されてい で覚えているの式 コンピュータのメモリ、これらの言葉があります。 だから私は非常にやらせます、 非常に簡単な例。 私は先に行くつもりだと 単純なテキストプログラムを開き、 そして、私は作成するつもりです hello.cというファイル。 この情報のほとんどは、我々 非常に詳細に説明しません、 私は書くつもりです その同じ言語でプログラム、 C.これは、はるかに威圧的です 私はスクラッチよりも、主張するだろう、 それは精神に非常に似ています。 実際には、これらの巻き braces--することができます種類の 私はちょうどこのように何をしたかと思います。 それでは、実際に、これを実行してみましょう。 緑の旗をクリックすると、 次の手順を実行します。 私はプリントアウトしたい "こんにちは。" だから、これは今擬似コードです。 私は種類のラインをぼかしています。 C言語では、この言語は私が話しています こんにちはこのラインプリント、約 実際に「printf関数」になります いくつかの括弧およびセミコロン。 しかし、それはまったく同じ考えです。 そして、これは非常にユーザーフレンドリー 「グリーンフラッグがクリックされたとき」になります はるかに難解な「int型メイン無効。 " そして、これは実際にはマッピングされていません、 私はちょうどそれを無視するつもりです。 しかし、中括弧のようなものです このような湾曲したパズルのピース。 だから、一種の推測することができます。 あなたは以前にプログラムされたことがない場合であっても、 このプログラムは、おそらく何をするのでしょうか？ おそらくハロー印刷 感嘆符を持ちます。 それでは、それを試してみましょう。 私はそれを保存するつもりです。 そして、これは、再び、非常にあります 古い学校の環境。 私はドラッグすることはできません、クリックすることはできません。 私は、コマンドを入力する必要があります。 だから私は、私のプログラムを実行したいです 私はhello.cのように、これを実行します。 それは私が走ったファイルです。 しかし、私はステップを欠けている、待ってください。 我々は必要です何と言いました Cのような言語のためのステップ？ 私はソースを書きました コー​​ドが、私は何が必要なのですか？ ええ、私はコンパイラが必要です。 だからここに私のMac上で、私が持っています GCCと呼ばれるプログラム、GNU Cコンパイラ、 私はthis--ターンを行うことを可能にします 私のソースコードには、我々はそれを呼ぶことにします、 マシンコード。 そして、私はそれを見ることができ、 再び、次のように、これらの 0と1私はちょうどあります 私のソースコードから作成され、 0と1のすべて。 そして、私は実行したい場合 それが起こる私のprogram-- a.outと呼ばれるように 歴史的reasons--「こんにちは。」 私は再びそれを実行することができます。 こんにちは、こんにちは、こんにちは。 そして、それは動作しているようです。 しかし、それはどこかに私の中で意味します コンピュータのメモリ言葉です H-E-L-L-O、感嘆符。 そして、それはちょうどさておきとして、結局のところ、 どのようなコンピュータが通常と それはどこで知っているように行います 物事が起動し、それがですend-- ここで特殊記号を置くつもり。 そして大会は置くことです 単語の末尾の数字のゼロ あなたはどこで知っているように、 実際に、終了しているので より多くのをプリントアウト保持しません あなたが実際に予定よりも文字。 しかし、ここで持ち帰り、偶数 これはかなり難解ですが、 それは最終的だということです 比較的単純な。 あなたは、ブランクテープのようなものを与えられました あなたは手紙を書くことができたスペース。 あなたは、単に持っている必要があります 任意のような特殊記号、 の末尾に入れて数字のゼロ、 あなたの言葉のコンピュータが知っているように、 ああ、私は後に印刷を停止する必要があります 私は、感嘆符を参照してください。 そこに次の事ので、 ゼロのASCII値であり、 またはnull文字として 誰かがそれを呼び出すことになります。 しかし、問題のようなものがあります ここでは、とのが戻すましょう 瞬間のための番号へ。 実際には、私が行うこととし、 数字の配列を持っています、 そして、仮定する 私が書いているプログラムがあります 教師のためのグレードブックのような そして、教師の教室。 そして、このプログラムは、彼または彼女を可能にします 生徒のスコアを入力します クイズに。 そして、学生が取得することを仮定 彼らの最初のクイズに100、多分 その後、次の1に80、のような 75、次に第四クイズに90。 だから、物語の中で、この時点では、 アレイのサイズは4本です。 より多くのメモリはで絶対にあります コンピュータが、いわば配列、 サイズ4です。 教師が望んでいることを今仮定 クラスに五クイズを割り当てることができます。 まあ、物事の一つ、彼 または彼女がしなければならないとしています 今ここに追加の値を格納されています。 しかし、配列教師が持っている場合 このプログラムで作成されたがためのサイズです、 アレイの問題の一つは、ということです あなただけのメモリに追加し続けることができません。 そのためどのような場合の別の部分 プログラムはすぐそこに「ちょっと」という言葉を持っていますか？ 換言すれば、私のメモリとすることができます プログラムの中で何のために使用されます。 そして、事前に私は、ちょっと、で入力した場合 私は4クイズのスコアを入力したいです、 彼らはこことここに行くかもしれません。 そして、あなたは突然、あなたの心を変更した場合 それ以降、私は第五のクイズをしたいと言います スコア、あなたがすることはできませんだけで あなたが好きな場所にそれを置きます、 何この場合理由 メモリが使用されています 何かのためにいくつかの他のプログラムをelse-- またはプログラムのいくつかの他の特徴 あなたが実行していること？ ですから、事前に考えなければなりません あなたのデータを保存する方法を、 今は塗装しましたので、 自分のデジタルコーナーへ。 だから先生ではなくかもしれません プログラムを書くときに言います 彼または彼女を保存します グレードは、あなたは何を知っていますか？ 私は、依頼するつもりです 私のプログラムを書くとき、 Iは、0個、1個、2個、3個、欲しいこと 4、5、6、8等級は合計します。 そのように、一つ、二つ、三つ、四つ、 5つ、6つ、7つ、8つ。 教師はちょうどオーバー割り当てることができます メモリは、彼または彼女のプログラムを書くとき あなたは何を知っている、と言いますか？ 私はより多くを割り当てるつもりはありませんよ 学期中8クイズより。 それはちょうどクレイジーです。 私はそれを割り当てることは決してないだろう。 この方法は、彼または彼女が有するように 店舗の生徒の得点に柔軟性、 75、90、そしておそらく1つの余分のような 学生は余分な信用、105を得ました。 しかし、もし先生決して これらの3つのスペースを使用して、 ここでの直感的なお持ち帰りがあります。 彼または彼女はただのスペースを無駄にされています。 換言すれば、これはあり プログラミングにおける一般的なトレードオフ あなたはどちらかに割り当てることができる場所 あなたがしたいと正確に同じだけのメモリ、 利点は、あなたがスーパーだということです あなたが無駄にされていませんefficient-- all--ではなくの欠点 あなたの心を変更した場合どのようなときです 保存したいプログラムを使用して、 あなたが最初に意図したよりも多くのデータ。 そのため、おそらく解決策は、その後、あります このような方法であなたのプログラムを書きます 彼らはより多くのメモリを使用すること 彼らが実際に必要とするよりも。 あなたがつもりはない。このよう その問題に実行するには、 しかし、あなたは無駄にされています。 そして、あなたのプログラムが使用するより多くのメモリ、 昨日説明したように、少ないです 利用可能なメモリ 他のプログラムのために、 早くお使いのコンピュータが遅くなる可能性があります なぜなら、仮想メモリのダウン。 そのため、理想的な解決策は何でしょうか？ アンダー割当悪いようです。 過割当悪いようです。 それでは、よりよい解決策になるかもしれませんか？ 再割り当てします。 よりダイナミックです。 選ぶために自分自身を強制しないでください。 先験的には、始めに、あなたは何をしたいです。 そして確かに、オーバー配分していません あなたといけないので無駄なこと。 そのため、その目標を達成するために、我々 このデータ構造をスローする必要があり、 そう離れて、話します。 だから何のプログラマ 一般的に使用されます 何かがないと呼ばれています 配列が、リンクされたリスト。 言い換えれば、彼または彼女は意志 そのメモリを考え始めます 彼ら形状の一種であるとして、 次のように描くことができます。 私は中1の数を格納する場合 それは9月ですのでprogram--、 私は私の学生クイズを与えてくれました。が欲しいです 学生の最初のクイズを格納するため、 彼らは私がit--に100を得ました 私のコンピュータをお願いするつもりです、 私がしたプログラムを介して メモリの1つのチャンクのために、書かれました。 そして、私は保存するつもりです その中の数百、それはそれです。 その後、数週間後に 私は私の第二のクイズを得るとき、 それが入力する時が来ました その90％に、私はつもりです コンピュータを聞いて、ちょっと、コンピュータ、 私はメモリの別のチャンクを持つことができますか？ 私にこれを与えるために起こっています メモリの空のチャンク。 私は、数90に入れるつもりです しかし、私のプログラムで何とかまたはother-- 私たちは心配しません 私は必要this--の構文 これらの事を何とか一緒にチェーンに。 そして、私はそれらを一緒に連鎖します 何がここに矢印のように見えます。 立ち上がる第三クイズ、 私が言うつもりです、ねえ、コンピュータ、 私はメモリの別のチャンクを与えます。 そして、私は下に置くつもりです 何でもそれは75のように、でした、 そして、私はチェーンにこれを持っています 一緒に今何とか。 第四にクイズに沿って来て、多分 それは、学期の終わりに向かっています。 そして、それによって私のプログラムを指します メモリを使用している可能性があります すべての場所の上に、すべての物理的にオーバー。 そして、これだけキックのために、私はよ これを引き出すつもり quiz--私はそれが何だったか忘れてしまいました。私 多分80またはsomething--を考えます こっちの方法。 絵ので、しかし、それは、大丈夫です 私はこの線を描画するつもりです。 換言すれば、実際には、 コンピュータのハードウェアで、 第1のスコアかもしれません それはだから、ここで終わります 学期の開始時に右。 次はここで終わるかもしれません 少し時間が経過しているので、 プログラムが実行され続けます。 た次のスコア、 75、こっちかもしれません。 そして、最後のスコアがあるかもしれません こっちで80、。 だから実際には、物理​​的に、これは可能性があります どのようなコンピュータのメモリは次のようになります。 しかし、これは便利な精神ではありません コンピュータープログラマーのためのパラダイム。 なぜあなたはどこに気にする必要があります 一体あなたのデータは終わるのですか？ あなただけのデータを保存したいです。 これは一種の私達の議論のようなものです キューブを描画する以前。 なぜあなたは何を気にしません 角度は立方体であります そして、どのようにそれを描画するために有効にする必要がありますか？ あなただけのキューブをしたいです。 同様にここで、あなた ちょうどグレードブックにしたいです。 あなただけを考えたいです 番号のリストとしてこの。 それはだどのように誰が気に ハードウェアで実装？ 今では抽象化 この絵はここにあります。 これはのように、リンクされたリストであります プログラマはそれを呼び出すことになります、 あなたが持っているものであれば、 明らか番号のリスト、。 しかし、それは絵リンクされています これらの矢印を介して、 そして、これらすべての矢印が下にare-- フード、あなたが興味があれば、 私たちの物理的なハードウェアが持っていることを思い出します アドレスはゼロ、一つ、二つ、三つ、四つ。 すべてのこれらの矢印は、地図のようなものです 今の場合90 is--や方向、 私は数えるようになりました。 ゼロ、1つ、2つ、3つ、 4つ、5、6、7。 90であるように見えます メモリアドレス番号7。 これらのすべての矢印がされています 紙の小さなスクラップのような それはに指示を与えています このマップに従うと言うプログラム 位置7に到達します。 そして、そこにあなたが見つけます 学生の第二クイズのスコア。 一方、75--私はこれを続ければ、 これは、7つ、8つ、9、10、11、12であり、 13、14、15。 この他の矢印はちょうど表し メモリ位置15にマップされます。 しかし、再び、プログラマは一般的にありません このレベルの詳細を気にしません。 そして、ほとんどすべてのプログラミングで 言語今日、プログラマ どこまでもメモリ内知ることができません これらの数値は実際にあります。 彼または彼女は気にしなければならないすべてがあります 彼らは何とか一緒にリンクされていること このようなデータ構造です。 しかし、それはない判明します あまりにも技術的な取得します。 しかし、単に、おそらく私達ができるので、 ここでこの議論を持っている余裕、 我々が再訪するとし ここでは、アレイのこの問題。 私たちはここに行く後悔どうかを見てみましょう。 これは100、90、75、および80です。 私は簡単にこの主張を作ってみましょう。 これは配列で、再び、 配列の顕著な特徴 すべてのデータがバックにあるということです バック文字通りmemory--にバックアップします 1バイトまたは多分4バイト、 離れバイトのいくつかの固定数。 リンクされたリストでは、描画可能性があります このように、ボンネットの下に人 その原料がどこにあるか知っていますか？ それも、このような流れにする必要はありません。 データの一部がかもしれません 戻ってそこまで左へ。 あなたも知りません。 そして、そのように配列して、あなたが持っています ランダムアクセスと呼ばれる機能。 そして、何ランダムアクセス手段は、あります コンピュータが瞬時にジャンプできます アレイ内の任意の場所にコピーします。 どうして？ コンピュータが知っているので 最初の場所があることを ゼロ、一、二、三。 だからあなたから移動する場合 次の要素にこの要素、 で文字通り、 コンピュータの心は、ちょうど1を追加します。 あなたが三番目の要素に行きたい場合は、 ただ単に、次の要素を選ぶ - 追加 1を追加します。 ただし、このバージョンで 物語の、仮定 コンピュータは、現在募集しています で、または数100を扱います。 どのようにして、次に行きますか グレード帳にグレード？ あなたは7を取らなければなりません 任意であるステップ、。 次のいずれかに取得するには、あなたがする必要はあり 15に到達するために、別の8つのステップを取ります。 言い換えれば、それはありません 数字の間に一定のギャップ、 ので、それだけで取ります コンピュータより多くの時間がポイントです。 コンピュータが検索する必要があります 順番にメモリを介して、 あなたが探しているものを見つけることができます。 だからアレイはなる傾向にあるのに対し、 あなたのための高速データstructure-- 文字通り簡単な計算を行うことができます あなたがしたい場所と、1を追加することにより取得 リンクリストをinstance--ため、 あなたは、その機能を生け贄に捧げます。 あなたは最初から行くことができません 第2〜第4の三番目にします。 あなたがマップに従わなければなりません。 あなたはより多くのステップを取る必要があります これらの値を取得するには、どの コストを追加するように思われます。 だから我々は、価格を支払うが、何だったしています ダンはここに求めていた機能？ どのようなリンクリストを行います どうやら私たちが行うことができ、 の起源でした この特定の話？ その通りです。 それへの動的なサイズ。 私たちは、このリストに追加することができます。 我々はそうであっても、リストを縮小することができます 私たちはできるだけ多くのメモリを使用していること 私たちは、実際に必要となるように 我々は過剰割当んじゃないんです。 今、本当にNIT-うるさいします、 隠れたコストがあります。 だからあなたは私だけでは納得せてはなりません あなたは、これは魅力的なトレードオフであること。 ここでもう一つの隠れたコストがあります。 利点は、明確にします 私たちは活力を得ることです。 私は別の要素が必要な場合、私はちょうどすることができます それを描き、そこに数字を入れて。 そして、私はそれをリンクすることができます ここでは画像と、 こっちのに対し、再び、私がしている場合 コー​​ナーに自分自身を描きました、 何か他のものは、すでに使用している場合 ここで、メモリは、私が運の尽きです。 私はコーナーに自分自身を描いてきました。 しかし、隠しは何ですか この写真の中のコスト？ それだけの量ではありません それにかかる時間 ここまでここから行くために、 次いで、7つのステップであります 複数のである8つのステップ、。 別の隠されたコストは何ですか？ だけでなく、時間。 追加情報があります この絵を達成するために必要な。 うん、そのマップのそれらのほとんどのスクラップ 紙、私は、それらを記述しておくように。 これらのarrows--これらは無料ではありません。 あなたが知っていますcomputer-- コンピュータが持っているもの。 これは、0と1を持っています。 あなたは、矢印や表現したい場合 マップや数は、あなたはいくつかのメモリを必要としています。 他の価格ですから リンクリストのために支払います、 一般的なコンピュータサイエンス リソースは、スペースもあります。 そして実際そうなので、一般的に、 トレードオフの間で ソフトウェアエンジニアリングの設計に システム時間とspace--です あなたの成分の2、2つです あなたの最も高価な成分の。 これは私に多くの時間を原価計算されています 私はこのマップに従わなければならないので、 それはまた、私に多くのスペースを原価計算です 私の周りこのマップを維持する必要があるため。 私たちは一種のきたようにそう願って、 昨日と今日の上に議論し、 メリットということです コストを上回るだろう。 しかし、ここで明らかな解決策はありません。 多分それはありますbetter-- ラ迅速かつ汚いです、 カリームはearlier--提案されているように 問題のメモリをスローします。 ただ、より多くのメモリを購入し、少ないと思います 問題の解決について、ハード、 そして簡単な方法でそれを解決します。 そして実際、以前、時 我々は、トレードオフについて話しました、 それはスペースはありませんでした コンピュータと時刻。 それは、その開発者の時間でした さらに別のリソースです。 だから、再び、それはこの綱渡りです それらのもののどれを決定しよう あなたが費やすことをいといませんか？ 最も安価どれですか？ どちらが良い結果をもたらしますか？ ええ？ 確かに。 この場合は、あなたがしている場合 maps--で表す数字 これらは、多くの言語で呼ばれています 「ポインタ」または「アドレス」 - それはダブルスペースです。 それがあれば、二重のように悪いである必要はありません 今、私たちは数字だけを保存しています。 私たちが保存されたと仮定し hospital--で患者記録 そうピアソンの名前、電話番号、 社会保障番号、医者 歴史。 このボックスには、多くの可能性があります その場合には、はるかに大きいです 小さな小さなポインタのアドレス 次は、それは大したことではないのですelement--。 このようなフリンジです それは問題ではありませんかかります。 しかし、この場合には、ええ、それは倍増です。 良い質問。 それでは、時間Aについてお話しましょう もう少し具体的に。 走行時間は何ですか このリストを検索しますか？ 私が検索したいと すべての生徒の学年を通して、 そしてnグレードがあります このデータ構造です。 ここでは、あまりにも、私たちは借りることができます 以前の語彙。 これは、線形データ構造です。 n個のビッグOは、取得するために必要なのものです このデータ構造の終わりに、 whereas--と我々は見ていません このアレイはあなたを与えますbefore-- 何を意味し、一定の時間と呼ばれています 1段階または2段階または10 steps-- 関係ない。 これは、固定された数です。 これは、とは何の関係もありません 配列のサイズ。 そして、その理由、 再度、ランダムアクセスです。 コンピュータは、ちょうどすぐにすることができます 別の場所にジャンプし、 それらはすべて同じだから 他のすべてからの距離。 関与しない考えはありません。 大丈夫。 私ができるのであれば、私にしてみましょう 2つの最終絵を描きます。 ハッシュテーブルとして知られている非常に一般的なもの。 だから、この議論をやる気にします、 私はこれを行う方法について考えてみましょう。 だから、これはどう？ 問題があるとし 我々は今、解決したいです dictionary--に実施しています 英語の単語のように全体の束 または何でも。 そして目標はお答えすることができることです フォームの質問これは言葉ですか？ だから、実装したいです ちょうどスペルチェッカー、 物理的な辞書のような あなたが物事を見ることができます。 私は配列でこれを行うためにあったとします。 私はこれを行うことができます。 そして、言葉はリンゴであると仮定 そして、バナナやメロン。 そして、私は果物を​​考えることはできません それがdで始まるので、私たちはただです 3果物を持っているつもり。 だから、これは配列であり、我々はしています これらの言葉のすべてを保存します 配列としてこの辞書インチ 質問は、その後、どのように他であります あなたは、この情報を保存することができますか？ まあ、私はので、ここでの不正行為のようなものです ワード内のこれらの各文字 本当に個々のバイトです。 だから私は本当にになりたい場合 NIT-うるさい、私は本当にすべき はるかにこれを分割すること メモリの小さな塊、 私たちはまさにそれを行うことができます。 しかし、我々はに実行するつもりです 前と同じ問題。 何メリアム・ウェブスターやオックスフォードなど、場合 すべてのは、彼らが単語を追加year--ん dictionary--に我々にはありません 必ずしも自分自身をペイントします 配列の角に？ だからではなく、多分賢くアプローチ 自ノードまたはボックスにリンゴを置くことです、 私たちが言うように、バナナ、および そして、ここではマスクメロンを持っています。 そして、我々の文字列これらの事を一緒に。 だから、これは配列で、 これは、リンクされたリストです。 あなたは非常に見ることができない場合は、それだけで 「アレイ」は、言うとこれが言う「リスト」 だから我々は同じを持っています 以前のように正確な問題、 それによって私たちが今持っています 私たちのリンクリスト内のダイナミズム。 しかし、我々はかなり遅いの辞書を持っています。 私は単語を検索するとします。 それは私に、nの大きなOがかかる場合があります 手順、言葉は可能性があるため、 の終了時にすべての方法であります マスクメロンのようなリスト、。 そして、それはことが判明します プログラミングで、並べ替え データの聖杯の 構造は、何かであります それはあなたが一定の与え 配列のような時間 それはまだあなたにダイナミズムを与えます。 だから我々は両方の長所を持つことができますか？ そして実際、何かがあります ハッシュテーブルと呼ばれます それはあなたが正確に行うことができます 約いえ、その。 ハッシュテーブルは愛好家であります 我々のデータ構造 以下のように考えることができます array--の組み合わせ 私はそれを描くつもりです this--とリンクリストのような 私はここの上にこのよう描くだろうと。 この事と方法 作品は次の通りです。 このnow--ハッシュ場合table-- 私の第3のデータ構造です、 そして、私は保存したいです この内の単語、私はしないでください ただのすべてを保存します 言葉が背中合わせに背中合わせにします。 私はいくつかを利用したいです 情報の一部 できるようになる言葉について それは高速ですどこ私はそれを取得します。 だから、言葉のリンゴを与えられました バナナやメロン、 私は意図的にそれらの単語を選択しました。 どうして？ ソートの根本的に何 3については違うのですか？ 明白とは何ですか？ 彼らは別の文字で始まります。 だからあなたは何を知っていますか？ 内のすべての私の言葉を置くのではなく 同じバケット、いわば、 一つの大きなリストのように、なぜしません 私は、少なくとも最適化をしてみてください そして、私のリストは1月26日限り行います。 説得力の最適化 なぜしない可能性があります I--単語を挿入するとき このデータ構造に、 コンピュータのメモリに、なぜ 私は、ここにすべての ''の単語を入れていません ここにすべての 'B'の言葉、 ここでは、すべての 'C'の言葉？ だから、これはリンゴを入れて終わります ここでは、ここではバナナ、ここではマスクメロン、 など。 そして、私は追加している場合 言葉は別の何like--？ アップル、バナナ、梨。 誰もがフルーツを考えます すなわち、B、またはCで始まりますか？ Blueberry--完璧。 それがここで終わるしようとしています。 そして、私たちは持っているように見えます わずかによりよい解決策、 今私がしたい場合のため リンゴを検索するには、I first--私はダイビングをしません 私のデータ構造に。 私は自分のコンピュータのメモリに飛び込むません。 私は、最初の最初の文字を見てください。 そして、これはどのようなコンピュータであり、 科学者は言うでしょう。 あなたのデータ構造にハッシュ。 あなたの入力、中を取ります この場合は、リンゴのような言葉です。 あなたが見て、それを分析します この場合の最初の文字、 それによって、それをハッシュします。 ハッシュは、一般的な用語のそれによってです あなたが入力として何かを取ります あなたは、いくつかの出力を生成します。 そして、その中で出力 場合は、場所です あなたは、最初に検索したいです 位置、第二の位置、第三。 だから入力はリンゴです、 出力は最初のものです。 入力は、バナナであります 出力は、第2にする必要があります。 入力は、マスクメロンです 出力は、第三にする必要があります。 入力は、ブルーベリーであります 出力は再び第二にする必要があります。 そして、それはあなたが取ることができますものです あなたの記憶を通じショートカット 言葉を得るために またはデータをより効果的に。 さて、これは潜在的に私たちの時間をダウンカット 26のうち1と同じくらいすることにより、 あなたはあなたと仮定した場合のため 「Z」のように多くの ""の単語を持っています 「Q」の単語などの単語、どの 本当にrealistic--されていません あなたは全体のスキューを持っているつもりです alphabet--の特定の文字 これは増分になります 許可しないアプローチ あなたがはるかに迅速に言葉を取得します。 そして、現実には、洗練されました プログラム、世界のグーグル、 world--のFacebooks それらは、ハッシュテーブルを使用します 異なる目的の多くのために。 しかし、彼らはほどナイーブではないでしょう ただ最初の文字を見て リンゴやバナナや 梨やメロン、 あなたはこれらを見ることができるよう理由 リストには、まだ長い得ることができます。 そして、これはまだソート可能性があります linear--のように一種の遅いです、 n個の大きなOを持つように 我々は先に説明しました。 それでは、本当の良いハッシュテーブルはなります それははるかに大きな配列を持つことになりますdo--。 そして、それははるかに使用します。 洗練されたハッシュ関数、 それだけで "。"を見ないように、 多分それは「-P-P-L-E」を見て、 何とかそれらの5文字を​​変換し、 どこの場所へ リンゴが保存されるべきです。 私達はちょうど単純に文字 ''を使用しています それは素晴らしく、シンプルだから、一人で。 しかし、ハッシュテーブル、中 最後に、あなたが考えることができます の組み合わせとしての アレイ、各 その理想的にリンクされたリストを持っています できるだけ短くあるべきです。 そして、これは明白な解決策ではありません。 微調整の実際には、多くの それはときにボンネットの下に行きます これらの種類を実装します 高度なデータ構造 右が何であるかであります 配列の長さは？ 右のハッシュ関数とは何ですか？ どのようにメモリに物事を格納していますか？ しかし、どのように迅速に実現 議論のこの種 これまでのところ、それはようなものだということのいずれか、エスカレート この時点で、自分の頭の上の、どの 結構です。 しかし、我々は本当にと、リコールを開始しました 何か低レベルと電子。 そしてこれは、再びこれです 抽象化のテーマは、 どこにあなたが取ることを始めると 付与され、[OK]を、私はそこだit--持っています 物理メモリ、OK、それを持って、すべての 物理的な位置は、アドレスを持っています [OK]を、私はそれは、私が表現することができました arrows--としてそれらのアドレス あなたは非常に迅速に持って始めることができます より洗練された会話のこと 最後に私たちを可能にしているように見えます 検索のような問題を解決するために そして、より効果的にソート。 そして、too--安心 私はこれを考えるので 我々はいくつかに行ってきた最も深いです 私たちがきたproper--これらのCSトピックの この時に日半で行われ あなたは一般的にオーバーするかもしれないものを指します 学期中の8週間のコース。 これらの上の任意の質問？ なし？ 大丈夫。 さて、なぜ私たちはそこに一時停止しませんが、 数分早い昼食を開始し、 ちょうど約1時間で再開？ そして、私はのために残りますよ 質問を少し。 それから私は行かなければならないつもりです それがOKかどうカップルの呼び出しを取ります。 私は、その間にいくつかの音楽をオンにします しかし昼食は、角を回っにする必要があります。