Документы серии Baby Croc Reading Collection подготовлены BCG для СШ №13, г.Брест E-mail:babycroc@mail.ru

Г.П. Антонюк, учитель информатики СШ №13 г. Бреста

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

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

Например, рассмотрим матрицы. Ну, чем не прямоугольные массивы? Скажите детям, что это высшая математика и как легко с ней можно разобраться. Поверьте, они сами себя начнут уважать.

Для начала ученикам можно дать определение матрицы: это прямоугольная таблица состоящая из чисел.

Это пример матрицы форматом nхm, т.е. n строк, m столбцов. Если все элементы матрицы 0 - это нулевая матрица. Пока все просто. Можно ввести понятие единичной матрицы: квадратная матрица, у которой элементы диагонали а₁₁, ..., а_nn равны 1, а остальные элементы - 0. Обозначают такую матрицу Е.

И вот теперь начинается самое интересное. Довольно просто довести до учащихся, что сумма двух матриц А и В - есть матрица С, каждый элемент которой равен сумме соответствующих элементов матриц А и В, т.е. элемент с_ij=а_ij+b_ij. Правда следует сделать оговорку, что форматы матриц должны быть одинаковы.

Теперь можно предложить учащимся решить следующую задачу: Даны две матрицы А и В размером nхm. Найти сумму С этих матриц. Задача сама по себе нетрудная и, как показывает практика, учащиеся с ней легко справляются.

Для удобства решение задачи приведено на учебном алгоритмическом языке (УАЯ), хотя его нетрудно перевести на любой другой язык программирования.

На следующем этапе можно ввести понятие произведения матриц. Правда, перед этим надо уточнить, что матрицы должны быть согласованы, т.е. количество строк первой матрицы должно равняться количеству столбцов второй. Например: матрица А имеет размер 4х3

Даны две матрицы: Аnхm и Вmхk. Элементы матрицы А принимают текущие значения а_ij, матрицы В - b_js . Элемент полученной матрицы сis вычисляется по формуле:

Другими словами, элементы строк формируются по следующему правилу: поэлементно умножаем 1-ю строку матрицы А на 1-й столбец матрицы В и складываем получившиеся произведения - это есть первый с11 элемент матрицы С

Например:

, и

Итоговая матрица С будет иметь вид:

Приведем решение задачи на УАЯ. Описываем исходные таблицы А[1:n,1:m], B[1:n,1:k]. Таблица С[1:n,1:k] есть результат. Вычисление текущего элемента таблицы С можно организовать следующим образом:

И теперь можно оформить всю задачу. Сделать это будет несложно. В качестве аргументов описываем целочисленные n, m, k, вещественные таблицы А и В, результат - вещественная таблица С.

Далее можно ввести понятие перестановки из n элементов матрицы: это любое их расположение в определенном порядке. И хотя заведомо известно, что число перестановок из n элементов равно n! можно предложить учащимся, в качестве самостоятельной задачи, рассчитать число перестановок.

Для ясности объясните, что первый элемент имеет n вариантов перестановок, второй - (n-1) вариант, третий - (п-2) и т.д.

Теперь введем понятие инверсии элементов: для двух чисел аi>аj , если i<J, аi ноаj , то говорят, что пара образует инверсию. Как продолжение темы вводится понятие четности перестановок. Перестановка называется четной, если она имеет четное число инверсий, и нечетной - если число инверсий нечетно.

Рассмотрим пример: inv(4,2,1,3,5)=3+1+0+0+0=4 - инверсия четная, т.е. число 3 имеет 3 инверсии, 2 - одну, 1 - ноль и т.д., inv(6,3,5,4,2,1)=5+2+3+2+1=13 - нечетная.

Здесь можете предложить учащимся задачу для определения четности инверсии.

Здесь же можно предложить задачу на подсчет числа инверсий в перестановке. По-другому задачу можно сформулировать примерно так: подсчитать число инверсий в линейной таблице из n элементов. Или для разнообразия предложить найти элемент, обладающий большим количеством инверсий. Например, алгоритм подсчета инверсий будет выглядеть примерно так:

В порядке ознакомления можно сказать о том, что транспозицией называется операция, меняющая местами два элемента в перестановке. Например: (4,3,1,3,5) - (4,3,1,2,5). Далее формулируем теорему о том, что всякая транспозиция меняет четность перестановки на противоположную.

И вот теперь мы подошли к рассмотрению одной из самых интересных задач линейной алгебры - вычисление определителя матрицы. Определение, которое дается в курсе линейной алгебры, звучит примерно так: Определителем n-го-порядка матрицы А называется число det А, которое равно алгебраической сумме всевозможных произведений элементов матрицы А, взятых ровно по одному из каждой строчки и каждого столбца. Знак каждого такого произведения равен (-1)s+t, где s - число инверсий, которое образуют первые индексы, а t - вторые индексы.

Т. е. здесь работают формулы вида:

s=inv(i₁, i₂, ..., i_n); t=inv(j₁,j₂,…j_n).

Ничего не изменится, если элементы упорядочить по 1 или 2 индексу:

При решении этой задачи в качестве вспомогательных алгоритмов используем алгоритм inv(n,b) для вычисления числа t и алгоритм, вычисляющий каждую такую перестановку b из индексов j.

Как уже было сказано, перестановок будет n!. Для каждой такой перестановки индексов j, вычисляется произведение.

Само решение задачи очень длинно и приводить его не имеет смысла. Для самостоятельного решения учащимся предлагать его не стоит. Однако кто-то, может быть, предложит более простое и удобное решение, чем-то, которое нашли мы. Или же, просто предложите решить задачу для матрицы формата 3х3.

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