Подготовка к ДМ-2014

Как готовиться к экзамену по дискретной математике 2014


1. Прочитать конспект.

2. Прочитать учебник.

3. Рассказывать другу или в крайнем случае себе определения, алгоритмы и теоремы. Сначала делать это с открытым конспектом или учебником, читая по тексту, потом пробовать делать это с закрытым.

4. Решить задачи, которые были рассмотрены на лекции, как подготовка к экзамену.

5. Решить задачи, которые были заданы на лекции как упражнения.

6. Решить задачи с сайта преподавателя, которые даны как подготовительные к экзамену.


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

1. Предложите два разных алгоритма для перевода числа из p-ичной системы в q-ичную. Предложите два разных алгоритма для перевода числа из факториальной системы в p-ичную (из p-ичной в фактриальную).

2. Докажите единственность представления числа в факториальной системе счисления. Является ли факториальная система смешанной? Придумайте другую систему счисления, похожую на факториальную, но отличающуюся от неё. Предложите алгоритм сложения чисел в факториальной системе счисления.

3. Какова трудоемкость алгоритма Евклида? Сколько операций деления в худшем случае придется сделать, если работать с числами до миллиарда?

4. Сформулируйте алгоритм для сокращения дробей. Проиллюстрируйте его работу для дроби 222222222222/33333333

5. Как решать диофантово уравнение ax+by+c=0? Как решать аналогичное диофантово уравнение с темя переменными ax+by+cz+d=0? Как изменяется решение при изменении знаков коэффициентов? Как меняется решение при умножении всех коэффициентов на одно и то же число? Известно, что x=y=z=0 является одним из решений последнего уравнения. Найдите: ещё одно решение, ещё два решения, ещё бесконечно много решений.

6. Дайте определение наилучшего приближения. Сформулируйте алгоритм, который генерирует наилучшие приближения для заданного рационального числа a/b.

7. Дайте определение деления многочленов с остатком. Можно ли определить деление многочленов, коэффициенты которого принадлежат кольцу вычетов по непростому модулю?

8. Дайте определение цепной (непрерывной дроби) для дробно-рациональной функции. Сформулируйте алгоритмы перевода дробно-рациональной функции в цепную дробь и обратно. Дайте определение подходящих дробей для дробно-рациональной функции и сформулируйте как можно больше свойств этих дробей. Может ли др.-рац. функция

y=(x^3+1)/(x^2-1) быть подходящей для какой-либо др.-рац. функции?

9. Дайте определение неприводимых многочленов. Существуют ли разложимые над полем К многочлены, не имеющие корней?

10. Как устроен алгоритм RSA? На какой теореме он основан? Какие проблемы возникают при его реализации? Что такое криптографический протокол? Придумайте криптографический протокол «бросание монеты по телефону».


Comments