Контрольная работа Методические указания по выполнению




Скачать 82.14 Kb.
НазваниеКонтрольная работа Методические указания по выполнению
Дата публикации10.02.2014
Размер82.14 Kb.
ТипКонтрольная работа
shkolnie.ru > Математика > Контрольная работа
Контрольная работа

Методические указания по выполнению.

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

Первые четыре задачи относятся к первой главе – теории множеств.

В первой задаче необходимо аналитически доказать равенство в пункте (а), используя свойства операций над множествами (по материалам п. 1.2.5), а также проиллюстрировать его диаграммами Эйлера-Венна (по материалам п. 1.2.2).

Например: Пусть нужно доказать равенство A\(A\B)=AB. Преобразуем левую часть: A \ (A \ B) = A \ (A B) (по свойству разности № 10) = = A  (A  B) (по двойственности № 9) = (A A)  (A  B) (по дистрибутивности № 4) =   (A  B) (по свойству дополнения № 7) = A  B (по свойству нуля № 5)  получена правая часть, т.е. равенство доказано.

В пункте (б) следует использовать определение операции декартова произведения, например: (AB)C = {(a,c) | a  AB, c  C} = {(a,c) | (a  A или a  B), c  C} = {(a,c) | (a  A, c  C) или (a  B, c  C} = … (далее аналогично).

Во второй задаче необходимо построить в декартовой системе координат каждое из заданных отношений (по материалам п. 1.3.2, рекомендуется первый способ графического представления – см. пример 1.13), построить обратное к композиции отношение. Найти области определения и множества значений всех трех отношений. Проверить по матрице свойства заданного отношения (по материалам п. 1.3.4), при этом сначала необходимо давать определение, а затем применять его к конкретной задаче.

Например: Пусть на некотором этапе решения задачи получена матрица отношения . Отношение рефлексивно, если на главной диагонали матрицы нет нулей, следовательно, данное отношение рефлексивно. Отношение симметрично, если исходная и транспонированная матрицы совпадают. В нашем случае это не так (выписать транспонированную матрицу), значит, отношение не является симметричным. И так далее – для всех свойств.

В третьей задаче необходимо проверить свойства заданного отношения согласно определениям (по материалам п. 1.3.3) – т.е. либо показать, что определение справедливо для всех элементов из области определения отношения, либо (если это не так) привести контрпример, т.е. показать, что для некоторой пары элементов – и указать эту пару – определение не выполняется.

Например, рассмотрим отношение P = {(x,y) | x,y Z и x+y > 7}. Отношение определено на всем множестве ^ Z, т.к. для любого целого x можно найти такое yZ, что x+y > 7. В силу коммутативности операции сложения, данное отношение является симметричным (т.е. (x,y)P  (y,x)P). Очевидно, что рефлексивным (т.е. (x,x)P) оно не является – например, (1,1)  P. Что касается транзитивности, согласно определению должно выполняться (x,y)P и (y,z)P  (x,z)P. 1+7>7, 7+2>7, но не 1+2>7,  отношение не транзитивно.

В четвертой задаче дано утверждение, которое следует доказать, используя принцип математической индукции (по материалам п. 1.4.3). Для этого сначала утверждение проверяется для начального значения параметра n (это может быть или 0, или 1, или 2 – в зависимости от задания) – это так называемая база индукции. Затем предполагается, что утверждение справедливо для n. Если в этом предположении удастся показать, что оно справедливо и для n+1, то доказательство считается законченным.

Например: Доказать, что   Z, n > 0 выражение n3 – n кратно трем. База индукции n = 1 (т.к. по заданию n > 0): 13–1 = 0, т.е. кратно трем. Предположим, что n3–n = 3k и покажем, что в таком случае (n+1)– (n+1) = 3m. (n+1)– (n+1) = n3+3n2+3n+1–n–1 = (n3–n)+3(n2+n); т.к. первое слагаемое делится на 3 по индукционному предположению, а у второго коэффициент 3, значит, и все выражение кратно 3.

Задачи №№ 5–8 относятся к главе № 2 – элементам комбинаторики.

В пятой задаче задание сводится к определению числа разбиений множества на заданное количество подмножеств (по материалам п. 2.4.2). В первом вопросе задачи группы, на которые следует разбить исходное множество, принципиально различны, следовательно, речь идет об упорядоченных разбиениях (т.е. о тех, когда порядок блоков имеет значение). Значит, следует использовать формулу (2.5). Во втором вопросе блоки абсолютно одинаковы, значит, их порядок значения не имеет и речь идет о разбиениях неупорядоченных. Можно для вычисления использовать числа Стирлинга 2 рода (если нет какого-либо ограничивающего условия на минимальное число элементов в блоке) или упорядоченные разбиения, устранив из их формулы порядок.

Например: Пусть дано множество {a,b,c,d}. Определить количество упорядоченных и неупорядоченных разбиений его на 2 подмножества.

Разбиения на 2 подмножества возможны на 1+3 элемента и 2+2. Для неупорядоченных: R(4;1,3)+R(4;2,2)/2 – т.к. формула предназначена для подсчета числа упорядоченных разбиений, а поскольку во втором случае элементов в блоках одинаковое количество (2 и 2), то будет автоматически учтен порядок, что нужно исключить. Значит, каждое из выражений, где есть блоки одинакового размера, нужно разделить на число перестановок этих блоков (с одинаковым количеством элементов) – в нашем случае это 2!. Следовательно, в итоге количество неупорядоченных разбиений 4!/(1!·3!)+4!/(2!·2!)/2! = 4+3 = 7. Если считать через числа Стирлинга 2 рода: S(4,2) = S(3,1) + 2·S(3,2) = 1 + 2·(S(2,1) + 2·S(2,2)) = 1 + 2·(1 + 2·1) = 7. Если выписать эти разбиения явно, получим: {{a},{b,c,d}}, {{b},{a,c,d}}, {{c},{a,b,d}}, {{d},{a,b,c}}, {{a,b},{c,d}}, {{a,c},{b,d}}, {{a,d},{b,c}}. Если бы, например, в задаче требовалось найти разбиения множества из 7 элементов с помощью формулы для R(7;2,2,1,1,1), то для исключения порядка ее бы следовало разделить на (2! 3!).

Для упорядоченных разбиений при выписывании добавятся варианты с обратным расположением блоков, т.е. еще 7, следовательно, всего 14. При подсчете вариантов: R(4,2) = R(4;1,3) + R(4;2,2) + R(4;3,1) = 2·R(4;1,3) + R(4;2,2) = 2·4!/(3!·1!) + 4!/(2!·2!) = 8+6 = 14. Т.е. при наличии в формуле блоков разных размеров следует для сокращения расчетов умножать ее на число перестановок этих блоков (определяемое согласно комбинаторной формуле).

Для определения того же R(7;2,2,1,1,1) в результате перестановок блоков с 1 и 2 элементами: 2+2+1+1+1 = 2+1+1+1+2 = 2+1+2+1+1+1=… – появится коэффициент 5!/(2!·3!) = C(5,2) = 10 (согласно п. 2.4.1, формула 2.3), т.е. количество различных перестановок таких блоков равно 10. Значит, в результирующем выражении при подсчете числа упорядоченных разбиений в состав общей суммы войдет 10·R(7;2,2,1,1,1).

Шестая задача решается на основании принципа включения и исключения (по материалам п. 2.5) с применением формулы 2.8 (см. пример 2.24 в лекциях).

В седьмой задаче следует использовать полиномиальную теорему (по материалам п. 2.4.2, формула 2.6). При определении ni в формуле 2.6 нужно обратить внимание на степени переменных в исходном выражении, а при вычислении числового коэффициента – на коэффициенты при переменных в исходном выражении.

Например: Пусть надо определить, чему равен коэффициент при x2·y2·z4 в выражении (2x2+3y+2z2)5. Для x2·y2·z4: (2x2)1·(3y)2·(2z2)2 . Значит, степени соответственно равны 1, 2 и 2, а числовой коэффициент имеет вид R(5;1,2,2)·21·32·22 = 5!/(1!·2!·2!)·21·32·22 = 2 160.

^ В восьмой задаче нужно найти частное решение рекуррентного уравнения с заданными начальными условиями (по материалам 2-й главы лекций, п. 2.6). Для этого требуется построить характеристический многочлен (формула 2.10) и найти его корни. Затем на основании теоремы 2.11 выписывается общее решение an рекуррентного соотношения, в котором присутствуют неизвестные константы c1, c2 (см. пример 2.29). После этого на основании заданных начальных условий составляется система уравнений и из нее определяются эти константы.

Задачи №№ 9, 10 относятся к главе № 3 – элементам теории графов.

^ В девятой задаче нужно построить ориентированный граф по заданной матрице смежности и определить его компоненты сильной связности, т.е. такие группы вершин, что каждая из них составляет максимальный сильно связный подграф (по материалам главы 3, п. 3.2.3, 3.4.2, 3.5.1). Затем следует заменить все дуги ребрами и в полученном неориентированном графе найти эйлеров цикл или цепь (по материалам главы 3 п. 3.5.4). При этом в случае соединения двух вершин a и b дугами (a,b) и (b,a) в неориентированном графе появятся кратные ребра. Для выяснения возможности построения эйлерова цикла или цепи (согласно определению, это соответственно цикл или цепь, проходящий по всем ребрам графа ровно по одному разу) необходимо определить степени всех вершин (см. лекции, п. 3.2.1). Условие наличия эйлерова цикла – четность степеней всех вершин. Для существования эйлеровой цепи в графе должно быть ровно две вершины с нечетными степенями.

В десятой задаче для построения остовного подграфа минимального веса следует использовать алгоритм Краскала (согласно п. 3.5.3 лекций) – нужно построить само дерево и вычислить его вес. Что касается второй части задачи, для ее решения необходимо применять алгоритм Дейкстры (согласно п. 3.5.3 лекций). При этом нужно обратить внимение на то, что пометки вершин (см. пример 3.32 из п. 3.5.3) изменяются только в случае, когда найдено более короткое расстояние. При этом поиск минимального расстояния выполняется по всем временным вершинам, а не только по тем, которые входили в множество смежности на последнем шаге.

Вариант 3


1 Доказать равенства, используя свойства операций над множествами и определения операций. Проиллюстрировать при помощи диаграмм Эйлера-Венна. а)  (A\B)  (A\C) = A \ (BC) б)  A(B\C)=(AB)\(AC).

2 Даны два конечных множества: А={a,b,c}, B={1,2,3,4}; бинарные отношения P AB, P B2. Изобразить P1, P2 графически. Найти P = (P2◦P1)–1. Выписать области определения и области значений всех трех отношений: P1, P2, Р. Построить матрицу [P2], проверить с ее помощью, является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным. P= {(a,1),(a,2),(a,4),(c,3),(c,2),(c,4)}; P= {(2,1),(3,1),(3,2),(4,1),(4,3)}.

3 Задано бинарное отношение P; найти его область определения и область значений. Проверить по определению, является ли отношение P рефлексивным, симметричным, антисимметричным, транзитивным. P  R2, P = {(x,y) | y = |x|}.

^ 4 Доказать утверждение методом математической индукции: для n  2.

5 Шестеро сотрудников фирмы направляются на изучение иностранного языка, причем нужно распределить их для изучения английского, немецкого и французского языков (каждый изучает только один язык). Сколько существует различных способов такого распределения? Сколькими способами они могут устроиться заниматься в двух совершенно одинаковых комнатах библиотеки (не менее одного в комнате)?

6 Сколько существует положительных трехзначных чисел: а) не делящихся ни на одно из чисел 4, 7, 18? б) делящихся ровно на одно из этих трех чисел?

7 Найти коэффициенты при a=x2·y·z6, b=x4·y·z, c=y2·z8 в разложении (3·x+5·y+2·z2)6.

8 Найти последовательность {an}, удовлетворяющую рекуррентному соотношению 4·an+2 + 9·an+1 + 5·an = 0· и начальным условиям a1=1, a2=4.



9

Орграф задан матрицей смежности. Необходимо:
а) нарисовать граф;
б) выделить компоненты сильной связности;
в) заменить все дуги ребрами и в полученном неориентированном графе найти эйлерову цепь (или цикл).

1
0
1
0
0
1

0
1
1
1
0
1

1
1
0
0
0
0

0
1
0
0
1
0

0
1
0
1
0
1

0
0
0
0
0
1

10 Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти: а) остовное дерево минимального веса;
б) кратчайшее расстояние от вершины v3 до остальных вершин графа, используя алгоритм Дейкстры.

Похожие:

Контрольная работа Методические указания по выполнению iconКонтрольная работа Методические указания по выполнению
Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями....
Контрольная работа Методические указания по выполнению iconМетодические указания по выполнению контрольной работы контрольная...
Контрольная работа по курсу «Теория бухгалтерского учета» предназначена для студентов заочного обучения по специальности 08010965...
Контрольная работа Методические указания по выполнению iconМетодические указания по выполнению контрольной работы. Контрольная...
Контрольная работа по дисциплине «Экономика малого бизнеса» состоит из нескольких заданий, которые логически связаны между собой....
Контрольная работа Методические указания по выполнению iconМетодические указания по выполнению контрольной работы по дисциплине «маркетинг»
Контрольная работа носит учебно практический характер и предназначена для закрепления знаний по ряду тем курса
Контрольная работа Методические указания по выполнению iconКонтрольная работа состоит из 3 задач и выполняется по вариантам....
Задания и методические указания к выполнению контрольной работы по курсу «Маркетинг»
Контрольная работа Методические указания по выполнению iconМетодические указания к выполнению контрольной работы по дисциплине «Основы философии»
...
Контрольная работа Методические указания по выполнению iconКонтрольная работа выполняется по вариантам. Номер варианта выбирается...
Задания и методические указания к выполнению контрольной работы по курсу “Менеджмент и маркетинг в информационных технологиях”
Контрольная работа Методические указания по выполнению iconМетодические указания по выполнению контрольной работы составитель: В. В. Ильяшенко
Контрольная работа приравнивается к зачету и рас­сматривается как одна из форм итогового контроля знаний студентов в учебном процессе...
Контрольная работа Методические указания по выполнению iconМетодические указания по выполнению контрольных работ для студентов заочной формы обучения
Только при соблюдении всех этих условий контрольная работа будет способствовать расширению кругозора и повышению уровня подготовки...
Контрольная работа Методические указания по выполнению iconОбщие методические указания по выполнению письменных контрольных...
Составитель: О. Ю. Баранова. Теплотехника: Задания и методические указания по выполнению контрольных работ для слушателей факультета...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
shkolnie.ru
Главная страница