по мотивам: Р. Грэхем/Д. Кнут/О. Паташник (Concrete Mathematics), К. Розенafter: R. Graham/D. Knuth/O. Patashnik (Concrete Mathematics), K. Rosen

Дискретная математикаDiscrete mathematics

Математика, изучающая дискретные (счётные, а не непрерывные) структуры — то, на чём в конечном счёте строятся комбинаторные алгоритмы (02.1.3), графовые алгоритмы (03) и большая часть криптографии (06). В отличие от математического анализа (00.1), здесь нет пределов и производных — только счётные множества, отношения, логические высказывания и целые числа. Каркас: 5 подразделов, страницы ещё не написаны.The mathematics of discrete (countable, not continuous) structures — what combinatorial algorithms (02.1.3), graph algorithms (03), and much of cryptography (06) are ultimately built on. Unlike mathematical analysis (00.1), there are no limits or derivatives here — just countable sets, relations, logical propositions, and integers. Skeleton: 5 subsections, pages not yet written.

00.3.1 Множества, отношения, логика00.3.1 Sets, relations, logic

Теория множествSet theoryОперации над множествами, мощность, диаграммы Венна, отношение включения, парадоксы наивной теории множеств.Set operations, cardinality, Venn diagrams, the subset relation, paradoxes of naive set theory. Отношения и функцииRelations & functionsБинарные отношения, отношения эквивалентности и порядка, замыкания отношений, функции как частный случай отношения.Binary relations, equivalence and order relations, relation closures, functions as a special case of a relation. Математическая логикаMathematical logicПропозициональная логика, логика предикатов, таблицы истинности, нормальные формы (КНФ/ДНФ), основы булевой алгебры.Propositional logic, predicate logic, truth tables, normal forms (CNF/DNF), boolean algebra fundamentals. Методы доказательствProof methodsМатематическая индукция (обычная и сильная), доказательство от противного, доказательство контрапозицией, инварианты.Mathematical induction (ordinary and strong), proof by contradiction, proof by contraposition, invariants.

00.3.2 Комбинаторика00.3.2 Combinatorics

фундамент под 02.1.3the foundation under 02.1.3

Правила суммы и произведенияSum & product rulesБазовые правила подсчёта, принцип Дирихле (pigeonhole), принцип включений-исключений.Basic counting rules, the pigeonhole principle, the inclusion-exclusion principle. Перестановки и сочетанияPermutations & combinationsРазмещения, перестановки (с повторениями и без), сочетания, биномиальные коэффициенты и треугольник Паскаля.Arrangements, permutations (with and without repetition), combinations, binomial coefficients, Pascal's triangle. Разбиения и рекуррентные числаPartitions & recurrence-defined numbersРазбиения множества и числа, числа Каталана, числа Стирлинга, числа Белла — комбинаторные последовательности, задаваемые рекуррентно.Partitions of a set and of a number, Catalan numbers, Stirling numbers, Bell numbers — combinatorial sequences defined recurrently. Производящие функцииGenerating functionsОбычные и экспоненциальные производящие функции как инструмент решения рекуррентных соотношений и подсчёта комбинаторных объектов.Ordinary and exponential generating functions as a tool for solving recurrences and counting combinatorial objects.

00.3.3 Теория чисел00.3.3 Number theory

фундамент под 06 (крипто)the foundation under 06 (crypto)

Делимость и НОД/НОКDivisibility & GCD/LCMАлгоритм Евклида и его расширенная версия, основная теорема арифметики, простые числа и решето Эратосфена.The Euclidean algorithm and its extended version, the fundamental theorem of arithmetic, prime numbers and the sieve of Eratosthenes. Модулярная арифметикаModular arithmeticСравнения по модулю, китайская теорема об остатках, малая теорема Ферма, функция Эйлера — фундамент, на котором строится RSA.Congruences modulo n, the Chinese remainder theorem, Fermat's little theorem, Euler's totient function — the foundation RSA is built on. Диофантовы уравненияDiophantine equationsЛинейные диофантовы уравнения, их связь с расширенным алгоритмом Евклида, критерии разрешимости.Linear Diophantine equations, their connection to the extended Euclidean algorithm, solvability criteria.

00.3.4 Теория графов (математический взгляд)00.3.4 Graph theory (the mathematical view)

теоремы, не алгоритмы — практика в 03theorems, not algorithms — practice lives in 03

Основные определения и теоремыBasic definitions & theoremsФормальное определение графа, степени вершин, лемма о рукопожатиях, изоморфизм графов.The formal definition of a graph, vertex degrees, the handshaking lemma, graph isomorphism. Деревья и планарностьTrees & planarityСвойства деревьев, формула Эйлера для планарных графов, теорема Понтрягина-Куратовского, раскраска графов и теорема о четырёх красках.Tree properties, Euler's formula for planar graphs, the Pontryagin-Kuratowski theorem, graph coloring and the four-color theorem.

00.3.5 Абстрактная алгебра для дискретной математики00.3.5 Abstract algebra for discrete math

пересечение с 02.4 (Степанов), другой уголoverlaps with 02.4 (Stepanov), a different angle

Группы, кольца, поля — формальный взглядGroups, rings, fields — the formal viewАксиоматика алгебраических структур с точки зрения математики (в отличие от 02.5.1, где тот же материал даётся с прицелом на выражение в коде); конечные поля как основа помехоустойчивого кодирования и криптографии на эллиптических кривых.The axiomatics of algebraic structures from math's own point of view (unlike 02.5.1, where the same material is aimed at expressing it in code); finite fields as the basis of error-correcting codes and elliptic-curve cryptography.

статусstatus

Это каркас: 5 подразделов и 14 пунктов зафиксированы, страницы ещё не написаны.This is a skeleton: 5 subsections and 14 items are locked in, pages not yet written.