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

Тренировочные задачи к экзамену по дискретной математике

 

    1. Алгоритм Евклида.

Оцените утверждения:

1.1.  НОК (НОД (a;b); НОД (a;c); НОД (b;c)) делится и на a, и на b, и на c;

1.2.  НОД (a;b) = НОД (a2-b2; b);

1.3.  НОД (a;b) = НОД ((a-1)(b+1); b).

 

    2. Бинарный алгоритм Евклида.

Оцените утверждения:

при нахождении наибольшего общего делителя чисел 410 и 6

бинарный алгоритм Евклида сделает не более

2.1.  15 шагов;

2.2.  20 шагов;

2.3.  25 шагов.

 

    3. Расширенный алгоритм Евклида.

Пусть (ai;bi) – пары чисел на  i-ом шаге алгоритма Евклида для пары чисел  (a;b), а  (xi;yi) – пары коэффициентов расширенного алгоритма Евклида, такие, что на  n-ом  шаге  axn+byn=1. Оцените утверждение:

3.1.  числа a и b взаимно просты;

3.2.  все числа  axi+byi  при i<n являются делителями чисел a и b;

3.3.  число  axi+byi  делится на НОД(a;b);

3.4.  axn+1+byn+1=0;

3.5.  |xn|<|b|, |yn|<|a|.

 

    4. Линейное представление наибольшего общего делителя.

Рассмотрим множество  L={na+mb| n,m - целые} для двух взаимно простых натуральных

чисел  a и b.

Оцените утверждения:

4.1.  L=Z;

4.2.  L={na2+mb2| n,m - целые};

4.3.  L={na+(m+n)b| n,m - целые}.

 

    5. Простейшие диофантовы уравнения.

Диофантово уравнение  ax+by=c  имеет решение  (x0;y0). НОД(a;b;c)=d.

Оцените утверждения:

5.1.  (x0+b; y0-a) – является решением данного уравнения;

5.2.  (x0+b/d; y0-a/d) – является решением данного уравнения;

5.3.  (x0/d; y0/d) – является решением данного уравнения;

 

    6. Арифметика многочленов.

Даны многочлены P(x) и Q(x) над полем K, не являющиеся константами.

Оцените утверждения:

6.1.  deg(P+Q)=deg(P)+deg(Q);

6.2.  l(P+Q)=l(P)+l(Q);

6.3.  deg(PQ)=deg(P)+deg(Q);

6.4.  l(PQ)=l(P)l(Q);

 

    7. Наибольший общий делитель многочленов и его линейное представление.

Даны взаимно простые многочлены P(x) и Q(x) над полем K. Оцените утверждения:

7.1.  существуют многочлены A(x) и B(x) над K, такие что A(x)P(x)+B(x)Q(x)=x;

7.2.  если A(x) и B(x) такие, что A(x)P(x)+B(x)Q(x)=1, то deg(A)<deg(Q) и deg(B)<deg(P);

7.3.  если A(x) и B(x) такие, что A(x)P(x)+B(x)Q(x)=1, то A(x) и B(x) взаимно простые.

 

    8. Разложение рациональной дроби в цепную (непрерывную)

Дан многочлен P(x)=x-a  и многочлен Q(x) такой, что Q(a)¹0  и  deg(Q)=n.

Оцените утверждения относительно разложения  P(x)/Q(x) в цепную дробь:

8.1.  цепная дробь конечна;

8.2.  цепная дробь состоит из  n+1  ненулевых членов;

8.3.  последний член цепной дроби равен x/Q(a)-a/Q(a).

 

    9. Разложение многочлена на свободные от квадратов множители

Дан многочлен P(x) над полем рациональных чисел Q, его разложение на свободные от квадратов множители имеет вид P(x)=P1(x)[P2(x)]2[P3(x)] 3.

Оцените утверждения:

9.1.  многочлены P1(x), P2(x) и P3(x)  неприводимы над полем рациональных чисел;

9.2.  многочлены P1(x), P2(x) и P3(x)  попарно взаимно просты.

 

    10. Кратные и простые корни многочлена

Дан многочлен P(x) над полем вещественных чисел R, P'(x) - его производная.

Оцените утверждения:

10.1.                   НОД(P(x); P'(x)) не имеет кратных корней;

10.2.                   многочлены P(x)/ НОД(P(x); P'(x))  и P(x)  имеют одинаковое множество корней;

10.3.                   многочлены P'(x)/ НОД(P(x); P'(x))  и P(x)  взаимно просты.

 

    11. Неприводимые многочлены

Многочлен  P(x)=x2+ax+b  неприводим в Z3[x].

Оцените утверждения:

11.1.                   многочлен  P(x)  не имеет целых корней;

11.2.                   многочлен  P(x)  приводим в Z6[x];

11.3.                   многочлен  P(x)  приводим в Z2[x].

 

    12. Функция Эйлера

Количество натуральных чисел, меньших нечётного числа N и взаимно простых с ним равно k. Оцените утверждения:

12.1.                   количество натуральных чисел, меньших  2N  и взаимно простых с ним равно k;

12.2.                   количество натуральных чисел, меньших  3N  и взаимно простых с ним равно 2k;

12.3.                   количество натуральных чисел, меньших  4N  и взаимно простых с ним равно 2k.

 

    13. Малая теорема Ферма и теорема Эйлера

Нечётные числа p и q различные и простые. Оцените утверждения:

13.1.                   (p+2)q=pq+2q (mod 2);

13.2.                   (p+2)q=pq+2q (mod p);

13.3.                   (p+2)q=pq+2q (mod q);

13.4.                   2*2qp=2q+p (mod pq);

13.5.                   pq-1qp-1= pq-1+qp-1 (mod pq).

 

    14. Комбинаторика: правило сложения

Пусть N – количество n-значных чисел, M – количество чисел среди них, у которых все цифры ненулевые, K – количество чисел среди них, у которых одна нулевая цифра, P – количество чисел среди них, у которых по крайне мере одна нулевая цифра. Оцените утверждения:

14.1.                   K+P=N

14.2.                   M+K=N

14.3.                   K+M=P

 

    15. Формула включений-исключений

Рассмотри конечное множество целых неотрицательных чисел M. Обозначим  A- подмножество M чисел, у которых по крайней мере одна цифра ненулевая, B - подмножество M чисел, у которых ровно одна цифра ненулевая, C - подмножество M чисел, у которых ровно одна цифра ненулевая. Оцените утверждения:

15.1.                   |A|+|C|=|M|

15.2.                   |A|-|B|+|C|=1

 

    16. Сочетания

C(n;k) - число сочетаний, n – простое, 0<k<n. Оцените утверждения:


16.1.             C(n;k) делится на n   ;

16.2.                   производящая функция   f(x) = 1 + nx+ ...+ C(n;k)*xk+... является многочленом;

16.3.                   производящая функция   f(x) = xk + ...+ C(n;k)*xn+... является многочленом.

 

    17. Перестановки

Перестановки чисел от  1  до  n  упорядочены в лексикографическом порядке (первая перестановка  (1,2,3…n)).  Оцените утверждения:

17.1.                   перестановка (213…n) стоит на 121 месте;

17.2.                   единица стоит на последнем месте в 20 перестановках.

 

    18. Задание отношения матрицей

Отношение задано матрицей, у которой ниже главной диагонали стоят нули, а остальные элементы равны 1. Оцените утверждения:

18.1.                   отношение рефлексивно;

18.2.                   отношение симметрично;

18.3.                   отношение антисимметрично;

18.4.                   отношение асимметрично;

18.5.                   отношение транзитивно;

18.6.                   отношение является отношением частичного порядка;

18.7.                   отношение является отношением линейного порядка;

18.8.                   отношение является отношением эквивалентности.

 

    19. Отношение порядка

Граф отношения строгого порядка R содержит 11 вершин и 55 рёбер. Оцените утверждения:

19.1.                   отношение R транзитивно;

19.2.                   отношение R является отношением строгого линейного порядка;

19.3.                   отношение R не является рефлексивным;

19.4.                   отношение R антирефлексивно;

19.5.                   к графу отношения можно применить алгоритм Уоршелла и граф после его применения не изменится;

19.6.                   к графу отношения можно применить алгоритм топологической сортировки;

19.7.                   существует несколько различных вариантов топологической сортировки вершин графа.

 

 

    20. Инварианты графа

Неориентированный граф имеет 2 компоненты связности и 49 рёбер. Оцените утверждения:

20.1.                   граф определяет отношение эквивалентности на множестве вершин;

20.2.                   хроматическое число графа равно 10;

20.3.                   хроматическое число графа равно 11;

20.4.                   цикломатическое число графа равно 40;

20.5.                   цикломатическое число графа равно 39;

20.6.                   граф является планарным.

 

 

 

Comments