情報数学 第15回 全体のまとめ 中間試験の結果 2015年度 情報数学中間試験分布 25 20 最高点：97 平均点：72.8 15 10 5 0 ～40 ～50 ～60 ～70 ～80 ～90 ～100 設問ごとの得点分布 25 20 15 10 5 0 1-(1) 1-(2) 1-(3) 1-(4) 1-(5) 2 3-(1) 3-(2) 3-(3) 4-(1) 4-(2) 4-(3) 設問ごとの正解率 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 1-(1) 1-(2) 1-(3) 1-(4) 1-(5) 2 3-(1) 3-(2) 3-(3) 4-(1) 4-(2) 4-(3) 全体のまとめ 第1章 論理と証明 • 真理値表が作れるか？ – AND、OR、XOR、EQUIV、IMP（含意） – 命題が正しいことを真理値表を使って言うこと • 逆･裏・対偶 – ある命題の逆･裏･対偶を作ること • 必要条件、十分条件 – 条件付命題（含意）の概念をベン図で表すこと 第2章 離散集合 • 集合の表現 – 外延的記法と内包的記法で書けること • ベキ集合 – ある集合のベキ集合を正しく書けること • 包除原理 – 3集合までの包除原理を利用できること 第3章 写像･関数 • 4つの対応 – 多対多、１対多、多対１、１対１（広義、狭義） • 直積集合 – 2つの集合の直積集合を正しく書けること – 順序対 • 写像 – 部分写像、写像、全射、単射、全単射の区別 – 逆写像 • 写像の合成 – 行列表現の写像の合成写像を作れること 第4章 帰納法 • 無限集合の濃度 – ベキ集合の濃度、実数の濃度＞自然数の濃度 • カントールの対角線論法 – 有理数の濃度＝自然数の濃度 • 数学的帰納法による証明 – 簡単な問題について証明できること • 帰納的アルゴリズム – ユークリッドの互除法 – ハノイの塔 – 階乗の計算 第5章 離散関係 • 関係とは集合である • 関係の表現 – 関係グラフ、関係行列 – 関係行列の和と積の意味 • 同値関係 – – – – – 3つの性質（律） 推移的閉包の意味 ある関係が同値関係であることを示すこと ある集合を同値類に分割すること、代表元 商集合 第6章 整数演算 • 代数系 – なにか？ – 単位元（零元）、逆元 • ユークリッドの互除法 – mx+ny=GCD(m,n)となるx､yを求めること • 剰余代数系 – 計算できること（加減乗除） – 繰り返し２乗法 – 法nによる剰余系とは • 同値関係であることの証明 – 剰余系での演算 • 演算表を作成できること、逆元表も作成できること – 有限体とは 第７章 離散代数系 • 代表的な代数系 – モノイド、群 –環 –体 – それぞれの持つ性質 第８章 順序集合と束 • 順序関係 – ３つの性質（律） – 半順序と全順序の違い – さまざまな順序関係 • 約数関係、派生語関係、包含関係、分割 – ハッセ図 – 最大元、最小元、極大元、極小元 – 上界、下界、上限、下限 • 束 – 束の演算（＋と・） – ブール代数 • AND、OR、NOT • 完全系 第９章 離散グラフ • 離散グラフ – – – – – – – 節点（ノード）、辺（エッジ） 離散グラフの種類 同型グラフ、ノードの次数 径路、小道、順路、閉路の区別 連結グラフ、橋、切断点、距離、直径 完全グラフ、正則グラフ、２部グラフ、木 オイラーグラフ（一筆書き） • オイラーの定理（オイラーグラフに関する） – ハミルトングラフ（巡回セールスマン問題） – 平面グラフ • オイラーの定理（平面グラフに関する） • クラトウスキーの定理 第１０章 木グラフ • 探索木 – 横型探索と縦型探索 – OpenListとClosedListの利用法 • 重みつきグラフ – 最短径路探索問題 – ダイクストラのアルゴリズム • ２点間の最短径路を求める方法 第１５回 終了
© Copyright 2024 ExpyDoc
