วีดีโอ

40:22 の辺りで忘れてしまったといった不等式の証明は説明欄 (概要欄) に書きましたので，そちらをご参照ください．

Love from India 🇮🇳

ありがとうございます。統計学を勉強中の身で、数式ばかりでﾅﾆｺﾚ状態でしたが、オートマトンは知っていたので、数式が表していることのイメージができました。

52:13 56:00 「なぜ？」の説明は次の補足動画に載せました．つまってしまい，すみません．th-cam.com/video/VFZXkI2oZ1A/w-d-xo.html

補足 (修正) 42:17 「EDDの最大納期遅れ」と書いてあるのは「EDDの最大納期ずれ」と読み直してください．この囲みが後で現れるときも同様です．口頭でも混乱していますが，今回は「納期遅れ」を扱っていないので，そういっている場合は全部「納期ずれ」だと思ってください． 51:51 Moore-Hodgsonのアルゴリズムでは，「1. EDD順でジョブを処理しようとする」という「しようとする」をした瞬間に，そのジョブは「仮に間に合うジョブ」としていると見なしてください．そして，納期に間に合わない場合は，それも含めて最大処理時間のジョブを遅れるジョブとします．実際，次のページの例ではそうなっています．

どうでもいい話ですが、このメンガーさんはKarl Mengerさんで、お父さんはCarl Mengerさんだそうです。

グラフの直積のところで double the points again!を思い出しました

素晴らしい講義でした。Edmondsのblossom algorithmの原論文を読もうとして挫折していましたが、再度挑戦してみたいと思います。

55:42 → この辺りから音声が消えていますが，その後で復帰して，音声が消えていた部分の内容は音声付きで説明されます．その点，ご了承ください． 56:58 → ここから音声が復帰します． なお動画中では編集するかもしれないと言っていますが，編集は行っておらず，いわゆる「撮って出し」になっています．よろしくお願いします．

訂正 1:19:51 例1において「=1」は誤りで，正しくは「=0」です． 1:27:45 例3の解答例において「43」と書いてあるところはすべて「41」が正しい数値です．つまり，答えも「x=43」ではなく「x=41」が正しいものとなります．

半年ほど「公開」にし忘れていました．すみません．

18:04 このページ (14ページ) において，「(√(5) - 1)/2」と書かれている部分はすべて「(1-√(5))/2」が正しいです．ここで訂正します．すみません．

素晴らしい講義動画を公開していただきありがとうございます。特にユークリッドの互除法の計算量についての話が面白かったです。次回が楽しみです。 55:38 先生が今回の講義では（簡単だから？）省略された箇所について、私は以下のように考えました。もしかしたら間違っているかもしれませんが。 bをn以下の任意の自然数として固定する。 (1) b=0のときには、max_{a≧1} {gcd(a, b)の実行で出力されるGの数} = 1 (2) bが1以上n以下の自然数のときには、max_{a≧1} {gcd(a, b)の実行で出力されるGの数}は、 1 + （gcd(b, 0)の実行で出力されるGの数）、 1 + （gcd(b, 1)の実行で出力されるGの数）、 … 1 + （gcd(b, b - 1)の実行で出力されるGの数） のうち最大の数に等しい。 (1), (2)どちらの場合も、max_{a≧1} {gcd(a, b)の実行で出力されるGの数}は有限。 よって、max_{a≧1, b≦n} {gcd(a, b)の実行で出力されるGの数}も有限。

訂正があります． 1:02:52 ここに書かれている性質は正しいですが，証明が正しくありません．正しくするためには，KG((k-2)g, (k-2)(g-1)/2)を考えればよいです． 1:04:52 正しくない元凶は，χ(KG(n, k)) = n-2k+1 という正しくない等式を使ってしまったからです．正しい等式はχ(KG(n, k)) = n-2k+2です． 1:11:46 そのため，ここに挙げる例も間違っています．G1 = K3 としたとき，証明に基づいてG2, G3, G4を構成すると，正しくは，G2 = KG(10, 4), G3 = KG(21, 9), G4 = KG(36, 16) となります．

スライド21ページと26ページの図は間違っています．すみません．正しい図については修正した講義スライドをご覧ください．

スライド21ページと26ページの図は間違っています．すみません．正しい図については修正した講義スライドをご覧ください．

1:05:10 仮定より「i(KG(n,k)) > i(KG(n',k'))」となるのは誤りで，正しくは「i(KG(n,k)) < i(KG(n',k'))」となります． 1:06:12 非準同型補題で，「i(G) ≦ i(H)」は誤りで，正しくは「i(G) ≧ i(H)」です．すみません．

岡本さんご無沙汰しております，早水です！TH-camの講義動画を拝見しました（チャンネル登録しました！）．私のほうもちょうど今週TH-camで平面グラフに関する講義をする予定なので大変有益でした． 21:41 のplanarity.net はリンク切れ？なのか少なくとも私は使えなかったのですが www.jasondavies.com/planarity/ は使えました．こんなサイトがあるんですね，私の授業でも紹介させていただこうと思います．日本地図の塗り絵など有用な画像がてんこ盛りのスライドで，Creative Commons Attribution licence (reuse allowed)とのことですので，もしも部分的に使わせて頂く場合はお名前と出典URLを明記したうえで活用させていただきます．よろしくお願いいたします．

1:06:22 ここで説明している重みの付け方だと，「最大重みマッチング」ではなく，「最大重み最大マッチング」，つまり，最大マッチングの中で最も重みが大きいものを見つける必要があります．その意味で，ここの説明は不正確です．すみません．ただ，別の重みの付け方をすれば，「最大重みマッチング」を考えるだけで済みます．

Hopcroft - Karpのアルゴリズムの計算量について非常に分かりやすい証明・説明でした。以前、HopcroftとKarpがこのアルゴリズムを発表したわずか6ページ半の論文が読み切れなかったのですが、この講義動画を見終わった今は読み切れると思います。HopcroftとKarpは、講義で説明していただいたようないくつかの議論の末に、よく最後まで証明し切ったなーと感動しました。

今回の講義も非常に分かりやすかったです。後半のHopcroft - Karpのアルゴリズムのアイディアも非常に分かりやすかったです。なぜHopcroft - Karpのアルゴリズムが速いのかの理由がよく分かりました。次の講義動画である「第3回補足」は難しいだろうと思いますが、何とか理解したいと思います。

驚くほど分かりやすい講義でした。弱双対性、強双対性という考え方を表に出さずに説明している本しか読んだことがなかったのですが、弱双対性、強双対性という考え方により、ややこしい議論がスッキリすると思いました。エレガントな講義をありがとうございました。

このような日本語での講義動画を待っていました。完全な初心者向けのアルゴリズムの本には載っていない内容を、マッチングに絞って解説してくださるというのがいいと思いました。43:19 このあたりの解説が非常に興味深く、次回以降の講義を見るのが楽しみです。Hopcroft - Karpのアルゴリズムには興味があるので特に楽しみです。

55:50 「Q4」とあるのは「Q5」の間違いです．すみません．

Hello, Mr. Okamoto, how could I get the lecture notes and PPT of your lecture? こんにちは、岡本先生、どうすれば講義ノートと講義のPPTを入手できますか。ありがとうございました。

1:20:27 (スライド31ページ)：下に手で書いてある「9/100」は間違いで，正しくは「91/100」です．図は合ってます．すみません．

16:54 (スライド14ページ)：「+X_S」は間違いで，正しくは「-X_S」です．すみません．

訂正があります．混乱してしまい，すみません． 0:31:33 ・「IF x3 = 0 THEN x0 := 1 ELSE x0 := 0」を「IF x3 = 0 THEN x0 := 0 ELSE x0 := 1」に修正． 1:16:59 ・「isHalting(x1, x2) = 1」のままで正しいです． 1:26:20 ・ここも「isHalting(x1, x2) = 1」のままで正しいです．