ENGLISH    |  

離散数学入門

離散数学入門/2017

概要

情報科学および自然言語処理の基礎となる離散数学を学ぶために、 M1 の人たちを対象に教科書の演習問題を中心とした離散数学の勉強会を行なっています。

  • 研究室の他の勉強会とは異なり、授業『自然言語処理学特論』として必修単位が割り当てられている勉強会です。欠席すると授業を欠席した扱いになるので注意してください。
  • 欠席する場合, TA 全員にメールを送信してください。
  • シラバスはこちら

2016年度はゼミ、輪読形式で行います。

  • 各節ごとに担当者を1名ずつ割り当てます。各節の担当者は、その節の内容に関して参加者から質問があった場合に答えられるように、勉強会の時間までにしっかり準備・予習してきてください。
  • 担当者以外の参加者も、事前に予習して、少なくとも「どこが分からないかが分からない」ということがないようにしてきてください。
  • 各節・各章に演習問題があります。演習問題の一部を割り当てますので、担当者全員で協力して解いてきてください。勉強会の時間に演習形式で発表してもらいます。開始前にあらかじめ板書しておくか、レジュメに解答をまとめておくか、プレゼン形式で発表するか、好きな形式で発表してもらって構いません。
  • 欠席する場合,担当している演習問題は次の勉強会で発表してください。

使用する教科書は Essentials of Discrete Mathematics. David J. Hunter, 2010, Jones & Bartlett Learning.です。

日時

毎週月曜日9:20

TA

担当者・参加者ともに、分からないことがあれば勉強会の時間外でも構いませんので気軽に TA に質問してください。

  • 4/25: 東, 重藤, 濱口
  • 5/2: 近藤, 大村, 吉本
  • 5/9: 東, 濱口, 重藤
  • 5/16: 近藤, 吉本, 澤井
  • 5/23: 近藤, 大村, 東
  • 6/6: 近藤, 大村
  • 6/13: 近藤, 大村, 東
  • 6/20: 椿, 近藤
  • 6/27: 椿, 東
  • 7/4: 重藤, 大村
  • 7/11: 椿, 重藤, 東
  • 7/25: 澤井, 重藤
  • 10/17: 東, 吉本, 近藤(D1)
  • 10/24: 大村, 近藤(D1), 森元
  • 10/31: 近藤, 吉本, 大村
  • 11/7: 近藤, 吉本, 近藤(D1)
  • 11/14: 東, 吉本, 加藤
  • 11/21: 椿, 吉本, 加藤
  • 12/5: 東, 大村, 澤井
  • 12/12: 濱口, 大村, 澤井
  • 12/19: 東, 濱口, An

参加者

  • Muhaimin Hading (Emi) - 1, 2期のみ
  • 劉 君 (Jun Liu) - 1, 2期のみ
  • 井上 剛 (Go Inoue)
  • 太田 瑤子 (Yoko Ohta)
  • 久保 大輝 (Daiki Kubo)
  • 小比田 涼介 (Ryosuke Kohita)
  • 佐藤 元紀 (Motoki Sato)
  • 澤山 熱気 (Atsuki Sawayama)
  • 寺西 裕紀 (Hiroki Teranishi)
  • 真鍋 陽俊 (Hitoshi Manabe)
  • 劉 欣然 (Xinran Liu)
  • 左 永 (Yong Zuo)
  • 堀江 卓弘 (Takahiro Horie)
  • Michael Wentao Li
  • 盧 宇勲 (Yuxun Lu)

出欠確認

  • ◎: 出席して,演習問題も解いている
  • ◯: 出席した (演習問題はなんらかの理由により解いていない)
  • △: 欠席したが,別の日に演習問題を解いた (もしくは,割り当てられていなかった)
Emi劉君井上太田久保小比田佐藤澤山寺西真鍋劉 欣然堀江Michael備考
4/251.1
5/21.2
5/91.3
5/161.4
5/231.5
5/30-
6/62.1
6/132.2
6/202.3
6/272.4
7/4○?2.5
7/112.6
10/17(連絡あり)3.1, 3.2
10/243.3, 3.4
10/31(連絡あり)3.5, 4.1
11/74.2, 4.3
11/144.4, 4.5
11/214.6, 5.1
12/55.2, 5.3
12/125.4, 5.5

担当

Chapter 1 Logical Thinking

  • 1.1 Formal Logic (TA: Shigeto)
    • Exercises: 1 (Emi), 6 (Jun Liu), 7 (Inoue), 10 (Ohta), 11 (Kubo), 12 (Kohita), 16, 17, 18, 22, 23
  • 1.2 Propositional Logic (Emi)
    • Exercises: 6 (Sato), 14 (Sawayama), 23 (Teranishi), 25 (Manabe), 26 (Xinran Liu), 27 (Zuo)
  • 1.3 Predicate Logic (Jun Liu) - see the errata
    • Exercises: 4 (Emi), 7 (Jun Liu), 10 (Inoue), 17 (Ohta), 19 (Kubo), 20 (Kohita)
  • 1.4 Logic in Mathematics (Inoue) - see the errata
    • Exercises: 6 (Sato), 8 (Sawayama), 10 (Teranishi), 12 (Manabe), 18 (Xinran Liu), 26(Zuo)
  • 1.5 Methods of Proof (Ohta)
    • Exercises: 6 (Emi), 11 (Jun Liu), 14 (Inoue), 17 (Ohta), 24 (Kubo), 25 (Kohita)

Chapter 2 Relational Thinking

  • 2.1 Graphs (Kubo)
    • Exercises: 3 (Sawayama), 6 (Teranishi), 8 (Manabe), 11 (Xinran Liu), 19 (Zuo), 27 (Sato), 29 ()
  • 2.2 Sets (Kohita)
    • Exercises: 1 (Jun Liu), 2 (Inoue), 5 (Ohta), 10 (Kubo), 23 (Kohita), 27 (Emi)
  • 2.3 Functions (Sato)
    • Exercises: 6 (Teranishi), 17 (Manabe), 22 (Xinran Liu), 28 (Zuo), 30 (Sato), 36 (Sawayama)
  • 2.4 Relations and Equivalences (Sawayama)
    • Exercises: 3 (Inoue), 11 (Ohta), 27 (Kubo), 30 (Kohita), 32 (Emi), 34(Jun Liu)
  • 2.5 Partial Orderings (Teranishi)
    • Exercises: 11 (Manabe), 13 (Xinran Liu), 15 (Zuo), 18 (Sato), 22 (Sawayama), 29 (Teranishi)
  • 2.6 Graph Theory (Manabe)
    • Exercises: 4 (Ohta), 11(Kubo), 13 (Kohita), 17 (Emi), 18 (Jun Liu), 28, 30 (Inoue)

Chapter 3 Recursive Thinking

  • 3.1 Recurrence Relations (Xinran Liu)
    • Exercises: 4 (Xinran Liu), 22 (Zuo), 23 (Sato), 24 (Sawayama), 27 (Teranishi), 29 (Manabe)
  • 3.2 Closed-Form Solutions and Induction (Yong Zuo)
    • Exercises: 1 (Kubo), 3 (Kohita), 10 (Inoue), 15 (Ohta), 21(Manabe)
  • 3.3 Recursive Definitions (Horie)
    • Exercises: 2 (Xinran Liu), 11 (Zuo), 20 (Horie), 21 (Michael), 22 (Lu)
  • 3.4 Proof by Induction(Michael)
    • Exercises: 1 (Inoue), 5 (Ohta), 8 (Kubo), 13(Kohita), 22 (Sato), 24 (Sawayama)
  • 3.5 Recursive Data Structures(Lu)
    • Exercises: 5 (Teranishi), 7 (Manabe), 11 (Xinran Liu), 17 (Zuo), 20 (Horie), 22 (Michael)

Chapter 4 Quantitative Thinking

  • 4.1 Basic Counting Techniques(Inoue)
    • Exercises: 2(Lu), 5(Inoue), 11(Ohta), 16(Kubo), 19(Kohita), 22(Sato)
  • 4.2 Selections and Arrangements - see the errata(Ohta)
    • Exercises: 5(Sawayama), 8(Teranishi), 11(Manabe), 14(Xinran Liu), 23(Zuo), 24(Horie)
  • 4.3 Counting with Functions(Kubo)
    • Exercises: 4(Michael), 6(Lu), 14(Inoue), 19(Ohta), 25(Kubo), 30(Kohita)
  • 4.4 Discrete Probability(Kohita)
    • Exercises: 10(Sato), 13(Sawayama), 18(Teranishi), 20(Manabe), 22(Xinran Liu), 27(Zuo)
  • 4.5 Counting Operations in Algorithms(Sato)
    • Exercises: 4(Horie), 9(Michael), 15(Lu), 21(Inoue), 22(Ohta)
  • 4.6 Estimation(Sawayama)
    • Exercises: 1(Kubo), 4(Kohita), 12(Sato), 19(Sawayama), 20(Teranishi), 22(Manabe), 25(Xinran Liu), 27(Zuo)

Chapter 5 Analytical Thinking

  • 5.1 Algorithms(Teranishi)
    • Exercises: 7(Horie), 10(Michael), 17(Lu), 21(Inoue) , 23(Ohta)
  • 5.2 Three Common Types of Algorithms(Manabe)
    • Exercises: 2(Kubo), 3(Kohita), 13(Sato), 16(Sawayama), 17(Teranishi), 21(Manabe), 22(Xinran Liu)
  • 5.3 Algorithm Complexity(Xinran Liu)
    • Exercises: 3(Zuo), 4(Horie), 7(Michael), 12(Lu), 15(Inoue), 20(Ohta)
  • 5.4 Bounds on Complexity (Zuo)
    • Exercises: 4(Kubo), 6(Kohita), 10(Sato), 15(Sawayama), 17(Teranishi), 22(Manabe)
  • 5.5 Program Verification(Horie)
    • Exercises: 4(Xinran Liu), 5(Zuo), 6(Horie), 11(Michael), 16(Lu), 18(Inoue)
  • 5.6 Loop Invariants(Michael)
    • Exercises: 3(Ohta), 9(Kubo), 12(Kohita), 13(Sato), 16(Sawayama), 20(Teranishi)