GAC024 離散数学

重複する集合要素は一度しかカウントされず、バイナリ carry は固定幅を超えることがあり、最少エッジの経路が最小重みとは限らない。離散数学はこれらのルールを明確にする。

GAC024 は集合、計数体系、バイナリ論理、アルゴリズム、ネットワークを扱う。貴校の現在の評価要件に基づき評価課題、ツール、ウェイト、期限が決定される。これらのオリジナル練習シートは公式の採点規則や大学での単位認定を確立するものではない。

解決する前に、全集、表現幅、許容入出力、またはグラフの仮定を明記せよ。別の読者が結果を再現できる enough の計算過程を示し、数学的モデルと実際の実装を区別せよ。

• 集合 は固有の物体の集まりである。順序や重複は考慮されない。
• 和集合 $A \cup B$ はどちらかに含まれるすべての要素; 积集合 $A \cap B$ は 両方に含まれる要素; 集合の補集合 は指定された全集に含まれるが集合の外側のすべての要素である。
• 部分集合は、ある集合の要素をすべて含みます。
• 関係は2つの集合の要素をペアにします。関数とは、各 定義域内の入力がちょうど1つの出力を持つ関係です。異なる入力が同じ出力を持つこともあり、逆関係が関数となるのは、出力が入力を一意に特定できる場合に限ります。
• ベン図は集合の問題を図示し、離散的な領域とそれぞれの個数を示すことができます。それらの領域の合計が与えられた全集合の総数と一致することを確認してください。

重複除外の原理とは、二重にカウントされた重なりを一度だけ引くことである：$|A\cup B|=|A|+|B|-|A\cap B|$。

** worked example.** 重複分は一度だけ差し引く

既知：生徒30名、フランス語18名、ドイツ語15名、両方7名。重なり部分は両科目の合計に含まれています。

フランス語のみは$18-7=11$、ドイツ語のみは$15-7=8$です。4つの離散領域の合計は30になります。

練習シート 4.1 は、段階的に難易度が上がる問題と、個別に検証済みの解答を含んでいます。

• 位置の進数系 b は、0 から b-1 までの数字と位权重 $b^i$ を使用します。十進法 は10を用い、二進法 2、十六進数の16。
• Every digit's value is its place value: in binary the places are 1, 2, 4, 8, 16 and so on.
• Hexadecimal is shorthand for binary: one hex digit is exactly four bits, so conversion can group a stated-width binary pattern into four-bit blocks. Leading zeros preserve width while leaving the unsigned value unchanged.

nビットの符号なし整数の場合、値は0から$2^n-1$までとなります。無制限の和と保存された固定幅の結果を区別してください。明示されたリターンルールがあれば、下位nビットを保持します。

Worked example. place weights determine the decimal value

既知の数値$1101_2$。右から左へ位权重を用います：1, 2, 4, 8。

The same value is D in hexadecimal. Leading zeros would not change this nonnegative value but can record an intended width.

練習シート 4.2 は、段階的に難易度が上がる問題と、個別に検証済みの解答を含んでいます。

• Binary arithmetic adds like decimal, carrying at 2 instead of at 10.
• ビットとは1つのバイナリ桁を指し、バイトとは8つです。
• 論理代数は真偽値に対してAND、OR、NOTで操作を行います。
• 真理表はすべての論理入力組み合わせとその出力をリストアップします。同じ有限の論理入力に対して各行が一致すれば等価性を証明できますが、物理的な回路タイミングや実際のシステムのセキュリティを証明するものではありません。
• 論理ゲートは指定された演算を実装し、論理回路はそれらを接続します。接続と入力規格に従って抽象的な論理をトレースしてください。

包括的ORと明記された括弧を使用してください。ド・モルガンの法則により$\neg(A\land B)=(\neg A)\lor(\neg B)$となります。ビット単位のNOTは指定された幅のみを反転させ、未指定の無限表現ではありません。

** worked example（解題例）。**ORの出力がNOTによって反転される

既知：$Y=\neg(A\lor B)$。包括的ORは両方の入力が false のときのみ false となり、NOTは結果を反転します。行番号順で$(A,B)=(0,0),(0,1),(1,0),(1,1)$、出力列は1, 0, 0, 0となります。ド・モルガンの法則による同等の式は$(\neg A)\land(\neg B)$です。

練習シート 4.3 は、段階的に難易度が上がる問題と、個別に検証済みの解答を含んでいます。

• アルゴリズムはタスクに対する曖昧さのない手順を記述します。指定された有限のタスクを解決する手続は、許容される入力に対して終了し、必要な結果を返さなければなりません。
• フローチャートで描画します：判断は菱形、処理は長方形です。
• 擬似コードは特定の実装言語を必要とせず手順を表します。トレース前に代入、ループの境界、インデックスの規格を明記してください。
• アルゴリズムのトレース — 変数ごとに1列、ステップごとに1行のテーブル — は実際の更新を記録します。トレースは選択された入力を検証しますが、すべての許容入力に対する主張には、正しさに関する議論も必要です。
• 効率性が重要です：線形探索は早期に停止可能ですが、全n項目を検査する場合があります。二項探索は整列された探索範囲の半分を繰り返し破棄し、対数的比較回数は整列データと境界規格を要します。

** worked example（解題例）。**2番目の数が0になるまで余りのステップを繰り返す

既知：正の整数 a=10, b=6 で始めます。bが非ゼロの間、r = a MOD b を計算し、a に b、b に r を設定します。完全な反復後のペアは (6,4), (4,2), (2,0) となり、出力は2です。一時的なrはaとbが変わる前の余りを保持します。各非ゼロ余りは直前の正のbより小さいため、終了が保証されます。

練習シート 4.4 は、段階的に難易度が上がる問題と、個別に検証済みの解答を含んでいます。

• グラフは頂点の集合で辺によって結合されています。以下の things と 接続モデル化します：道路、交友関係、依存関係。
• ループや重複エッジのない単純無向グラフにおいて、次数は接する辺の数を数えます。各辺は合計次数に2寄与します。
• 木はサイクルを持たない連結グラフであり、n頂点の有限木はn-1本の辺を持ちます。階層構造モデルには木が使われますが、実際のシステムにはクロスリンクやサイクルが含まれることもあります。
• 最短経路問題は、単に辺の数を最小化するのではなく、指定された制約条件下で2つの頂点間の総重みが最も低い経路を求める問題である。一方、最小 spanning tree はサイクルを形成せずすべての頂点を接続し、総重みを最小化する.

** worked example.** 辺の数ではなく、総経路の重みを比較する

既知の辺の重みは AB = 2, BC = 3, AC = 8, CD = 1 です。経路 A-C-D の重みは9ですが、A-B-C-D の重みは6です。したがって、辺の数は多いものの、3辺の経路の方が重みでは短くなります。この小さなネットワークの最小 spanning tree は AB, BC, CD を使用し、合計は6となりますが、この一致が両タスクが同一であることを意味するわけではありません。

練習シート 4.5 には段階的に難易度が上がる問題と、個別に検証された解答が含まれています。