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

билет 2
1.операции над множествами и их свойства. покрытие и разбиение
2.теоретичиский минимум:
полиномиальная теорема,отношение эквивалентности, матричное представление графа, свойства базы и антибазы, счетная мощность, комбинаторные комбинации без повторений
3.задача:
В={2,3,6}, А=В декартово на В. частично упорядоченное множество (А,<). (a,b)<(c,d) тогда и только тогда когда а делится нацело на с или а=с и b делиться нацело на d. построить диаграмму Гессе

Ким №3
1.Мощность множества. Определение мощности. Метод включений и исключений.
а) понятие нечеткого множества
б) композиция бинарных отношений
в) фактор мн-ва
г) теорема вандемонга
д) с-ва производщ. ф-и
е) определение сильных компонент

Практика: ((X*корень 3-й степени из X^(-1)) + 1 / (корень седьмой степени из X^2))^10
при разложении найти член не содержащий X

Билет 4

1) Бинарные отношения. Способы задания. Связь с графами и функциями. Нечеткие множества.
2)Теоретический минимум

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

3)Дан граф. Найти сильные компоненты, базы и антибазы. Я б нарисовал, но, к сожалению, не помню как точно выглядит.

КИМ № 5
1) Операции над БО и их свойства
2) теоретический минимум:
степень множества, треугольник Паскаля и его свойства, матричный критерий, последовательность Фибоначчи и её производящая функция, конденсация графа и её свойства, полиномиальная теорема
3) практика
Дано отношение R={(x,y): f(x)=f(y)}, которое задано на [-2,4]^2, f(x)=x*x+1
доказать, что это отношение R - отношение эквивалентности
построить классы эквивалентности [0], [1], [2], [-1/2]

Билет №6

1 8ой вопрос из листочка.
2 теоретический минимум
a)свойства операций над множествами
b)перестановки с повторениями и без повторений
c)
d)теорема об отношении эквивалентности
e)метод производящей (функции?)
f)свойства бесконтурного графа
3 даны 8 букв найти количество их перестановок, если
а) нет ограничений
б) между буквами а и с 2 буквы ИЛИ 3 буквы
в) между буквами а и с НЕ 3 буквы И НЕ 2 буквы
г)на первых четырех местах могут стоять буквы (а с d f)?

7 билет
1. Понятие выборки. Комбинаторные конфигурации без повторений. Правило сложения и умножения.
2. -Определение св-в бинарных отн-й по матрице,
- композиция бинарных отн-й,
- суть задачи-раскраски,
- св-ва остовов,
- св-ва операций над мн-вами в терминах характеристич. ф-ции,
-
3. Найти СК графа,базы и антибазы.

КИМ №9
1) связность и достижимость. алгоритм пострроения сильных компонент
теоритический минимум:
а) операции над мн-вами в терминах характеристической ф-и
б)покрытие и разбиение
в)полиномиальная теорема
г)биномиальные коэффициенты и их св-ва
д)последовательность Фибоначчи и ее производящая ф-я
ж)св-ва остовного дерева

задача: ск-кими способами можно переставить буквы w,e,d,i,g,m,a,t,h так чтобы: а) последовательности букв не были хотя бы одним из слов we, dig, math; b) первые три буквы стояли по алфавиту.

КИМ №10

1. Отношение эквивалентности. Классы эквивалентности. Фактор-множества. Теорема об отношении эквивалентности. Матричный критерий.

Теор. минимум.
a) свойства отношений включения и равенства множеств
b) частичный и линейный порядок (определения, примеры)
c) теорема Вандермонда
d) свойства треугольника Паскаля (?)
e) энумератор, денумератор
f) алгоритм Краскала (изначально было "базисные циклы и базисные разрезающие множества", но она заменила. так как из списка вопросов их вычеркнули)

Задача.
Найти сильные компоненты, базы и антибазы данного графа.

Получил 5:
- решена практика
- пропущено свойство в теор. минимуме
- отсутствут вторая часть теоремы в вопросе 1

КИМ №12
1. Полиномиальная теорема. Бином Ньютона. Свойства биномиального коэффициента.

Теор. минимум:
a) свойства операций над множествами
b) композиция отношений и ее свойства
c) фактор-множество
d) свойства бинарных отношений
e) теорема о суперпозиции
f)... (забыл)

Задача:
Найти наибольший коэффициент (1 + sqrt(3))^100 (ответ был 63 (у меня) или 64, Леденева сама не сказала точно)

13 вариант
3) матрица смежности и матрица достижимости орграфа
4) фактор-множество
5) бинарные отношения

практика: найти производящую функцию для заданной последовательности. где есть просто n и его надо получить

КИМ №14
1.Конденсация графа. База и антибаза. Разложение бесконтурного графа на уровни.

Теоретический минимум:
а) степень множества
б)свойства производящих функций
в)алгоритм прима
г)полиномиальная теорема
Еще два вопроса забыл

В задаче была матрица, является отношение заданное данной матрицей отношением эквивалентности, и если да то выписать классы эквивалентности.

Ким №16
1)10 вопрос
теоритический минимум:алгоритм построения сильной компонентной, мощьность декартово произведения из n элементов, свайства суперпозиции бинарных отношений, свойства отношений в матрице, остальное не помню
Практика была неожиданной была система:1)A(из 2y по 3х)=А(из 2у по 3х-1) 2) С(из 2у по 3х)=8/9С(из 2y по 3х-1) Найти х и у (ответ: x=3 у=8)

Не выяснено: 1. Производящие функции и их свойства. 2. теорминимум. все не помню, но были композиция бинарных отношений и их свойства, треугольник паскаля и его свойства, разложение графа на уровни и что-то еще. Задача - доказать, что если АиВ включено в С, то А включено в (неВ)или С

Дата добавления: 2015-08-27