Обложка Краснов М.Л., Киселев А.И., Макаренко Г.И., Шикин Е.В., Заляпин В.И., Эвнин А.Ю. Вся высшая математика. Том 7: Дискретная математика (теория чисел, общая алгебра, комбинаторика, теория Пойа, теория графов, паросочетания, матроиды)
Id: 263191
687 руб.

Вся высшая математика.
Том 7: Дискретная математика (теория чисел, общая алгебра, комбинаторика, теория Пойа, теория графов, паросочетания, матроиды) Т.7. Изд. стереотип.

URSS. 2021. 208 с. ISBN 978-5-9710-7794-7. Увеличенный формат (170мм x 240мм).
Газетная бумага

Аннотация

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


Оглавление
Предисловие
LXVIЭлементы теории чисел
 § 1.Теорема о делении с остатком
 § 2.Наибольший общий делитель. Алгоритм Евклида
 § 3.(ka -- 1, kb -- 1) = k(a,b) -- 1
 § 4.Простые числа. Основная теорема арифметики
 § 5.Сравнения и их свойства
 § 6.Системы вычетов
 § 7.Теорема Эйлера
 § 8.Линейные диофантовы уравнения
 § 9.Мультипликативные функции
 § 10.Система РША
 Упражнения
 Ответы
LXVIIНачальные понятия общей алгебры
 § 1.Отношения
 § 2.Отношение эквивалентности
 § 3.Отношения порядка
 § 4.Алгебраические структуры. Группа
 § 5.Кольцо и поле
 § 6.Группы самосовмещений многоугольников и многогранников
 Упражнения
 Ответы
LXVIIIКомбинаторика
 § 1.Правило произведения
  1.1.Число перестановок
  1.2.Число подмножеств конечного множества
 § 2.Выборки. Размещения
 § 3.Сочетания
 § 4.Перестановки с повторениями
 § 5.Полиномиальная формула
 § 6.Комбинаторные тождества
 § 7.Формула включения-исключения
 § 8.Функция Эйлера
 § 9.Задача о беспорядках и встречах
 § 10.Число сюръекций
 § 11.Обобщение формулы включения-исключения
 § 12.Числа Стирлинга II рода
 § 13.Числа Стирлинга I рода
 § 14.Производящие функции
 § 15.Число счастливых билетов
 § 16.Число бинарных деревьев с n вершинами
 § 17.Решение линейных рекуррентных уравнений
 Упражнения
 Ответы
LXIXТеория Пойа
 § 1.Цикловой индекс группы подстановок
 § 2.Лемма Бернсайда
 § 3.Функции и классы эквивалентности
 § 4.Теорема Пойа
 § 5.Примеры
 Упражнения
 Ответы
LXXВведение в теорию графов
 § 1.Определения и примеры
 § 2.Связные графы
 § 3.Метрические характеристики графа
 § 4.Гамильтоновы графы
 § 5.Эйлеровы графы
 § 6.Деревья и леса
 § 7.Теорема Кэли о числе помеченных деревьев
 § 8.Стягивающие деревья
 § 9.Фундаментальная система циклов
  9.1.Симметрическая разность множеств
  9.2.Псевдоциклы
  9.3.Фундаментальная система циклов
 § 10.Укладки графов
 § 11.Формула Эйлера
 § 12.Критерий планарности графа
 § 13.Ориентированные графы
 § 14.Нахождение кратчайших путей в орграфе
 § 15.Задача сетевого планирования и управления (PERT)
 § 16.Потоки в сетях
 Упражнения
 Ответы
LXXIПаросочетания
 § 1.Теорема Холла
 § 2.Венгерская теорема
 § 3.Теорема Дилворта
 § 4.Совершенные паросочетания в регулярных двудольных графах
 § 5.Дважды стохастические матрицы
 § 6.Латинские прямоугольники
 § 7.Реберная раскраска графов
 § 8.Теорема Бёржа
 § 9.Нахождение наибольшего паросочетания
 § 10.Нахождение наименьшего вершинного покрытия
 § 11.Венгерский алгоритм
 § 12.Задача о назначениях на узкое место
 Упражнения
 Ответы
LXXIIМатроиды
 § 1.Определения и примеры
 § 2.Двойственность
 § 3.Представимые матроиды
 § 4.Ранговая функция
 § 5.Жадный алгоритм
 § 6.Одна задача планирования эксперимента
 § 7.Трансверсали
 § 8.Трансверсальный матроид
 § 9.Независимые трансверсали
 § 10.Общие трансверсали
 § 11.Некоторые интересные матроиды
  11.1.Матроид Фано
  11.2.Матроид Вамоса
 Упражнения
 Ответы
Предметный указатель

Предисловие

В предыдущих книгах нашего издания развитие основных событий в большей или меньшей степени было связано с ключевой идеей близости, математическое осмысление которой привело к ошеломляющему каскаду самых разнообразных результатов. И хотя эта идея еще весьма далека от исчерпания, существует широкий пласт математических задач, в которых она не работает. Значительную по объему долю в этом пласте составляют задачи, в которых изучаются свойства множеств, состоящих из конечного числа элементов. Число элементов в таких множествах может быть разным -- от нескольких единиц до многих степеней десяти -- 1010, 101010, ... .

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

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

Дискретность (от латинского discretus -- разделенный, прерывистый) нередко противопоставляют непрерывности. Однако при решении сложных практических задач дискретные и непрерывные подходы работают совместно и весьма эффективно, взаимно обогащая друг друга.

В 1998 году издательство "Мир" выпустило книгу Р.Грэхема, Д.Кнута и О.Паташника "Конкретная математика" (Concrete mathematics), термин

CONCRETE

в названии которой образован слиянием слов

CONtinious и disCRETE.

Основная задача этого тома -- дать читателю рабочее представление о технике оперирования с дискретными объектами, аналогичной технике для объектов непрерывных.

Наша цель скромней: мы лишь хотим познакомить читателя с некоторыми элементами дискретной математики.

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


Об авторах
Краснов Михаил Леонтьевич
Кандидат физико-математических наук, профессор кафедры высшей математики Московского энергетического института (МЭИ). Был членом Редакционного совета МЭИ, работал в Совете по математическому образованию при Министерстве высшего образования СССР.

В область научных интересов М. Л. Краснова входили дифференциальные уравнения. Им были написаны научные статьи, посвященные уравнениям в частных производных и некоторым прикладным задачам. Вместе с А. И. Киселевым и Г. И. Макаренко он придумал и осуществил простую и в то же время гениальную идею — учить будущих инженеров сложным разделам высшей математики на рассмотрении подробных решений тщательно подобранных типовых примеров при минимальном изложении теории. В результате более чем тридцатилетней совместной работы ими были написаны ставшие классическими учебные пособия ("Векторный анализ", "Вариационное исчисление" и другие). Все эти книги многократно выходили в издательстве URSS, а также были переведены и изданы на испанском, португальском, английском, французском, японском, польском и других языках.

Киселев Александр Иванович
Born on August 26th 1917 in Russia. Graduated from Moscow State University (Department of Mechanics and Mathematics) in 1951. 1951-1962: Affiliated to the Institute of Physical Problems of USSR Academy of Sciences. 1962-1996: Associate Professor of Moscow Power Institute. Department of Mathematics. Fields of interest: Theory of Functions.
Макаренко Григорий Иванович
Окончил механико-математический факультет Московского государственного университета имени М. В. Ломоносова в 1951 г. В 1951–1960 гг. работал на кафедре высшей математики Московского энергетического института. В 1960–1978 гг. — старший научный сотрудник Объединенного института ядерных исследований в Дубне. В 1978–1989 гг. — профессор кафедры математики Московского государственного института путей сообщения. Область научных интересов: дифференциальные уравнения.
Шикин Евгений Викторович
Доктор физико-математических наук, профессор Московского государственного университета имени М. В. Ломоносова. Научные интересы: изометрические погружения двумерных римановых многообразий неположительной кривизны в трехмерное евклидово пространство, геометрические свойства решений уравнения Монжа—Ампера гиперболического типа, геометрические и графические подходы к разрешению задач динамического поиска объектов, исследование проблем управления на разных стадиях кризиса.
Заляпин Владимир Ильич
Окончил механико-математический факультет Московского государственного университета имени М. В. Ломоносова в 1969 г., аспирантуру Отделения математики МГУ — в 1972 г. Кандидат физико-математических наук, доцент, профессор кафедры математического анализа Южно-Уральского государственного университета.

Автор 86 научных и более 40 учебных и методических публикаций. Заместитель председателя Челябинского регионального отделения научно-методического Совета по математике Минобрнауки РФ, председатель Совета по математике ЮУрГУ. Награжден нагрудным знаком "Почетный работник высшей школы РФ".

Эвнин Александр Юрьевич
Кандидат педагогических наук, доцент кафедры прикладной математики Южно-Уральского государственного университета. Автор более 80 научных публикаций, в том числе одного учебника, 16 учебных пособий, а также статей в журналах «Квант», «Математическое образование», «Математика в высшем образовании», «Математика в школе».