General Information
Discrete Structures というのは奇妙な名前です – Discrete Mathematics という方が分かりやすいと思います。 これは基本的に、連続的でない数学 (たとえば微積分) を意味します。
前提条件
なし
扱うトピック
- 集合、関数、関係
- 証明のテクニック。 帰納法
- 整数論と公開鍵暗号
- 計数と組合せ論
- 確率
- 論理
- グラフ理論
- 有限オートマトンと正規言語
- 文脈依存型自由言語
- 計算可能性とNP-completeness証明に多くの時間を費やし、帰納法による証明に重点を置いている。
ワークロード
通常、毎週問題集があり、予備試験が2-3回、期末試験があります。 歴史的に、宿題は成績に占める割合が比較的大きいです。 このコースにはプログラミングはなく、作業量は学期を通してそれなりに一定しています。
General Advice
CS2110と同時に受講することは、非常に管理しやすく、有益である。 特に帰納法やグラフ理論に関するトピックは重なる部分が多く（最近は特に2110が証明に重点を置かなくなったので重なりは少なくなっていますが）、2回見ることができるのは助かります。 この授業は多くのCSの基礎となるものなので、それなりに早めに受講しておくと良い。 グラフ理論と証明を学ぶことは、多くの上級コースや一般的なCSにとってそれなりに重要です。
推薦・必修の教科書がとても役に立ちました！
推薦・必修の教科書がとても役に立ちました！
推薦・必修の教科書がとても役に立ちました。 授業で簡単に説明された多くのトピックが、教科書では深く掘り下げて説明されていました。 教科書を読み、例題に目を通すことで、テストの点数が上がりました。
教科書は買わないでください。 また、問題集がある日はオフィスアワーが混雑します。
学生TAの中で数学を専攻している人を見つけて、彼らに助けを求めましょう。 2800は理論のクラスなので、CSの人よりも数学専攻の人のほうが詳しいでしょう。 また、前述したように、グラフ理論や証明など、学ぶ内容のほとんどは、様々な問題の推論に非常に役立ちます。
受講者の声
バート・セルマンと一緒に、このクラスは本当に簡単だと思いました。
私は高校時代に数学に熱中しており、数論や組合せ論をやっていましたが、この授業はそれ以上進展しませんでした。 また、基本的にこのコースのもっと難しいバージョンであるMATH 3360を同時に取ったので、結局2800ではほとんど何も学べませんでした。
Passで取りました。 このクラスはふざけたもので、新しい材料はほとんど学びませんでしたが、ほとんどが今までの授業で正式に出てこなかったランダムな数学の良い復習になりました。 メンテナンスが少なく、十分に面白いですが。
Kozen（2013年秋）コースはひどく難しいものではありませんでしたが、他の証言から想像されるよりも難しいものでした。 このコースでは、8つの問題集があり、それぞれ数時間かかりました。 試験中の難易度はそれなりでしたが、授業中の予習は与えられた時間内に終わらせるのが大変でした。 (ファイナルには十分な時間がありました。)離散数学のクラスを既に取っていない限り、多くのトピックを初めて目にすることになることを認識してください。
Kozen (Fall 2013): Kozenは非常に良い講師で、すべてを詳しく説明してくれました。 問題は、幅の広いクラスがすべきことよりもはるかに詳細に説明してくれたので、私たちは多くの異なるトピックをすぐにまともな深さで学ぶことになったことです。 それでもあまり難しくはないのですが、その分資料が多く、試験のために暗記しなければならない具体的な内容も多くありました（上記の体験談がよく説明しています）。 Passのコースノート（下記リンク参照）は非常に有用でしたが、Kozenはいくつかの異なるテーマを扱っていました。 本はあまり役に立ちませんでしたが、いくつかの問題が本からだったので必要でした。
Graeme Bailey (Spring 2014): かなり驚きの連続でした。 このクラスは比較的簡単という評判ですが、今学期の教材は非常に難しかったです。 通常のトピックに加え、Bailey は様々な抽象代数学、特に群論に多くの時間を費やした。
毎週の宿題は通常水曜日に出され、次の月曜日が提出期限でした（10日間の約束でしたが、5日間以上できたことはほとんどありませんでした）。 それらは非常に証明集約的で、10 ～ 15 時間以上の相当な時間がかかりました。 ごく少数の数学専攻の学生は別として、ほとんどの TA は問題の解き方を知らないので宿題を手伝うことができず、オフィスアワーを私たちと一緒にバタバタ過ごすだけでした。
にもかかわらず、ベイリーは学生を助けるために顕著な努力をして、追加のオフィスアワーを設け、ピアッツァにすばやく対応しました。 テストは授業中か夜間に行われましたが、驚くほど公平でした。 最後に一言。 このクラスは、私が望んでいたよりも多くの努力をし、おそらく離散数学について多くのことを学びましたが、できるならば、より簡単な教授を取りたいと思います。 私は個人的にこのクラスを本当に楽しんで、材料が面白いと感じたが、YMMV。 ワークロードは管理可能でしたが、うまくやるにはオフィスアワー（COVID以前は本当に夜遅くまで開催されていた）がかなり必要でした。 隔週で発表される問題集は月曜から水曜まで、翌週の金曜が締め切りで、パートナーと一緒に取り組むことができました。 講義は（COVID以前は）授業前にコースWikiの「予習」を読むことになっていて、授業はほとんど例題とiClickerの問題で概念を補強して過ごしました。 オンライン化された後の講義では、講義の中でより多くの内容を学ぶことができました。
過去の授業
Hopcroft は通常秋に、Pass は春にこの授業を行います。 Kozenは2013年秋にこれを教えていますが。 2014年秋にはマイケル・ジョージが引き継ぎました。 2020年秋からはAnke van Zuylenがこれを担当する予定です
。