GAC024 Discrete Mathematics · ⁨GAC024 Дискретная математика⁩ — GAC Mathematics · ⁨GAC Математика⁩ Revision Notes · ⁨Конспекты GAC024 Discrete Mathematics · ⁨GAC024 Дискретная математика⁩

4.1

What this module is, and how it is marked · ⁨Что представляет собой этот модуль и как он оценивается⁩

English

A repeated set member is counted once, a binary carry may exceed a fixed width, and the fewest-edge route may not have the smallest weight. Discrete mathematics makes those rules explicit.

GAC024 covers sets, counting systems, binary logic, algorithms and networks. Your centre's current brief determines assessment tasks, tools, weights and deadlines. These original practice sheets do not establish official marking rules or a university credit decision.

State the universe, representation width, allowed inputs or graph assumptions before solving. Show enough working for another reader to reproduce the result and distinguish a mathematical model from its real implementation.

Русский

Повторяющийся элемент множества считается один раз, двоичный перенос может превышать фиксированную ширину, а маршрут с наименьшим количеством ребер может иметь не самый маленький вес. Дискретная математика делает эти правила явными.

GAC024 охватывает множества, системы счета, двоичную логику, алгоритмы и сети. Текущее задание вашего учебного центра определяет задачи оценки, инструменты, веса и сроки. Эти оригинальные практические листы не устанавливают официальных правил оценивания или решения о зачете в университете.

Укажите универсум, ширину представления, допустимые входные данные или предположения о графе перед решением. Покажите достаточно работы, чтобы другой читатель мог воспроизвести результат и отличить математическую модель от её реальной реализации.

4.1

Sets, relations and functions · ⁨Множества, отношения и функции⁩

Syllabus · ⁨Программа⁩

English

Unit 1 of 5 in GAC024 Discrete Mathematics (Level III). The module is taught over about 40 class hours plus 20 hours of independent study, and is assessed at the teaching centre and moderated by ACT — there is no external exam.

Module purpose: On completion of this module, students should be able to demonstrate an understanding of the basic principles of discrete mathematics, particularly the utilisation of mathematical logic. They should also be able to demonstrate the application of these skills to practical situations.

The module outcomes this unit works towards:

Learning Objective GAC024.1: Demonstrate understanding of the introductory concepts and properties of sets, relations and functions.

Русский

Раздел 1 из 5 в GAC024 Дискретная математика (Уровень III). Модуль изучается в течение примерно 40 академических часов плюс 20 часов самостоятельной работы, оценивается на учебном центре и проходит модерацию ACT — внешнего экзамена нет.

Цель модуля: По завершении этого модуля студенты должны продемонстрировать понимание основных принципов дискретной математики, особенно использования математической логики. Они также должны уметь демонстрировать применение этих навыков в практических ситуациях.

Результаты обучения, к которым работает этот раздел:

Цель обучения GAC024.1: Демонстрировать понимание вводных понятий и свойств множеств, отношений и функций.

Source: Cambridge International syllabus · ⁨Источник: Программа Cambridge International⁩

English

A set 集合 is a collection of distinct objects. Order and repetition do not matter.
Union 并集 $A \cup B$ is everything in either; intersection 交集 $A \cap B$ is what is in both; the set complement 补集 is everything in the stated universe but outside the set.
A subset 子集 has all its elements inside another set.
A relation 关系 pairs elements of two sets. A function 函数 is a relation where each input in its stated domain has exactly one output. Different inputs may share an output; an inverse relation is a function only when outputs uniquely identify their inputs.
A Venn diagram 韦恩图 turns a set problem into a picture, and can show the disjoint regions and their counts. Check that those regions add to the supplied universe total.

The inclusion-exclusion principle 容斥原理 subtracts the twice-counted overlap once: $|A\cup B|=|A|+|B|-|A\cap B|$.

Worked example. subtract an overlap only once

Known: 30 learners, 18 study French, 15 German, and 7 both. The overlap is included in both subject totals.

$$|F\cup G|=|F|+|G|-|F\cap G|=18+15-7=26$$

$$N_{neither}=|U|-|F\cup G|=30-26=4$$

French-only is $18-7=11$ and German-only $15-7=8$. The four disjoint regions sum to 30.

Practice sheet 4.1 includes progressively harder problems and independently checked solutions.

Русский

Множество — это совокупность различных объектов. Порядок и повторения не имеют значения.
Объединение $A \cup B$ — это всё, что находится в любом из них; пересечение $A \cap B$ — это то, что находится в обоих; дополнение множества — это всё, что находится в указанном универсуме, но вне множества.
Подмножество содержит все свои элементы внутри другого множества.
Отношение связывает элементы двух множеств. Функция — это отношение, в котором каждому элементу из заданной области определения соответствует ровно один результат. Различные входные значения могут иметь общий результат; обратное отношение является функцией только тогда, когда результаты однозначно идентифицируют свои входные значения.
Диаграмма Венна превращает задачу о множествах в изображение и может показать непересекающиеся области и их количества. Убедитесь, что эти области в сумме дают общее количество элементов универсального множества.

Принцип включений-исключений вычитает пересечение, посчитанное дважды, один раз: $|A\cup B|=|A|+|B|-|A\cap B|$.

Разобранное решение. вычтите пересечение только один раз

Универсальное множество класса из 30 человек разделено на тех, кто изучает только французский (11), оба предмета (7), только немецкий (8) и ни одного (4).

Известно: 30 учеников, 18 изучают французский, 15 — немецкий, и 7 — оба. Пересечение включено в оба предметных итога.

$$|F\cup G|=|F|+|G|-|F\cap G|=18+15-7=26$$

$$N_{neither}=|U|-|F\cup G|=30-26=4$$

Только французский составляет $18-7=11$, а только немецкий — $15-7=8$. Четыре непересекающиеся области в сумме дают 30.

Практический листок 4.1 содержит задачи возрастающей сложности и решения, проверенные независимо.

Vocabulary · ⁨Словарь⁩ Train · ⁨Тренировать⁩

English	Русский
set/set/	множество
Union/ˈjuːnɪən/	объединение
intersection/ˌɪntəˈsekʃn/	пересечения
set complement/set ˈkɒmplɪmənt/	дополнение множества
subset/ˈsʌbset/	подмножество
relation/rɪˈleɪʃn/	отношение
function/ˈfʌŋkʃn/	функцией
Venn diagram/ven ˈdaɪəɡræm/	диаграмма Венна
inclusion-exclusion principle/ɪnˈkluːʒn eksˈkluːʒn ˈprɪnsɪpl/	принцип включений и исключений
number base/ˈnʌmbə beɪs/	система счисления
Decimal/ˈdesɪml/	Десятичная дробь

4.2

Counting systems · ⁨Системы счисления⁩

Syllabus · ⁨Программа⁩

English

Unit 2 of 5 in GAC024 Discrete Mathematics (Level III). The module is taught over about 40 class hours plus 20 hours of independent study, and is assessed at the teaching centre and moderated by ACT — there is no external exam.

The module outcomes this unit works towards:

Learning Objective GAC024.2: Understand the relationships between different counting systems and be able to perform simple binary arithmetic operations.

Русский

Раздел 2 из 5 в GAC024 Дискретная математика (Уровень III). Модуль изучается в течение примерно 40 академических часов плюс 20 часов самостоятельной работы, оценивается на учебном центре и проходит модерацию ACT — внешнего экзамена нет.

Результаты обучения, к которым работает этот раздел:

Цель обучения GAC024.2: Понимать взаимосвязи между различными системами счисления и уметь выполнять простые арифметические операции в двоичной системе.

Source: Cambridge International syllabus · ⁨Источник: Программа Cambridge International⁩

English

A positional number base 进制 b uses digits from zero to b minus one and place weights $b^i$. Decimal 十进制 uses ten, binary 二进制 two, hexadecimal 十六进制 sixteen.
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.

For n unsigned bits, values run from zero to $2^n-1$. Distinguish an unrestricted sum from a stored fixed-width result; a wraparound rule, if explicitly given, keeps the low n bits.

Worked example. place weights determine the decimal value

Known numeral $1101_2$. Use weights from right to left: 1, 2, 4 and 8.

$$V=\sum d_i2^i$$

$$V=1(8)+1(4)+0(2)+1(1)=13$$

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

Practice sheet 4.2 includes progressively harder problems and independently checked solutions.

Русский

Позиционная основание системы счисления b использует цифры от нуля до b минус один и весовые позиции $b^i$. Десятичная система использует десять, двоичная две, шестнадцатеричная — шестнадцать.
Значение каждой цифры определяется её разрядным значением: в двоичной системе разряды равны 1, 2, 4, 8, 16 и так далее.
Шестнадцатеричная запись — это сокращённая форма для двоичной: одна шестнадцатеричная цифра точно соответствует четырем битам, поэтому преобразование может группировать бинарный паттерн указанной ширины на блоки по четыре бита. Ведущие нули сохраняют ширину, не изменяя при этом беззнаковое значение.

Для n беззнаковых битов значения варьируются от нуля до $2^n-1$. Отличайте unrestricted sum (неограниченную сумму) от сохранённого результата фиксированной ширины; правило обхода границ, если оно явно указано, сохраняет младшие n бит.

Разобранное решение. весовые позиции определяют десятичное значение

Биты 1101 выровнены по весовым позициям 8, 4, 2 и 1.

Известный numeral (число) $1101_2$. Используйте веса справа налево: 1, 2, 4 и 8.

$$V=\sum d_i2^i$$

$$V=1(8)+1(4)+0(2)+1(1)=13$$

То же самое значение записывается как D в шестнадцатеричной системе. Ведущие нули не изменили бы это неотрицательное значение, но могут зафиксировать intended width (запланированную ширину).

Практический листок 4.2 содержит задачи возрастающей сложности и решения, проверенные независимо.

4.3

Binary applications · ⁨Применение двоичной логики⁩

Syllabus · ⁨Программа⁩

English

Unit 3 of 5 in GAC024 Discrete Mathematics (Level III). The module is taught over about 40 class hours plus 20 hours of independent study, and is assessed at the teaching centre and moderated by ACT — there is no external exam.

The module outcomes this unit works towards:

Learning Objective GAC024.2: Understand the relationships between different counting systems and be able to perform simple binary arithmetic operations.

Learning Objective GAC024.5: Use the basic identities of Boolean algebra to analyse logic circuits and understand the basic principles of propositional logic.

Русский

Раздел 3 из 5 в GAC024 Дискретная математика (Уровень III). Модуль изучается в течение примерно 40 академических часов плюс 20 часов самостоятельной работы, оценивается на учебном центре и проходит модерацию ACT — внешнего экзамена нет.

Результаты обучения, к которым работает этот раздел:

Цель обучения GAC024.2: Понимать взаимосвязи между различными системами счисления и уметь выполнять простые арифметические операции в двоичной системе.

Цель обучения GAC024.5: Использовать основные тождества булевой алгебры для анализа логических схем и понимания базовых принципов пропозиционной логики.

Source: Cambridge International syllabus · ⁨Источник: Программа Cambridge International⁩

English

Binary arithmetic 二进制运算 adds like decimal, carrying at 2 instead of at 10.
A bit 位 is one binary digit; a byte 字节 is eight.
Boolean algebra 布尔代数 works on true and false with AND, OR and NOT.
A truth table 真值表 lists every Boolean input combination and output. Matching every row proves equivalence for the same finite Boolean inputs; it does not prove physical circuit timing or real-system security.
Logic gates 逻辑门 implement stated operations, and a logic circuit 逻辑电路 connects them. Trace the abstract logic according to its connections and input conventions.

Use inclusive OR and explicit brackets. De Morgan gives $\neg(A\land B)=(\neg A)\lor(\neg B)$. Bitwise NOT inverts only the stated width, not an unspecified infinite representation.

Worked example. an OR output is inverted by NOT

Known: $Y=\neg(A\lor B)$. Inclusive OR is false only when both inputs are false; NOT reverses that result. In row order $(A,B)=(0,0),(0,1),(1,0),(1,1)$, the output column is 1, 0, 0, 0. De Morgan gives equivalent expression $(\neg A)\land(\neg B)$.

Practice sheet 4.3 includes progressively harder problems and independently checked solutions.

Русский

Двоичная арифметика складывается аналогично десятичной, с переносом при 2 вместо 10.
Бит — это одна двоичная цифра; байт состоит из восьми бит.
Булева алгебра работает с истиной и ложью с помощью операций AND, OR и NOT.
Таблица истинности перечисляет все комбинации булевых входов и выходов. Совпадение каждой строки доказывает эквивалентность для одних и тех же конечных булевых входов; это не доказывает временные характеристики физической схемы или безопасность реальных систем.
Логические вентили реализуют указанные операции, а логическая схема соединяет их. Отслеживайте абстрактную логику согласно соединениям и конвенциям входа.

Используйте инклюзивное OR и явные скобки. Закон де Моргана даёт $\neg(A\land B)=(\neg A)\lor(\neg B)$. побитовое NOT инвертирует только указанную ширину, а не неопределённое бесконечное представление.

Разобранное решение. выход OR инвертируется через NOT

Входы A и B поступают в блок с меткой OR, выход которого поступает в блок с меткой NOT, давая Y.

Известно: $Y=\neg(A\lor B)$. Инклюзивное OR ложно только тогда, когда оба входа ложны; NOT инвертирует этот результат. В порядке строк $(A,B)=(0,0),(0,1),(1,0),(1,1)$ столбец вывода равен 1, 0, 0, 0. Закон де Моргана даёт эквивалентное выражение $(\neg A)\land(\neg B)$.

Практический листок 4.3 содержит задачи возрастающей сложности и решения, проверенные независимо.

Vocabulary · ⁨Словарь⁩ Train · ⁨Тренировать⁩

English	Русский
binary/ˈbaɪnəri/	бинарная
hexadecimal/ˌheksəˈdesɪml/	шестнадцатеричный
place value/pleɪs ˈvæljuː/	разрядное значение
Binary arithmetic/ˈbaɪnəri əˈrɪθmətɪk/	Арифметика двоичных чисел
bit/bɪt/	бит
byte/baɪt/	байт
Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/	Булева алгебра
truth table/truːθ ˈteɪbl/	таблица истинности
Logic gates/ˈlɒdʒɪk ɡeɪts/	Логические вентили
logic circuit/ˈlɒdʒɪk ˈsɜːkɪt/	логическая схема

4.4

Algorithms · ⁨Алгоритмы⁩

Syllabus · ⁨Программа⁩

English

Unit 4 of 5 in GAC024 Discrete Mathematics (Level III). The module is taught over about 40 class hours plus 20 hours of independent study, and is assessed at the teaching centre and moderated by ACT — there is no external exam.

The module outcomes this unit works towards:

Learning Objective GAC024.3: Construct and analyse algorithms and flowcharts for simple mathematical and general procedures.

Русский

Раздел 4 из 5 в GAC024 Дискретная математика (Уровень III). Модуль изучается в течение примерно 40 академических часов плюс 20 часов самостоятельной работы, оценивается на учебном центре и проходит модерацию ACT — внешнего экзамена нет.

Результаты обучения, к которым работает этот раздел:

Цель обучения GAC024.3: Составлять и анализировать алгоритмы и блок-схемы для простых математических и общих процедур.

Source: Cambridge International syllabus · ⁨Источник: Программа Cambridge International⁩

English

An algorithm 算法 describes unambiguous steps for a task. A procedure solving the stated finite task must terminate and give the required result for its allowed inputs.
A flowchart 流程图 draws it: a decision is a diamond, a process a rectangle.
Pseudocode 伪代码 represents its steps without requiring a particular implementation language. State assignment, loop bounds and index conventions before tracing.
Tracing 追踪 an algorithm — a table with one column per variable and one row per step — records its actual updates. A trace checks the chosen input; a claim for all allowed inputs also needs a correctness argument.
Efficiency 效率 matters: a linear search can stop early but may inspect all n items. Binary search repeatedly discards half of an ordered search range; its logarithmic comparison count requires the sorted-data and bound conventions.

Worked example. repeat a remainder step until the second number is zero

Known: start with positive integers a equal to 10 and b equal to 6. While b is nonzero, compute r as a MOD b, then set a to b and b to r. Pairs after complete iterations are (6,4), (4,2), (2,0), giving output 2. Temporary r preserves the remainder before a and b change. Each nonzero remainder is smaller than the previous positive b, supporting termination.

Practice sheet 4.4 includes progressively harder problems and independently checked solutions.

Русский

Алгоритм описывает однозначные шаги для выполнения задачи. Процедура, решающая указанную конечную задачу, должна завершиться и дать требуемый результат для своих допустимых входов.
Блок-схема изображает его: решение обозначается ромбом, процесс — прямоугольником.
Псевдокод представляет его шаги без требования конкретного языка реализации. Укажите присваивание состояний, границы циклов и конвенции индексации перед отслеживанием.
Отслеживание алгоритма — таблица с одним столбцом на переменную и одной строкой на шаг — фиксирует фактические обновления. Отслеживание проверяет выбранный вход; утверждение для всех допустимых входов также требует доказательства корректности.
Эффективность имеет значение: линейный поиск может остановиться раньше, но может проверить все n элементов. Бинарный поиск многократно отбрасывает половину упорядоченного диапазона поиска; его логарифмическое количество сравнений требует отсортированных данных и конвенций границ.

Разобранное решение. повторяйте шаг остатка, пока второе число не станет равно нулю

Блок-схема алгоритма Евклида проверяет, равно ли b нулю, иначе вычисляет остаток и обновляет пару перед возвратом к проверке.

Известно: начните с положительных целых чисел 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 содержит задачи возрастающей сложности и решения, проверенные независимо.

Vocabulary · ⁨Словарь⁩ Train · ⁨Тренировать⁩

English	Русский
algorithm/ˈælɡərɪθəm/	алгоритм
flowchart/ˈfləʊtʃɑːt/	блок-схема
Pseudocode/ˈsuːdəʊkəʊd/	Псевдокод
Tracing/ˈtreɪsɪŋ/	отслеживание
Efficiency/ɪˈfɪʃənsi/	Эффективность

4.5

Graphs and networks · ⁨Графы и сети⁩

Syllabus · ⁨Программа⁩

English

Unit 5 of 5 in GAC024 Discrete Mathematics (Level III). The module is taught over about 40 class hours plus 20 hours of independent study, and is assessed at the teaching centre and moderated by ACT — there is no external exam.

The module outcomes this unit works towards:

Learning Objective GAC024.4: Identify the basic types, properties and applications of graphs and trees.

Русский

Раздел 5 из 5 в GAC024 Дискретная математика (Уровень III). Модуль изучается в течение примерно 40 академических часов плюс 20 часов самостоятельной работы, оценивается на учебном центре и проходит модерацию ACT — внешнего экзамена нет.

Результаты обучения, к которым работает этот раздел:

Цель обучения GAC024.4: Идентифицировать основные типы, свойства и области применения графов и деревьев.

Source: Cambridge International syllabus · ⁨Источник: Программа Cambridge International⁩

English

A graph 图 is a set of vertices 顶点 joined by edges 边. It models anything with connections: roads, friendships, dependencies.
For a simple undirected graph with no loops or repeated edges, the degree 度 counts incident edges. Every edge contributes two to the total degree sum.
A tree 树 is a connected graph with no cycles, and a finite tree with n vertices has n minus 1 edges. Some hierarchical models use trees, but actual systems can also contain cross-links or cycles.
A shortest path 最短路径 problem asks for the cheapest route between two vertices, by total weight under the stated constraints, rather than by the number of edges alone. A minimum spanning tree instead connects every vertex without cycles and minimises total included edge weight.

Worked example. compare total route weight, not the number of edges

Known edge weights are AB = 2, BC = 3, AC = 8 and CD = 1. The path A-C-D has weight 9, while A-B-C-D has weight 6. Therefore the three-edge path is shorter by weight despite having more edges. The minimum spanning tree for this small network uses AB, BC and CD with total 6; the agreement of totals here does not make the tasks identical.

Practice sheet 4.5 includes progressively harder problems and independently checked solutions.

Русский

Граф — это множество вершин, соединённых рёбрами. Он моделирует любое явление с связями: дороги, дружеские отношения, зависимости.
Для простого неориентированного графа без петель и кратных рёбер степень вершины считает инцидентные рёбра. Каждое ребро добавляет два к общей сумме степеней.
Дерево — это связный граф без циклов, и конечное дерево с n вершинами имеет n минус 1 рёбер. Некоторые иерархические модели используют деревья, но реальные системы также могут содержать перекрёстные связи или циклы.
Задача о кратчайшем пути требует найти маршрут с наименьшей суммарной стоимостью между двумя вершинами, исходя из общего веса при заданных ограничениях, а не только по количеству рёбер. Минимальное остовное дерево, напротив, соединяет все вершины без циклов и минимизирует суммарный вес включённых рёбер.

Разбор примера. Сравнивайте суммарный вес маршрута, а не количество рёбер

Неориентированная сеть соединяет A и B с весом 2, B и C с 3, A и C с 8, а C и D с 1.

Известные веса рёбер: AB = 2, BC = 3, AC = 8 и CD = 1. Путь A-C-D имеет вес 9, тогда как A-B-C-D — вес 6. Следовательно, путь из трёх рёбер короче по весу, несмотря на большее количество рёбер. Минимальное остовное дерево для этой небольшой сети использует рёбра AB, BC и CD с общим весом 6; совпадение итогов здесь не делает задачи идентичными.

Практический листок 4.5 содержит постепенно усложняющиеся задачи и проверенные решения.

Vocabulary · ⁨Словарь⁩ Train · ⁨Тренировать⁩

English	Русский
graph/ɡræf/	график
vertices/ˈvɜːtɪsiːz/	вершины
edges/ˈedʒɪz/	края
degree/dɪˈɡriː/	степени
tree/triː/	дерево
shortest path/ˈʃɔːtɪst pæθ/	кратчайший путь