Лекции по дискретной математике, Вялый М., Подольский В., Рубцов А., Шварц Д., Шень А., 2017

Лекции по дискретной математике, Вялый М., Подольский В., Рубцов А., Шварц Д., Шень А., 2017.

   Слова «дискретная математика», входящие в название этой книжки, употребляют в разных значениях. Иногда противопоставляют «дискретную» математику, говорящую о конечных или по крайней мере хорошо различимых объектах, и «непрерывную», где речь идёт о действительных числах, пределах, непрерывности, производных и т.п. Хотя это противопоставление условно и не всегда применимо (скажем, странно было бы разделять «дискретные» алгебраические кривые над конечным нолем и «непрерывные» алгебраические кривые над нолем комплексных чисел), некоторый смысл оно имеет.
Говоря о «советской школе дискретной математики», имеют в виду немного другое прежде всего пионерские работы 1950-х и 1960-х годов (О.Б. Лупанов и его школа) по анализу булевых функций, их классов, обобщений на многозначную логику и др.




Пример из алгебры: системы однородных уравнений.
Есть такая народная мудрость: если в задаче n неизвестных, то чтобы все их определить, нужно составить п уравнений, меньшего числа не хватит, останется неоднозначность. Иногда ещё говорят, что есть n «степеней свободы», каждое уравнение отбирает одну из них, и если уравнений меньше n, то какая-то свобода останется.

Как всегда, при буквальном понимании это неверно: скажем, уравнение х+у2=0 определяет сразу две переменные: х = 0 и у = 0 (иначе сумма квадратов положительна). И таких примеров много, скажем, уравнение х2-2ху+2у2-2у+1=0 тоже однозначно определяет обе переменные (и люди, недавно готовившиеся к «вступительным экзаменам», это сразу же увидят). Но принцип этот тем не менее имеет смысл и в каких-то ситуациях работает, и в этом разделе мы рассмотрим самую простую такую ситуацию.

ОГЛАВЛЕНИЕ.
Предисловие.
I. Начальные примеры.
1. Математическая индукция.
2. Подсчёты.
3. Графы.
4. Арифметика остатков.
II. Основные конструкции.
5. Множества и логика.
6. Функции.
7. Отношения и их графы.
8. Мощность множеств.
9. Упорядоченные множества.
10. Вероятность: первые шаги.
11. Комбинаторные игры.
III. Вычислимость.
12. Разрешающие деревья.
13. Булевы схемы и формулы.
14. Алгоритмическая неразрешимость.
15. Вычислимые функции, разрешимые и перечислимые множества.
16. Машины Тьюринга.

Купить .

Купить .



Хештеги: #учебник по математике :: #математика :: #Вялый :: #Подольский :: #Рубцов :: #Шварц :: #Шень