Close
(0) шт.
У вас немає елементів у кошику для покупок.
Категорії
    Filters
    Налаштування
    Пошук

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

    450 грн
    Лекции по дискретной математике / Автор: Вялый М. и др., Издательство: Высшая школа экономики, Серия: , Страниц: 496, Переплет: Твердый, ISBN: 978-5-7598-1782-6
    ISBN: 978-5-7598-1782-6
    Наявність : Немає в наявності
    Доставка: 1-2 дня

    Аннотация к книге "Лекции по дискретной математике"

    Учебник написан по материалам курса "Дискретная математика", который читается студентам младших курсов факультета компьютерных наук НИУ ВШЭ. Темы этого курса являются частью базовой математической культуры и необходимы будущим математикам, программистам и специалистам в области анализа данных, но не входят в традиционно сложившиеся курсы начального математического цикла (математический анализ, алгебра, линейная алгебра). В книге излагаются начальные сведения из перечислительной комбинаторики, теории графов, теории чисел, теории множеств, теории вероятностей, теории игр, теории вычислимости. Не претендуя на полноценный охват какой-либо из упомянутых теорий, учебник дает введение в эти области, с одной стороны, достаточное для студентов соответствующих специальностей, а с другой –– позволяющее читать специализированную литературу.
    Книга будет полезной студентам младших курсов, изучающим курс дискретной математики; преподавателям этой дисциплины; а также более широкому кругу любителей математики.

    Cодержание

    Предисловие
    Часть I. Начальные примеры
    Лекция 1. Математическая индукция
    1.1. Задача о раскраске плоскости
    1.2. Общая схема доказательств по индукции
    1.3. Варианты рассуждений по индукции
    1.3.1. С чего начинать?
    1.3.2. Сведение к меньшим
    1.3.3. Переформулировка: принцип наименьшего
    числа
    1.4. Как не надо
    1.5. Как догадаться, что доказывать?
    1.6. Доказательства по индукции и без индукции
    1.7. Индукция и рекурсия
    1.8. Доказательства неравенств по индукции
    1.8.1. Неравенство Бернулли
    1.8.2. Среднее арифметическое и среднее
    геометрическое
    1.9. Пример из алгебры: системы однородных
    уравнений
    1.10. Коды Грея
    1.11. Теорема Холла о представителях
    1.12. Задачи для самостоятельного решения
    Лекция 2. Подсчёты
    2.1. Правило суммы
    2.2. Рекуррентное соотношение: пример
    2.3. Рекуррентное соотношение: число путей
    2.4. Слова и правило произведения
    2.5. Выбор с ограничениями
    2.6. Подсчёты с кратностью
    2.7. Подмножества и числа сочетаний
    2.8. Ещё о числах сочетаний
    2.8.1. Симметрия
    2.8.2. Сумма чисел в строке
    2.8.3. Знакочередующаяся сумма
    2.8.4. Снова о включениях и исключениях
    2.8.5. Пути, подмножества, слова
    2.8.6. Соседние числа в строке
    2.8.7. Монеты и перегородки
    2.9. Бином Ньютона и производящие функции
    2.10. Числа Каталана
    2.10.1. Правильные последовательности скобок
    2.10.2. Рекуррентная формула
    2.10.3. Вычисление с помощью отражений
    2.10.4. Вычисление с производящей функцией
    2.10.5. Вычисление с теорией вероятностей и
    поворотами
    2.10.6. Доказательство по индукции с дробными
    параметрами
    2.10.7. Неассоциативные произведения,
    триангуляции и стековый каль­кулятор
    2.11. Что дальше?
    Лекция 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.2.1. Определение
    3.2.2. Соседи. Степени вершин
    3.2.3. Связные компоненты
    3.2.4. Расстояния. Простые пути
    3.2.5. Деревья
    3.2.6. Полное бинарное дерево
    3.3. Ориентированные графы
    3.3.1. Определение
    3.3.2. Степени вершин
    3.3.3. Пути и достижимость
    3.3.4. Достижимость и разрезы
    3.3.5. Компоненты сильной связности и
    ациклические графы
    3.3.6. Графы преобразований
    3.4. Эйлеровы циклы
    3.4.1. Определение
    3.4.2. Критерий существования
    3.4.3. Последовательности де Брёйна
    3.4.4. Гамильтоновы циклы
    3.5. Двудольные графы
    3.5.1. Определение
    3.5.2. Двудольные графы и раскраска в два цвета
    3.5.3. Степени вершин
    3.5.4. Паросочетания
    3.6. Клики и независимые множества
    Лекция 4. Арифметика остатков
    4.1. Чётные и нечётные числа
    4.2. Деление на 3 и остатки
    4.3. Деление с остатком
    4.4. Сравнения по модулю
    4.5. Таблицы сложения и умножения по модулю N
    4.6. Обратимые остатки по модулю N
    4.7. Обратимые элементы и диофантовы уравнения
    4.8. Алгоритм Евклида
    4.9. Алгоритм Евклида и диофантовы уравнения
    4.10. Однозначность разложения на множители
    4.11. Китайская теорема об остатках
    4.12. Малая теорема Ферма
    4.13. Функция Эйлера и теорема Эйлера
    4.14. Что дальше?
    Часть II. Основные конструкции
    Лекция 5. Множества и логика
    5.1. Основные свойства множеств и операции с
    множествами
    5.2. Теоретико-множественные тождества
    5.3. Логические переменные, логические связки
    5.4. Наблюдения
    5.5. Какие связки необходимы?
    5.5.1. Полнота дизъюнкции, конъюнкции и
    отрицания
    5.5.2. Полнота конъюнкции и отрицания
    5.5.3. Алгебраическое доказательство полноты
    5.6. Формула включений-исключений
    5.6.1. Первое доказательство
    5.6.2. Второе доказательство
    5.6.3. Формула для симметрической разности
    Лекция 6. Функции
    6.1. Пример
    6.2. Функции и связанные с ними понятия
    6.2.1. Терминология и обозначения
    6.2.2. Образ множества, полный прообраз
    6.3. Декартово произведение множеств и графики
    функций
    6.4. Инъекции, сюръекции и биекции
    6.4.1. Определения
    6.4.2. Биекции и сравнение множеств
    6.5. Композиции функций
    6.5.1. Определение
    6.5.2. Ассоциативность
    6.5.3. Обратная функция
    6.5.4. Степени композиций
    6.6. Подсчёты
    6.7. Задачи для самостоятельного решения
    Лекция 7. Отношения и их графы
    7.1. Отношения в естественном языке
    7.2. Отношения с точки зрения математики
    7.3. Свойства бинарных отношений
    7.4. Графы, матрицы и бинарные отношения
    7.5. Отношения эквивалентности
    7.6. Композиция отношений
    7.7. Отношения: что дальше?
    7.8. Задачи для самостоятельного решения
    Лекция 8. Мощность множеств
    8.1. Равномощные множества
    8.1.1. Определение равномощности
    8.1.2. Свойства равномощности
    8.1.3. Примеры равномощных множеств
    8.2. Счётные множества
    8.2.1. Определение и простейшие примеры
    8.2.2. Свойства счётных множеств
    8.3. Несчётные множества
    8.3.1. Интервал и отрезок равномощны
    8.3.2. Добавление счётного множества
    8.3.3. Числа и последовательности
    8.3.4. Отрезок и квадрат
    8.4. Диагональный аргумент Кантора и сравнение
    мощностей
    8.4.1. Несчётность отрезка
    8.4.2. Сравнение мощностей
    8.5. Что дальше?
    Лекция 9. Упорядоченные множества
    9.1. Отношения порядка
    9.1.1. Отношения строгого частичного порядка
    9.1.2. Строгие и нестрогие порядки
    9.2. Примеры
    9.3. Операции над частично упорядоченными
    множествами
    9.4. Какие порядки считать «одинаковыми»?
    9.5. Конечные линейные порядки
    9.6. Порядки и индукция
    9.7. Антицепи
    Лекция 10. Вероятность: первые шаги
    10.1. Элементарная теория вероятностей:
    определения
    10.2. Вероятность объединения событий
    10.3. Вероятностный метод
    10.4. Условные вероятности
    10.5. Случайная величина, математическое
    ожидание
    10.6. Частота орлов при подбрасывании монеты и
    биномиальные коэффи­циенты
    10.7. Большие уклонения: неравенство Чернова
    10.8. Подробности для любознательных
    10.8.1. Ещё одна элементарная оценка отношения
    биномиальных ко­эффициентов
    10.8.2. Другое доказательство неравенства
    Чернова
    Лекция 11. Комбинаторные игры
    11.1. Позиции
    11.2. Стратегии
    11.3. Разбор с конца
    11.4. Симметричные стратегии
    11.5. Ним
    11.6. Сумма игр и функция Шпрага — Гранди
    Часть III. Вычислимость
    Лекция 12. Разрешающие деревья
    12.1. Задача об угадывании числа. Деление
    пополам. Мощностная нижняя оценка
    12.2. Формализация модели
    12.3. Угадывание числа, неадаптивный вариант
    задачи
    12.4. Ограниченные модели разрешающих
    деревьев. Сортировка, взвеши­вания, булевы
    функции
    12.5. Рассуждение с противником
    Лекция 13. Булевы схемы и формулы
    13.1. Булевы схемы
    13.2. Формулы
    Лекция 14. Алгоритмическая неразрешимость
    14.1. Игра FRACTRAN
    14.2. Что утверждается?
    14.3. Отступление о процессорах
    14.4. Кодирование
    14.5. Класс вычислимых функций
    14.6. Определение вычислимости?
    14.7. Компромисс
    14.8. Композиция вычислимых функций
    14.9. Не все функции вычислимы
    14.10. Неразрешимость проблемы остановки
    14.11. Самоприменимость
    14.12. Перечисление останавливающихся программ
    14.13. Как доказать неразрешимость?
    14.14. Язык программирования для доказательства
    теоремы Конвея
    14.15. Сведение проблемы остановки: от программ
    к пасьянсам
    Лекция 15. Вычислимые функции, разрешимые и
    перечислимые множества
    15.1. Примеры вычислимых функций
    15.2. Не все функции вычислимы (повторение)
    15.3. Разрешимые множества
    15.4. Перечислимые множества
    15.5. Вычислимость и конечные объекты
    15.6. Универсальная вычислимая функция
    15.7. Главная универсальная функция
    15.8. Теорема Райса — Успенского
    15.9. Теорема о неподвижной точке
    15.10. Решения задач
    Лекция 16. Машины Тьюринга
    16.1. Определения
    16.2. Тезис Чёрча — Тьюринга
    16.3. Машины Тьюринга и свойства вычислимых
    функций
    16.4. Использование машин Тьюринга в
    доказательствах
    16.5. Композиция функций, вычислимых по
    Тьюрингу, и «уборка мусора»
    16.6. Многоленточные машины Тьюринга
    16.7. Моделирование многоленточной МТ на
    одноленточной
    16.8. Универсальная машина Тьюринга
    16.9. Универсальная трёхленточная машина для
    одноленточных машин
    16.10. Соответствие между абстрактной теорией
    алгоритмов и МТ
    16.11. Машины Тьюринга в доказательствах
    неразрешимости
    16.11.1. Задача достижимости на графе
    подстановок слов
    16.11.2. Неразрешимость задачи достижимости для
    графа подстановок слов
    16.12. Решения задач
    Литература
    Об авторах

    Технічні характеристики продукту
    Автор Вялый М. Н., Рубцов А. А., Подольский В. В.
    Серія Учебники Высшей школы экономики
    Кількість сторінок 496
    Формат видання 172x242 мм
    Обкладинка Тверда обкладинка
    Папір Офсет
    Иллюстрации Черно-белые
    Напишіть власний відгук
    • Лише зареєстровані користувачі можуть написати відгуки
    *
    *
    • Неправильне
    • Відмінно
    *
    *
    *
    *

    Доставка

     

    Новая почта

    Доставка в любое отделение или почтомат Новой почты.

    Стоимость доставки по Киеву от 35 грн.

    Стоимость доставки по Украине от 45 грн.

    Срок доставки 1-2 дня.

     

    Оплата

     

    Безналичный расчет

    Оплата на карту ПриватБанка

     

     

    Наличный расчет

    Оплата при получении на почтовом отделении

    Стоимость услуги

    Новая почта - 20 грн + 2% от суммы перевода.

     

    Аннотация к книге "Лекции по дискретной математике"

    Учебник написан по материалам курса "Дискретная математика", который читается студентам младших курсов факультета компьютерных наук НИУ ВШЭ. Темы этого курса являются частью базовой математической культуры и необходимы будущим математикам, программистам и специалистам в области анализа данных, но не входят в традиционно сложившиеся курсы начального математического цикла (математический анализ, алгебра, линейная алгебра). В книге излагаются начальные сведения из перечислительной комбинаторики, теории графов, теории чисел, теории множеств, теории вероятностей, теории игр, теории вычислимости. Не претендуя на полноценный охват какой-либо из упомянутых теорий, учебник дает введение в эти области, с одной стороны, достаточное для студентов соответствующих специальностей, а с другой –– позволяющее читать специализированную литературу.
    Книга будет полезной студентам младших курсов, изучающим курс дискретной математики; преподавателям этой дисциплины; а также более широкому кругу любителей математики.

    Cодержание

    Предисловие
    Часть I. Начальные примеры
    Лекция 1. Математическая индукция
    1.1. Задача о раскраске плоскости
    1.2. Общая схема доказательств по индукции
    1.3. Варианты рассуждений по индукции
    1.3.1. С чего начинать?
    1.3.2. Сведение к меньшим
    1.3.3. Переформулировка: принцип наименьшего
    числа
    1.4. Как не надо
    1.5. Как догадаться, что доказывать?
    1.6. Доказательства по индукции и без индукции
    1.7. Индукция и рекурсия
    1.8. Доказательства неравенств по индукции
    1.8.1. Неравенство Бернулли
    1.8.2. Среднее арифметическое и среднее
    геометрическое
    1.9. Пример из алгебры: системы однородных
    уравнений
    1.10. Коды Грея
    1.11. Теорема Холла о представителях
    1.12. Задачи для самостоятельного решения
    Лекция 2. Подсчёты
    2.1. Правило суммы
    2.2. Рекуррентное соотношение: пример
    2.3. Рекуррентное соотношение: число путей
    2.4. Слова и правило произведения
    2.5. Выбор с ограничениями
    2.6. Подсчёты с кратностью
    2.7. Подмножества и числа сочетаний
    2.8. Ещё о числах сочетаний
    2.8.1. Симметрия
    2.8.2. Сумма чисел в строке
    2.8.3. Знакочередующаяся сумма
    2.8.4. Снова о включениях и исключениях
    2.8.5. Пути, подмножества, слова
    2.8.6. Соседние числа в строке
    2.8.7. Монеты и перегородки
    2.9. Бином Ньютона и производящие функции
    2.10. Числа Каталана
    2.10.1. Правильные последовательности скобок
    2.10.2. Рекуррентная формула
    2.10.3. Вычисление с помощью отражений
    2.10.4. Вычисление с производящей функцией
    2.10.5. Вычисление с теорией вероятностей и
    поворотами
    2.10.6. Доказательство по индукции с дробными
    параметрами
    2.10.7. Неассоциативные произведения,
    триангуляции и стековый каль­кулятор
    2.11. Что дальше?
    Лекция 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.2.1. Определение
    3.2.2. Соседи. Степени вершин
    3.2.3. Связные компоненты
    3.2.4. Расстояния. Простые пути
    3.2.5. Деревья
    3.2.6. Полное бинарное дерево
    3.3. Ориентированные графы
    3.3.1. Определение
    3.3.2. Степени вершин
    3.3.3. Пути и достижимость
    3.3.4. Достижимость и разрезы
    3.3.5. Компоненты сильной связности и
    ациклические графы
    3.3.6. Графы преобразований
    3.4. Эйлеровы циклы
    3.4.1. Определение
    3.4.2. Критерий существования
    3.4.3. Последовательности де Брёйна
    3.4.4. Гамильтоновы циклы
    3.5. Двудольные графы
    3.5.1. Определение
    3.5.2. Двудольные графы и раскраска в два цвета
    3.5.3. Степени вершин
    3.5.4. Паросочетания
    3.6. Клики и независимые множества
    Лекция 4. Арифметика остатков
    4.1. Чётные и нечётные числа
    4.2. Деление на 3 и остатки
    4.3. Деление с остатком
    4.4. Сравнения по модулю
    4.5. Таблицы сложения и умножения по модулю N
    4.6. Обратимые остатки по модулю N
    4.7. Обратимые элементы и диофантовы уравнения
    4.8. Алгоритм Евклида
    4.9. Алгоритм Евклида и диофантовы уравнения
    4.10. Однозначность разложения на множители
    4.11. Китайская теорема об остатках
    4.12. Малая теорема Ферма
    4.13. Функция Эйлера и теорема Эйлера
    4.14. Что дальше?
    Часть II. Основные конструкции
    Лекция 5. Множества и логика
    5.1. Основные свойства множеств и операции с
    множествами
    5.2. Теоретико-множественные тождества
    5.3. Логические переменные, логические связки
    5.4. Наблюдения
    5.5. Какие связки необходимы?
    5.5.1. Полнота дизъюнкции, конъюнкции и
    отрицания
    5.5.2. Полнота конъюнкции и отрицания
    5.5.3. Алгебраическое доказательство полноты
    5.6. Формула включений-исключений
    5.6.1. Первое доказательство
    5.6.2. Второе доказательство
    5.6.3. Формула для симметрической разности
    Лекция 6. Функции
    6.1. Пример
    6.2. Функции и связанные с ними понятия
    6.2.1. Терминология и обозначения
    6.2.2. Образ множества, полный прообраз
    6.3. Декартово произведение множеств и графики
    функций
    6.4. Инъекции, сюръекции и биекции
    6.4.1. Определения
    6.4.2. Биекции и сравнение множеств
    6.5. Композиции функций
    6.5.1. Определение
    6.5.2. Ассоциативность
    6.5.3. Обратная функция
    6.5.4. Степени композиций
    6.6. Подсчёты
    6.7. Задачи для самостоятельного решения
    Лекция 7. Отношения и их графы
    7.1. Отношения в естественном языке
    7.2. Отношения с точки зрения математики
    7.3. Свойства бинарных отношений
    7.4. Графы, матрицы и бинарные отношения
    7.5. Отношения эквивалентности
    7.6. Композиция отношений
    7.7. Отношения: что дальше?
    7.8. Задачи для самостоятельного решения
    Лекция 8. Мощность множеств
    8.1. Равномощные множества
    8.1.1. Определение равномощности
    8.1.2. Свойства равномощности
    8.1.3. Примеры равномощных множеств
    8.2. Счётные множества
    8.2.1. Определение и простейшие примеры
    8.2.2. Свойства счётных множеств
    8.3. Несчётные множества
    8.3.1. Интервал и отрезок равномощны
    8.3.2. Добавление счётного множества
    8.3.3. Числа и последовательности
    8.3.4. Отрезок и квадрат
    8.4. Диагональный аргумент Кантора и сравнение
    мощностей
    8.4.1. Несчётность отрезка
    8.4.2. Сравнение мощностей
    8.5. Что дальше?
    Лекция 9. Упорядоченные множества
    9.1. Отношения порядка
    9.1.1. Отношения строгого частичного порядка
    9.1.2. Строгие и нестрогие порядки
    9.2. Примеры
    9.3. Операции над частично упорядоченными
    множествами
    9.4. Какие порядки считать «одинаковыми»?
    9.5. Конечные линейные порядки
    9.6. Порядки и индукция
    9.7. Антицепи
    Лекция 10. Вероятность: первые шаги
    10.1. Элементарная теория вероятностей:
    определения
    10.2. Вероятность объединения событий
    10.3. Вероятностный метод
    10.4. Условные вероятности
    10.5. Случайная величина, математическое
    ожидание
    10.6. Частота орлов при подбрасывании монеты и
    биномиальные коэффи­циенты
    10.7. Большие уклонения: неравенство Чернова
    10.8. Подробности для любознательных
    10.8.1. Ещё одна элементарная оценка отношения
    биномиальных ко­эффициентов
    10.8.2. Другое доказательство неравенства
    Чернова
    Лекция 11. Комбинаторные игры
    11.1. Позиции
    11.2. Стратегии
    11.3. Разбор с конца
    11.4. Симметричные стратегии
    11.5. Ним
    11.6. Сумма игр и функция Шпрага — Гранди
    Часть III. Вычислимость
    Лекция 12. Разрешающие деревья
    12.1. Задача об угадывании числа. Деление
    пополам. Мощностная нижняя оценка
    12.2. Формализация модели
    12.3. Угадывание числа, неадаптивный вариант
    задачи
    12.4. Ограниченные модели разрешающих
    деревьев. Сортировка, взвеши­вания, булевы
    функции
    12.5. Рассуждение с противником
    Лекция 13. Булевы схемы и формулы
    13.1. Булевы схемы
    13.2. Формулы
    Лекция 14. Алгоритмическая неразрешимость
    14.1. Игра FRACTRAN
    14.2. Что утверждается?
    14.3. Отступление о процессорах
    14.4. Кодирование
    14.5. Класс вычислимых функций
    14.6. Определение вычислимости?
    14.7. Компромисс
    14.8. Композиция вычислимых функций
    14.9. Не все функции вычислимы
    14.10. Неразрешимость проблемы остановки
    14.11. Самоприменимость
    14.12. Перечисление останавливающихся программ
    14.13. Как доказать неразрешимость?
    14.14. Язык программирования для доказательства
    теоремы Конвея
    14.15. Сведение проблемы остановки: от программ
    к пасьянсам
    Лекция 15. Вычислимые функции, разрешимые и
    перечислимые множества
    15.1. Примеры вычислимых функций
    15.2. Не все функции вычислимы (повторение)
    15.3. Разрешимые множества
    15.4. Перечислимые множества
    15.5. Вычислимость и конечные объекты
    15.6. Универсальная вычислимая функция
    15.7. Главная универсальная функция
    15.8. Теорема Райса — Успенского
    15.9. Теорема о неподвижной точке
    15.10. Решения задач
    Лекция 16. Машины Тьюринга
    16.1. Определения
    16.2. Тезис Чёрча — Тьюринга
    16.3. Машины Тьюринга и свойства вычислимых
    функций
    16.4. Использование машин Тьюринга в
    доказательствах
    16.5. Композиция функций, вычислимых по
    Тьюрингу, и «уборка мусора»
    16.6. Многоленточные машины Тьюринга
    16.7. Моделирование многоленточной МТ на
    одноленточной
    16.8. Универсальная машина Тьюринга
    16.9. Универсальная трёхленточная машина для
    одноленточных машин
    16.10. Соответствие между абстрактной теорией
    алгоритмов и МТ
    16.11. Машины Тьюринга в доказательствах
    неразрешимости
    16.11.1. Задача достижимости на графе
    подстановок слов
    16.11.2. Неразрешимость задачи достижимости для
    графа подстановок слов
    16.12. Решения задач
    Литература
    Об авторах

    Технічні характеристики продукту
    Автор Вялый М. Н., Рубцов А. А., Подольский В. В.
    Серія Учебники Высшей школы экономики
    Кількість сторінок 496
    Формат видання 172x242 мм
    Обкладинка Тверда обкладинка
    Папір Офсет
    Иллюстрации Черно-белые