URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Деза Е.И., Модель Д.Л. Основы дискретной математики
Id: 188474
 
239 руб.

Основы дискретной математики. Изд.2, испр. и доп.

URSS. 2011. 224 с. Мягкая обложка. ISBN 978-5-397-01588-2. Уценка. Состояние: 5-. Блок текста: 5. Обложка: 4+.

 Аннотация

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

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

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


 Содержание

Введение
Глава 1. Графы и их применения
 1.1.Основные понятия
 1.2.Степени вершин графа
 1.3.Операции над графами
  1.3.1.Взятие подграфа
  1.3.2.Взятие дополнения
  1.3.3.Уничтожение ребра
  1.3.4.Уничтожение вершины
 1.4.Полный граф и пустой граф
 1.5.Путь, цикл
 1.6.Связный граф
 1.7.Деревья
 1.8.Регулярные графы
 1.9.Двудольные графы
 1.10.Графы и матрицы
  1.10.1.Матрица смежности
  1.10.2.Матрица принадлежности
  1.10.3.Матрица расстояний
  1.10.4.Матрица достижимости
 1.11.Плоские графы
  1.11.1.Основные понятия
  1.11.2.Вершины, ребра и грани плоского графа. Формула Эйлера
  1.11.3.Графы K5 и K3,3
  1.11.4. Теорема Понтрягина--Куратовского
  1.11.5.Раскраска плоских графов
 1.12.Эйлеровы графы
 1.13.Гамильтоновы графы
Глава 2. Комбинаторика и рекуррентные соотношения
 2.1.Основные комбинаторные соединения
 2.2.Рекуррентные соотношения
 2.3.Решение рекуррентных соотношений
 2.4.Деление многочленов и рекуррентные соотношения
 2.5.Производящие функции
 2.6.Рекуррентные соотношения и конечные суммы
  2.6.1.Сумма первых n натуральных чисел
  2.6.2.Сумма n первых членов арифметической прогрессии
  2.6.3.Сумма n первых членов геометрической прогрессии
  2.6.4. Сумма первых n квадратов натуральных чисел
  2.6.5.Сумма первых n кубов натуральных чисел
  2.6.6. Сумма первых n чисел Фибоначчи
 2.7.Некоторые методы суммирования
  2.7.1. Простейший способ суммирования
  2.7.2.Преобразование Абеля (суммирование по частям)
 2.8.Асимптотические методы суммирования
  2.8.1.Суммирование и производящие функции
  2.8.2.Асимптотические формулы
Глава 3. Задачи
 3.1.Элементы теории графов
  3.1.1.Определение графа. Граф как бинарное отношение
  3.1.2.Степени вершин графа
  3.1.3.Операции над графами
  3.1.4.Изоморфные графы
  3.1.5.Классические графы. Путь, цикл, связный граф
  3.1.6.Деревья
  3.1.7.Регулярные графы
  3.1.8.Двудольные графы
  3.1.9.Графы и матрицы
  3.1.10.Плоские графы
  3.1.11.Эйлеровы и Гамильтоновы графы
 3.2.Комбинаторика
  3.2.1.Комбинаторные соединения. Правило сложения и умножения
  3.2.2.Размещения с ограничениями
  3.2.3.Разбиение на группы
  3.2.4.Решение неопределенных уравнений
  3.2.5.Метод включений и исключений
  3.2.6.Бином Ньютона и полиномиальная теорема
  3.2.7.Основные комбинаторные тождества
 3.3.Рекуррентные соотношения
  3.3.1. Числа Фибоначчи
  3.3.2. Треугольник Паскаля
  3.3.3.Решение рекуррентных соотношений
  3.3.4.Конечные суммы
 3.4.Контрольные работы
  3.4.1.Контрольная работа по теме "Графы"
  3.4.2.Лабораторная работа по комбинаторике
  3.4.3.Контрольная работа по теме "Комбинаторика"
  3.4.4.Контрольная работа по теме "Рекуррентные соотношения"
Литература

 Введение

Дискретная математика -- часть математической науки, которая зародилась в глубокой древности. Как говорит само название, главной ее спецификой является дискретность, то есть антипод непрерывности.

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

В узком смысле дискретная математика ограничивается только этими новыми разделами. К ним относятся теория графов и сетей, комбинаторный анализ, теория кодирования, теория функциональных систем, целочисленное программирование и т.д.

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

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

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

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

Таким образом, к ведению дискретной математики могут быть отнесены такие разделы, как:

  • наивная теория множеств;
  • математическая логика;
  • математическая кибернетика;
  • теория функциональных систем;
  • общая алгебра;
  • комбинаторика;
  • теория графов;
  • машинная арифметика;
  • теория алгоритмов;
  • теория игр;
  • теория кодирования;
  • теория конечных автоматов;
  • теория формальных грамматик;
  • вычислительная геометрия;
  • теория булевых функций;
  • логическое программирование;
  • функциональное программирование;
  • Булева алгебра;
  • комбинаторная логика;
  • математическая лингвистика;
  • теория искусственного интеллекта.

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


 Об авторах

Елена Ивановна ДЕЗА

Кандидат физико-математических наук. В 1983 г. окончила математический факультет Московского государственного педагогического института, в 1992 г. -- аспирантуру по кафедре теории чисел МГПИ. С 1988 г. преподает на математическом факультете МГПИ (ныне -- МПГУ). Автор нескольких книг по теории чисел, дискретной математике и теории метрических пространств.

Дмитрий Лазаревич МОДЕЛЬ (род. в 1980 г.)

В 2003 г. с отличием окончил математический факультет МПГУ. В настоящее время -- старший преподаватель кафедры теории чисел; является соискателем ученой степени кандидата наук на кафедре теории и методики преподавания математики. Область научных интересов: дискретная математика, методы принятия решений, профильное образование школьников, развитие образовательных систем. Автор более 20 научно-методических публикаций.

 
© URSS 2016.

Информация о Продавце