Рандомная генерация тестов

[Munin]

В теме «Онлайн учебник»
я упомянул походя проблему:

Munin в сообщении #1167734 писал(а):

Насчёт рандомных тестов... Не так-то просто сделать, например, рандомную матрицу с целыми (и небольшими!) числами, чтобы при вычислении обратной матрицы тоже получились приличные целые числа.

И внезапно офтопик получил продолжение:

VAL в сообщении #1167784 писал(а):

Я поступал так:
Генерил верхне(нижне)треугольную матрицу маленькими целыми элементами и единицами(минус единицами) по главной диагонали. А затем прибавлял к каждой строке, кроме первой (последней) первую (последнюю), умноженную на небольшой целый коэффициент.

Предлагаю в этой теме собирать подобные преподавательские рецепты и ноу-хау.

[gevaraweb]

Наподобие генерил задачу:

var a = random( 2, 5 );
var b = random( 2, 5 );
// запомним правильный ответ для проверки
answer = b; 
// выводим вопрос на экран с помощью MathJax
document.write( '\\[\\lim_{x \\to 0} \\frac{\\sin (' + b * a + 'x)} 
{ ' + a + 'x} = ? \\]');

На выходе с разными коэф.:

$\lim_{x \to 0} \frac{\sin (8 x)} { 4 x} = ? $

К правильному ответу answer добавляется или вычитается ненулевое число, и получается список ответов. При проверке выбранный сверяется на равенство с answer.

Я б показал на песочнице, но тут вроде как это считается саморекламой )

[Munin]

Это, простите, не тот уровень, для которого заводилась тема. Здесь не приходится "подгонять условия" под хороший ответ, здесь какие бы условия ни были заданы, ответ легко найти, и он не будет в среднем "плохим".

[Brukvalub]

gevaraweb в сообщении #1168060 писал(а):

На выходе с разными коэф.:

$\lim_{x \to 0} \frac{\sin (8 x)}
{ 4 x} = ? $

Это пример действий, доходчиво разъясняющий смысл высказывания "Гора родила мышь"?

[Red_Herring]

Brukvalub в сообщении #1168270 писал(а):

Это пример действий, доходчиво разъясняющий смысл высказывания "Гора родила мышь"?

Безусловно. После того как трое студентов пройдут этот тест и сверятся, все будут знать, какова задача и пойдет гулять шпора:

$$\lim_{x\to0}\frac{\sin (ax)}{bx}=\frac{a}{b}$$

[VAL]

Раз уж такая тема возникла, поностальгирую немного.
В конце 80-х годов прошлого века, когда у нас в вузе появились первые персональные компы, я разработал пакет генераторов индивидуальных заданий (На MSX-Basic, для "Ямахи"). Из-за этого пакета одну "Ямаху" с принтером не списывали после перехода на более современные компы лет 10-15.
В пакет входили генераторы индивидуальных заданий по различным темам преимущественно из алгебры и геометрии. Можно было составить примерный вариант, выбирая типы задач, и указав количество. Во многих случаях можно было настроить сложность (например, за счет изменения размерности).

Поясню основные идеи алгоритма на примере одной из задач:
Выяснить взаимное расположение двух двумерных плоскостей, заданных своими параметрическими уравнениями в 5-мерном пространстве.
Распределим вероятность возникновения возможных ответов так, чтобы возникали все возможные ответы, но более общие, все же, несколько чаще, чем те, что почти невозможны при тупом генерировании коэффициентов уравнений. Например,
1) скрещивание - 30%;
2) пересечение в точке - 20%;
3) частичная параллельность - 20%;
4) пересечение по прямой - 10%;
5) параллельность - 10%;
6) совпадение - - 10%
Сгенерируем случайное натуральное число в диапазоне 1-10. Если выпадет:
число от 1 до 3 - сконструируем случай 1;
. . .
10 - сконструируем случай 6.
Пусть, например, выпал именно последний случай.
Сгенерируем начальную точку первой плоскости с небольшими координатами и два направляющих вектора с совсем маленькими координатами (например, от -2 до 3).
Далее сгенерируем 5 линейных комбинаций двух этих векторов с маленькими коэффициентами. Один новый вектор отложим от начальной точки первой плоскости и получим начальную точку второй. Остальные две пары примем на направляющие векторы первой и второй плоскостей (разумеется, проверив, не получились ли случайно направляющие одной плоскости коллинеарными).

Остальные случаи генерируются аналогично.

[Vince Diesel]

Munin в сообщении #1167843 писал(а):

VAL в сообщении #1167784 писал(а):

Я поступал так:
Генерил верхне(нижне)треугольную матрицу маленькими целыми элементами и единицами(минус единицами) по главной диагонали. А затем прибавлял к каждой строке, кроме первой (последней) первую (последнюю), умноженную на небольшой целый коэффициент.

Для этой конкретной задачи случайной генерации вполне достаточно. Пусть все элементы матрицы из множества $\{1,-1,2,-2\}$. У меня получилось, что для порядка $n=3$ определитель, по модулю равный единице, из $10^5$ матриц имеют примерно $4000$, для $n=4$ $\vphantom{aa}$ ${\sim}1400$ и для $n=5$ $\hphantom{aa}$ ${\sim}480$. Так что для нахождения требуемой матрицы пять на пять надо в среднем около 200 попыток, что для современных компьютеров немного. Несколько вариантов контрольных составить нет проблем.

[VAL]

Vince Diesel в сообщении #1168957 писал(а):

Для этой конкретной задачи случайной генерации вполне достаточно. Пусть все элементы матрицы из множества $\{1,-1,2,-2\}$. У меня получилось, что для порядка $n=3$ определитель, по модулю равный единице, из $10^5$ матриц имеют примерно $4000$, для $n=4$ $\vphantom{aa}$ ${\sim}1400$ и для $n=5$ $\hphantom{aa}$ ${\sim}480$. Так что для нахождения требуемой матрицы пять на пять надо в среднем около 200 попыток, что для современных компьютеров немного. Несколько вариантов контрольных составить нет проблем.

Элементы из множества $\{1,-1,2,-2\}$ - это уныло
В описанном мной методе я генерировал элементы исходной матрицы в диапазоне от $-3$ до $3$, а коэффициенты, на которые умножалась ведущая строка, как раз, из Вашего множества.
При таком подходе элементы итоговой матрицы находятся в диапазоне от $-9$ до $9$. Ждать от матрицы со случайными коэффициентами из такого диапазона определителя $\pm1$ можно для второго пришествия. Тем более, что вычисление определителя требует времени $O(n^3)$.

[Vince Diesel]

VAL в сообщении #1168972 писал(а):

Элементы из множества $\{1,-1,2,-2\}$ - это уныло

Это же учебная задача. Но если надо $-$ в квадрат матрицу возвести, там и побольше 9 коэффициенты могут получиться. А то еще раз в квадрат, чтобы студентам жизнь медом не казалась

VAL в сообщении #1168972 писал(а):

Тем более, что вычисление определителя требует времени $O(n^3)$.

Интересно, какого у вас порядка учебные линейные системы? Для пятого компьютер может за секунду много определителей посчитать.

[Munin]

А какие ещё типовые задания можно дать, используя такие "хорошо обратимые" матрицы?

А то мы что-то сосредоточились на одном узком примере, только gevaraweb попытался выйти за его рамки...

Что насчёт матанализа (calculus)?

-- 14.11.2016 16:41:22 --

По поводу порядка: имхо, давать вручную обращать матрицы $n>3$ - ненужный садизм. СЛАУ ну где-то $n\leqslant 4,$ если гауссом. С ростом порядка, количество описок, которое понаделает студент, растёт слишком быстро, и обнуляет ценность всего труда. Произведение матриц - ну где-то до $m\times n\sim 2\times 5.$ (И 3, максимум 4 матрицы в цепочке.) С.в. и с.з. - до $n=3.$

[VAL]

Vince Diesel в сообщении #1168990 писал(а):

Интересно, какого у вас порядка учебные линейные системы?

В зависимости от выбранного преподавателем уровня сложности 3. 4 или 5.

-- 14 ноя 2016, 22:04 --

Munin в сообщении #1168994 писал(а):

А какие ещё типовые задания можно дать, используя такие "хорошо обратимые" матрицы?

Например, "Найти собственные векторы и собственные значения".
Я генерировал жорданову форму матрицы и строил подобную ей матрицу, умножая справа и слева на взаимно обратные целочисленные матрицы, получаемые описанными выше способом.

[ewert]

Munin в сообщении #1167843 писал(а):

Не так-то просто сделать, например, рандомную матрицу с целыми (и небольшими!) числами, чтобы при вычислении обратной матрицы тоже получились приличные целые числа.

Последний раз я генерировал подобную задачу на прошлой неделе. Речь шла о преобразовании матрицы оператора при замене базиса. Матрицы, естественно, 3 на 3, и с плюс-минус единичным определителем матрицы перехода. И поскольку так, а времени было мало, то я поступал очень тупо: абсолютно случайно выбирал элементы исходной матрицы и матрицы перехода, а потом отбраковывал всё, что не даёт единичного определителя и все варианты, в которых хоть в одной из матриц (обратного перехода, результирующей и после умножения исходной как справа, так и слева) появлялись элементы, большие девятки.

Методом научного тыка выяснилось, что разумные результаты получаются, если ограничить элементы матрицы перехода тройкой, а исходной -- пятёркой. При этом пятьдесят вариантов генерируются секунд за 3 - 5. Ну а куда быстрее-то?

[gevaraweb]

Доброго! Вот хочу, для теории игр, сгенерировать матрицу, допустим, 4 на 4, так, чтобы она обязательно имела седловую точку (лучше, наверно, !). Подскажите алгоритм, заодно обогатимся рецептом (ну а я реализую ) Подразумевается матричная игра двух игроков с нулевой суммой.

[Vince Diesel]

Взять неотрицательные (целочисленные) наборы $\{x_i\}$, $\{y_j\}$, $i,j=1,\ldots,n$, и положить $a_{ij}=x_i-y_j$. Минимакс и максимин совпадают и равны $\max x_i-\max y_j$.

[gevaraweb]

Vince Diesel, извиняюсь, но так минимальные элементы строк находятся все в одном столбце, и наоборот. Как-то нехорошо...