Бесплатная электронная библиотека. Скачать книги DJVU, PDF бесплатно
   Б.Н. Иванов, Дискретная математика. Алгоритмы и программы

   Вы можете  найти на этой странице (программа отметит желтым цветом)
   Вы можете посмотреть  список книг по высшей математике с сортировкой по алфавиту.
   Вы можете посмотреть  список книг по высшей физике с сортировкой по алфавиту.

   • Бесплатно скачать книгу, объем 3.74 Мб, формат .djvu (совр. изд.)

   Уважаемые дамы и господа !! Для того, чтобы без "глюков" скачать файлы электронных публикаций, нажмите на подчеркнутую ссылку с файлом ПРАВОЙ кнопкой мыши, выберите команду "Save target as ..." ("Сохранить объект как ...") и сохраните файл электронной публикации на локальный компьютер. Электронные публикации обычно представлены в форматах Adobe PDF и DJVU.

   ГЛАВА 1. Комбинаторные схемы
   1.1. Правило суммы
   1.2. Правило прямого произведения
   1.3. Размещения с повторениями
   1.4. Размещения без повторений
   1.5. Перестановки
   1.6. Сочетания
   1.7. Сочетания с повторениями
   1.8. Перестановки с повторениями, мультимножества
   1.9. Упорядоченные разбиения множества
   1.10. Неупорядоченные разбиения множества
   1.11. Полиномиальная формула
   1.12. Бином Ньютона
   1.13. Инверсии
   1.14. Обратные перестановки

   ГЛАВА 2. Представление абстрактных объектов
   2.1. Представление последовательностей
   2.1.1. Смежное представление
   2.1.2. Характеристические векторы
   2.1.3. Связанное размещение
   2.2. Представление деревьев
   2.2.1. Представление деревьев на связанной памяти
   2.2.2. Представление деревьев на смежной памяти
   2.3. Представление множеств

   ГЛАВА 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.2. Линейные рекуррентные соотношения
   3.3. Неоднородные линейные рекуррентные соотношения
   3.4. Обобщенное правило произведения
   3.5. Принцип включения и исключения
   3.6. Ладейные многочлены и многочлены попаданий
   3.6.1. Ладейные многочлены
   3.6.2. Многочлены попаданий

   ГЛАВА 4. Генерация комбинаторных объектов
   4.1. Поиск с возвращением
   4.2. Перестановки различных элементов
   4.3. Эффективное порождение перестановок
   4.4. Порождение подмножеств множества
   4.5. Генерация размещений с повторениями
   4.6. Порождение сочетаний
   4.7. Порождение композиций и разбиений
   4.8. Генерация случайных перестановок

   ГЛАВА 5. Сортировка и поиск
   5.1. Сортировка вставками
   5.2. Пузырьковая сортировка
   5.3. Сортировка перечислением
   5.4. Сортировка всплытием Флойда
   5.5. Последовательный поиск
   5.6. Логарифмический поиск
   5.7. Сортировка с вычисляемыми адресами

   ГЛАВА 6. Введение в теорию графов. Алгоритмы на графах
   6.1. Основные понятия и определения
   6.2. Представления графов
   6.2.1. Матрица смежности графа
   6.2.2. Матрица инцидентности графа
   6.2.3. Матрица весов графа
   6.2.4. Список ребер графа
   6.2.5. Структура смежности графа
   6.3. Метод поиска в глубину
   6.4. Отношение эквивалентности
   6.5. Связные компоненты
   6.6. Выделение компонент связности
   6.7. Эйлеровы графы
   6.8. Остовные деревья
   6.8.1. Жадный алгоритм построения минимального основного дерева
   6.8.2. Алгоритм ближайшего соседа построения основного дерева
   6.9. Кратчайшие пути на графе
   6.10. Потоки в сетях
   6.11. Клики, независимые множества
   6.12. Циклы, фундаментальные множества циклов
   6.13. Листы и блоки
   6.13.1. Листы
   6.13.2. Блоки
   6.13.3. Поиск блоков в глубину
   6.14. Двудольные графы
   6.14.1. Условия существования двудольных графов
   6.14.2. Паросочетания
   6.14.3. Алгоритм определения максимального паросочетания
   6.14.4. Системы различных представителей
   6.14.5. Связь системы различных представителей и двудольных графов
   6.14.6. Задача о назначениях
   6.15. Хроматические графы
   6.16. Диаметр, радиус и центры графа

   ГЛАВА 7. Введение в теорию групп. Приложения
   7.1. Определение группы
   7.2. Гомоморфизм групп
   7.3. Смежные классы
   7.4. Строение коммутативных (абелевых) групп
   7.5. Строение некоммутативных групп
   7.6. Симметрическая группа подстановок
   7.7. Действие групп на множестве
   7.8. Цикловой индекс группы
   7.9. Теория перечисления Пойа
   7.10. Цикловая структура групп подстановок
   7.10.1. Цикловой индекс группы, действующей на себе
   7.10.2. Цикловой индекс циклической группы
   7.10.3. Цикловой индекс симметрической группы

   ГЛАВА 8. Элементы теории чисел
   8.1. Наибольший общий делитель
   8.2. Наименьшее общее кратное
   8.3. Простые числа
   8.4. Сравнения, свойства сравнений
   8.5. Полная система вычетов
   8.6. Приведенная система вычетов
   8.7. Функция Эйлера
   8.8. Функция Мёбиуса. Формула обращения Мёбиуса

Краткая аннотация книги

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

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

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

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

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

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

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