Вопросы к зачету
Конечные суммы. Способы записи конечных сумм. Арифметическая и геометрическая прогрессии.
Конечные последовательности, их применение для вывода некоторых конечных сумм.
Рекуррентные соотношения и возвратные последовательности. Нахождение общего решения линейного однородного рекуррентного уравнения.
Рекуррентные соотношения и возвратные последовательности. Нахождение общего решения линейного неоднородного рекуррентного уравнения.
Биномиальные коэффициенты. Элементарные тождества. Доказательство одного из них (по указанию преподавателя). Треугольник Паскаля.
Доказательство бинома Ньютона.
Свойства биномиальных коэффициентов. Доказательство свойства  .
Свойства биномиальных коэффициентов. Доказательство тождества Коши.
Числа Стирлинга первого и второго рода. Формула чисел Стирлинга второго рода. Число Белла.
Символы o, O. Свойства отношений o и O.
Символ ~. Формула Стирлинга. Асимптотика n! и  .
Размещения с повторениями и без повторений, их число.
Сочетания с повторениями и без повторений, их число.
Подстановки и перестановки.
Разбиения. Комбинаторный смысл полиномиальных коэффициентов, чисел Стирлинга и числа Белла.
Принцип включения и исключения, его применение.
Теорема обращения. Формулы обращения для биномиальных коэффициентов.
Производящие функции, их применение.
Функция Мёбиуса. Формула обращения Мёбиуса.
Графы и орграфы. Реализации графов. Изоморфизм графов.
Подграфы. Регулярные графы. Цепи. Циклы. Связность.
Тривиальные, полные и двудольные графы. Критерий двудольного графа.
Операции над графами.
Направленные орграфы и сети. n-мерный единичный куб.
Способы представления графов в ЭВМ.
Связность в орграфах. КСС. Матрица связности и матрица контрдостижимости.
Расстояния в графах. Матрица расстояний. Диаметр и радиус графа.
Деревья. Цикломатическое и коцикломатическое числа. Алгоритм нахождения остова минимального веса во взвешенном графе.
Обходы графа по глубине и ширине.
Эйлеровы графы. Теорема Эйлера. Алгоритм построения эйлерова цикла в эйлеровом графе.
Гамильтоновы графы.
Раскраска вершин графа. Хроматическое число графа.
Планарные графы. Укладка графа. Формула Эйлера и её следствия.
Теоремы о пяти и о четырёх красках.
Б. 3. 14. Математическая логика
Вопросы к экзамену
1. Предмет и метод математической логики.
2. Высказывание. Виды препозиционных операций.
3. Понятие формулы. Виды формул. Основные равносильности.
4. Нормальные формы формул логики высказываний.
5. Совершенные нормальные формы.
6. Методы приведения формулы с СНФ.
7. Применение логики высказываний к анализу и синтезу РКС.
8. Схемы, содержащие функциональные элементы. Сумматоры. Многополюсники.
9. Закон Двойственности.
10. Задача аксиоматического построения логики высказываний.
11. Доказуемые формулы. Доказательство.
12. Выводимость из формул. Примеры выводимости.
13. Теорема дедукции и ее применение.
14. Равносильные формулы исчисления высказываний.
15. Требования к системам аксиом исчисления высказываний.
16. Независимость аксиом исчисления высказываний.
17. Логика предикатов. Основные понятия.
18. Равносильные формулы логики предикатов.
19. Запись теорем школьной математики с помощью формул логики предикатов.
20. Нормальные формы логики предикатов.
21. Предваренная нормальная форма в логике предикатов.
22. Проблема разрешения в логике предикатов.
23. Исчисления предикатов.
24. Алгоритм и его основные свойства.
25. Уточнение понятия алгоритма.
26. Машина Тъюринга.
27. Понятие рекурсивных функций.
28. Примитивно-рекурсивные функции.
29. Нормальные алгоритмы Маркова.
30. Представление о тезисе Черча.
Б.3.15.Теория алгоритмов
Лабораторная работа № 1
Написание и сдача программы каждым из студентов на тему «Линейный список».
Лабораторная работа № 2
Написание и сдача программы каждым из студентов на тему «Деревья».
Лабораторная работа № 3
Написание и сдача программы каждым из студентов на тему «Решение NP-полных задач».
Лабораторная работа № 4
Написание и сдача программы каждым из студентов на тему «Поиск в тексте».
Лабораторная работа № 5
Написание и сдача программы каждым из студентов на тему «Сортировка».
Лабораторная работа № 6
Написание и сдача программы каждым из студентов на тему «Представление графов в виде матриц».
Лабораторная работа № 7
Написание и сдача программы каждым из студентов на тему «Представление графов с помощью динамических структур данных».
Лабораторная работа № 8
Написание и сдача программы каждым из студентов на тему «Генерация комбинаторных объектов».
Б.3.16 Теория вероятностей и математическая статистика
Вопросы к экзамену
Вероятностное пространство. Пространство элементарных событий. Алгебра событий. Вероятность.
Классическое определение вероятности.
Геометрическое определение вероятности.
Статистическое определение вероятности.
Случайные числа.
Условные вероятности. Вероятность произведения событий. Формула полной вероятности.
Схема Бернулли. Полиномиальная схема.
Схема Бернулли. Наиболее вероятностное число появления событий.
Теорема Пуассона.
Локальная теорема Муавра–Лапласа.
Интегральная теорема Муавра–Лапласа.
Функция распределения и её свойства.
Дискретные и абсолютно непрерывные распределения.
Совместные распределения нескольких случайных величин.
Независимость случайных величин.
Математическое ожидание. Свойства математического ожидания.
Дисперсия. Ковариация. Коэффициент корреляции.
Неравенство Чебышёва. Теорема Чебышёва. Закон больших чисел.
Закон больших чисел. Теорема Бернулли.
Цепи Маркова.
Понятие о выборке. Эмпирическая функция распределения. Гистограмма. Выборочное среднее и выборочная дисперсия.
Оценивание неизвестных параметров распределения. Метод наименьших квадратов.
Хи-квадрат распределение.
Распределение Стьюдента.
Доверительное оценивание параметров нормальных выборок.
Критерий согласия Пирсона.
Критерий проверки статистических гипотез.
Б.3.23 Введение в алгебру и анализ
Контрольная работа № 1
Примерный вариант
Если человек произносит фразу: ”Я лжец”, то может ли он быть уроженцем острова рыцарей и лжецов?
Мы попали на развилку двух дорог. Какой вопрос нужно задать аборигену, чтобы узнать, куда ведет каждая из дорог – в город лжецов или в город рыцарей?
На местном языке слова “да” и “нет” звучат как “тип” и “топ”, но неизвестно, какое из них чему соответствует. Как, задав аборигену один вопрос, выяснить, лжец он или рыцарь?
Какой вопрос нужно задать аборигену, чтобы он обязательно ответил “тип”?
В комнате находятся 12 человек. Некоторые из них всегда лгут, а остальные всегда говорят правду. Один из них сказал: “Здесь нет ни одного честного человека”, второй: “Здесь не более одного честного человека”, третий: “Здесь не более двух честных людей” и т.д., двенадцатый: “Здесь не более одиннадцати честных людей”. Сколько в комнате честных людей?
За круглым столом сидят 12 человек (лжецы и рыцари).
а) Каждый сидящий за столом произнес два высказывания: 1) слева от меня сидит рыцарь; 2) справа от меня сидит лжец. Могло ли такое быть?
б) Каждый из сидящих за столом произнес: «Напротив меня сидит лжец». Сколько лжецов за столом?
Предположим, вам встретились близнецы, которые либо лгут, либо говорят правду. Вы хотите узнать, кто из них Коля. Каждому из них разрешается задать только один вопрос, на который можно ответить только «да» или «нет». Сам вопрос должен состоять из трех слов. Какой вопрос Вы задали бы?
На столе стоят два одинаковых ящика. В каждом находится либо белый, либо черный шарик. На первом ящике надпись: “По крайней мере, в одном из этих ящиков находится белый шарик”. На втором: “Черный шарик находится в другом ящике”. Известно, что, либо обе эти надписи истинны, либо обе ложны. Есть ли в каком-нибудь ящике белый шарик и если есть, то в каком именно?
Пять пловцов - Андрей, Боря, Вася, Дима и Женя - были членами одного спортивного клуба. Однажды в отсутствие тренера они устроили между собой соревнование. Когда же тренер, вернувшись, спросил их о результатах, то услышал следующее.
Андрей. (1) Дима занял второе место, (2) а я оказался на третьем.
Боря. (3) Я показал самый лучший результат, (4) а Вася занял второе место.
Вася. (5) Я был третьим, (6) а Боря - последним.
Дима. (7) Я занял второе место, (8) а Женя- четвёртое.
Женя. (9) Мне удалось опередить лишь одного пловца.(10) Соревнование выиграл Андрей.
Увидев изумленное лицо тренера, ребята признались, что пошутили: сведения, сообщенные тренеру каждым из них, содержали одно истинное и одно ложное утверждение. Кто же какое место занял?
Когда Дмитрий Вячеславович спит, все что он считает во сне истинным на самом деле ложно и наоборот. Наяву он обо всем судит здраво, то есть считает истинное истинным, а ложное – ложным. Вчера вечером в 23 часа Дмитрий Вячеславович считал, что он и Михаил Александрович уже спят. Спал ли Михаил Александрович в это время?
«Я, как и Дмитрий Вячеславович, – сказал Михаил Александрович, во сне обо всем сужу превратно, а наяву здраво. Вчера вечером, незадолго до полуночи, Дмитрий Вячеславович думал, что я сплю. Я же в это самое время либо думал, что он спит, либо думал, что он бодрствует. Что я думал?»
На перепутье трех дорог a, b, c, ведущих в Правдычино, Кривдино и Середину-на-половине, стоят три человека А, В, С соответственно. Наш корреспондент задал им несколько вопросов и получил такие ответы.
А: каждая из трех дорог ведет в какое-нибудь село – либо в Правдычино, либо в Кривдино, либо в Середину-на-половине.
В: Я житель Середины-на-половине.
А: Все дороги ведут в различные села.
С: Я живу в том же селе, что и В.
А: Мы все трое живем в различных селах.
В: Дорога, проходящая рядом с каждым человеком, ведет не в то село, где он живет.
С: Дорога а ведет не в то село, где я живу.
А: Дорога а ведет в то село, где я живу.
В: За все время разговора С ни разу не сказал правду.
А: Последнее утверждение В ложно.
С: Дорога с ведет не в то селение, где я живу.
Установите, кто где живет, куда ведет каждая дорога.
Контрольная работа № 2
Примерный вариант
У Тани есть 5 разных фломастеров, 7 разных карандашей и 11 разных тетрадей. Сколькими способами она может подарить Коле набор из 1 фломастера, 1 карандаша и 1 тетради?
В стране ABCD из города A в город B ведут 11 дорог, из города B в город C – 7 дорог, из города A в город D ведут 5 дорог, а из города D в город C ведут 13 дорог. Сколькими различными способами можно добраться из города A в город C?
а) В алфавите племени Тумба-Бомба 5 букв: a, b, c, d, e. Сколько слов в словаре этого племени, если словом считать любую последовательность из 4 букв?
б) Сколько из этих слов не имеют повторяющихся букв?
в) Сколько из этих слов имеют хотя бы одну гласную букву (гласные буквы – a, e)?
а) Сколько существует натуральных 10-значных чисел, в десятичной записи которых нет цифры 0?
б) Сколько существует натуральных 10-значных чисел, в десятичной записи которых нет цифры 5?
в) Сколько существует натуральных 10-значных чисел, в десятичной записи которых есть цифра 5?
а) Сколькими способами можно разбить 12 школьников на две команды по 6 человек в каждой для участия в матбое?
б) Тот же вопрос, если нужно выбрать еще капитанов команд?
На плоскости даны 10 точек, никакие 3 из которых не лежат на одной прямой. Сколько существует треугольников с вершинами в данных точках?
На одной из параллельных прямых отмечено 7 точек, а на другой – 8 точек. Сколько существует треугольников с вершинами в отмеченных точках?
а) Имеется 3 гласных и 5 согласных букв. Сколько существует перестановок этих букв, в которых никакие 2 согласные буквы не стоят рядом?
б) Имеется 3 гласных и 4 согласных буквы. Сколько существует перестановок этих букв, в которых никакие 2 согласные буквы не стоят рядом?
в) Имеется 3 гласных и 3 согласных буквы. Сколько существует перестановок этих букв, в которых никакие 2 согласные буквы не стоят рядом?
Докажите, что
а)  ; б)  .
Игра «Ханойская башня». Имеется пирамида с n кольцами возрастающего диаметра (внизу самое большое) и ещё два пустых стержня той же высоты. Разрешается перекладывать кольца с одного стержня на другой, но при этом запрещается класть большее кольцо на меньшее. Докажите, что можно а) переложить все кольца на один из имеющихся пустых стержней; б) это можно сделать не более чем за 2n–1 перекладывание.
Фермер Вася хочет заплатить за обучение своего сына в ЛМШ пачками мороженого, которые у него хранятся в ящиках по 3 или 5 штук. Путевка в ЛМШ стоит больше 8 пачек мороженого. Докажите, что фермер Вася сможет заплатить требуемую сумму без сдачи.
Докажите, что сумма кубов трех последовательных натуральных чисел делится на 9.
На плоскости проведены n прямых, проходящих через одну точку. Докажите, что они разбивают плоскость на 2n областей.
Докажите, что число 11…1 (81 единица) делится на 81.
Докажите по индукции, что в графе четное число вершин нечетной степени.
Вопросы к экзамену
Множества. Подмножества. Диаграммы Эйлера-Венна. Примеры.
Операции над множествами. Свойства.
Прямое произведение множеств, n-арные отношения. Отношение эквивалентности.
Числовые множества. Числовые промежутки.
Отображения. Виды отображений. Счетные и несчетные множества.
Высказывания. Логические операции над высказываниями.
Предикаты, операции над ними.
Кванторы. Запись высказываний с помощью логического языка.
Теоремы. Виды теорем. Примеры.
Теоремы. Методы доказательств. Примеры.
Методы математической индукции. Примеры.
Размещения, перестановки и сочетания. Примеры.
Модуль действительного числа. Свойства.
Уравнения и неравенства с модулем.
Метод интервалов.
Упорядоченные множества. Закон сложения и умножения.
Бином Ньютона. Свойства.
Таблицы истинности.
Элементарные функции, их свойства
Графики функций. Преобразование графиков функций.
Графическое решение уравнений и неравенств.
Б. 3. 23. Вводный курс математики
|
