Что такое двоичная матрица

Бинарная матрица

Бинарная матрица (двоичная матрица, (0, 1)-матрица) — матрица, элементами которой являются 0 или 1.

— бинарная матрица

Примеры

Полезное

Смотреть что такое «Бинарная матрица» в других словарях:

Матрица достижимости — простого ориентированого графа бинарная матрица замыкания по транзитивности отношения (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.… … Википедия

Тринарная матрица — (троичная матрица, (0,1,2) матрица, элементами которой являются 0, 1 или 2. тринарная матрица троичной функции Вебба. Примеры В троичной логике таблицы истиности логических функций являются тринарными матрицами. См. также … Википедия

Список матриц — Структура матрицы Здесь собраны наиболее важные классы матриц, используемые в математике, науке (в целом) и прикладной науке (в частности). Под матрицей понимается прямоугольный массив чисел … Википедия

Алгоритм Флойда — Уоршелла — Алгоритм Флойда Уоршелла динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. Содержание 1 Алгоритм 1.1… … Википедия

Алгоритм Флойда — Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла… … Википедия

Перколяция — В физике и химии явлением перколяции (от лат. percōlāre, просачиваться, протекать) называется явление протекания или не протекания жидкостей через пористые материалы, электричества через смесь проводящих и непроводящих частиц и другие… … Википедия

Нейтральный элемент — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка… … Википедия

E2 (шифр) — E2 Создатель: NTT Опубликован: 1998 Размер ключа: 128 (192, 256) бит Размер блока: 128 бит Число раундов: 12 Тип: Ячейка Фейстеля … Википедия

Источник

Что такое двоичная матрица

Основные темы параграфа:

♦ таблицы типа «объект — свойство»;
♦ таблицы типа «объект — объект»;
♦ двоичные матрицы.

Таблицы типа «объект — свойство»

Еще одной распространенной формой информационной модели является прямоугольная таблица, состоящая из строк и столбцов. Использование таблиц настолько привычно, что для их понимания обычно не требуется дополнительных объяснений.

В качестве примера рассмотрим таблицу 2.1.

Таблица 2.1. Домашняя библиотека

При составлении таблицы в нее включается лишь та информация, которая интересует пользователя. Например, кроме тех сведений о книгах, которые включены в таблицу 2.1, существуют и другие: издательство, количество страниц, стоимость. Однако для составителя таблицы 2.1 было достаточно сведений, которые позволяют отличить одну книгу от другой (столбцы «Автор», «Название», «Год») и найти книгу на полках книжных стеллажей (столбец «Полка»). Предполагается, что все полки пронумерованы и, кроме того, каждой книге присвоен свой инвентарный номер (столбец «Номер»).

Таблица 2.1 — это информационная модель книжного фонда домашней библиотеки.

Таблица может отражать некоторый процесс, происходящий во времени (табл. 2.2).

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

Таблицы 2.1 и 2.2 относятся к наиболее часто используемому типу таблиц. Их будем называть таблицами типа «объект-свойство». В одной строке такой таблицы содержится информация об одном объекте (книга в библиотеке или состояние погоды в 12-00 в данный день). Столбцы — отдельные характеристики (свойства) объектов.

Таблицы типа «объект — объект»

Другим распространенным типом таблиц являются таблицы, отражающие взаимосвязи между разными объектами. Назовем их таблицами типа «объект-объект». Вот понятный каждому школьнику пример таблицы успеваемости (табл. 2.3).

Таблица 2.3. Успеваемость

Строки относятся к ученикам — это первый вид объектов; столбцы — к школьным предметам — второй вид объектов. В каждой клетке на пересечении строки и столбца — оценка, полученная данным учеником по данному предмету.

Таблица 2.4 тоже имеет тип «объект-объект». Однако, в отличие от предыдущей таблицы, в ней строки и столбцы относятся к одному и тому же виду объектов. В этой таблице содержится информация о наличии дорог между населенными пунктами с карты из § 2.

В математике прямоугольная таблица, составленная из чисел, называется матрицей. Если матрица содержит только нули и единицы, то она называется двоичной матрицей. Числовая часть таблицы 2.4 представляет собой двоичную матрицу.

Таблица 2.5 также содержит двоичную матрицу.

Таблица 2.5. Факультативы

В ней приведены сведения о посещении четырьмя учениками трех факультативов. Вам уже должно быть понятно, что единица обозначает посещение, ноль — непосещение. Из этой таблицы следует, например, что Русанов посещает геологию и танцы, Семенов — геологию и цветоводство и т. д.

В таблицах, представляющих собой двоичные матрицы, отражается качественный характер связи между объектами (есть дорога — нет дороги; посещает — не посещает и т. п.). Таблица 2.3 содержит количественные характеристики успеваемости учеников по предметам, выраженные оценками пятибалльной системы.

Мы рассмотрели только два типа таблиц: «объект-свойство» и «объект-объект». На практике используются и другие, гораздо более сложные таблицы.

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

В таблице типа «объект-свойство» одна строка содержит информацию об одном объекте. Столбцы — отдельные характеристики (свойства) объектов.

В таблице типа «объект-объект» отражается взаимосвязь между различными объектами.

Числовая прямоугольная таблица называется матрицей. Матрица, составленная из нулей и единиц, называется двоичной матрицей.

1. В чем состоит удобство табличного представления информации?
2. Приведите примеры таблиц, с которыми вам приходится иметь дело в школе и дома. Определите тип, к которому они относятся: «объект-свойство» или «объект-объект».
3. Что такое матрица? Что такое двоичная матрица?
4. Представьте в табличной форме сведения об увлечениях ваших одноклассников. Какой тип таблицы вы используете для этой цели?

Выполните следующие задания:
• определите, какое минимальное количество учителей физкультуры требуется при таком расписании;
• найдите один из вариантов расписания, при котором можно обойтись двумя учителями физкультуры;
• в школе три учителя физкультуры: Иванов, Петров, Сидоров; распределите между ними уроки в таблице так, чтобы ни у кого не было «окон» (пустых уроков);
• распределите между тремя учителями уроки так, чтобы нагрузка у всех была одинаковой.
6. В компьютерной сети узловым является сервер, с которым непосредственно связаны все остальные серверы. Дана следующая двоичная матрица. В ней С1, С2, СЗ, С4, С5 — обозначения серверов сети.

Определите, какой сервер является узловым.

И. Семакин, Л. Залогова, С. Русаков, Л. Шестакова, Информатика, 9 класс
Отослано читателями из интернет-сайтов

_{Планы уроков информатики, скачать тесты бесплатно, всё для учителя и школьника в подготовке к уроку по информатике 9 класс, домашние задания, вопросы и ответы}

Если у вас есть исправления или предложения к данному уроку, напишите нам.

Источник

Урок 12
Табличные модели

Содержание урока

Табличные модели. Таблицы типа «объект—объект»

Табличные модели
Таблицы типа «объект—объект»

Другим распространенным типом таблиц являются таблицы, отражающие взаимосвязи между разными объектами. Их называют таблицами типа «объект—объект». Вот понятный каждому школьнику пример таблицы успеваемости (табл. 2.3).

Строки относятся к ученикам — это первый вид объектов; столбцы — к школьным предметам — второй вид объектов. В каждой ячейке таблицы, на пересечении строки и столбца, — оценка, полученная данным учеником по данному предмету.

Таблица 2.4 тоже имеет тип «объект-объект».

Однако, в отличие от предыдущей таблицы, в ней строки и столбцы относятся к одному и тому же виду объектов. В этой таблице содержится информация о наличии прямых дорог между населенными пунктами, согласно карте (см. рис. 2.2).

Двоичные матрицы

В математике прямоугольная таблица, составленная из чисел, называется матрицей. Если матрица содержит только нули и единицы, то она называется двоичной матрицей. Числовая часть таблицы 2.4 представляет собой двоичную матрицу.

Таблица 2.5 также содержит двоичную матрицу.

В ней приведены сведения о посещении четырьмя учениками трех факультативов. Вам уже должно быть понятно, что единица обозначает посещение, нуль — непосещение. Из этой таблицы следует, например, что Русанов посещает геологию и танцы, Семенов — геологию и цветоводство и т. д.

В таблицах, представляющих собой двоичные матрицы, отражается качественный характер связи между объектами (есть дорога — нет дороги; посещает — не посещает и т. п.). Таблица же 2.3 содержит количественные характеристики успеваемости учеников по предметам, выраженные оценками пятибалльной системы.

Мы рассмотрели только два типа таблиц: «объект-свойство» и «объект-объект». На практике используются и другие, гораздо более сложные таблицы.

Следующая страница Табличные модели. Вопросы и задания

Источник

Бинарная матричная нейронная сеть

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

Предпосылки создания бинарной матричной нейронной сети

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

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

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

В искусственных нейронных сетях перцептронного типа все нейроны соседних слоев связаны друг с другом. А “сила” связи определяется значением коэффициентов. Связь “все-со-всеми”, это решение проблемы связей нейронов методом “грубой силы”. В этом случае, нейронная сеть может содержать только сравнительно небольшое число нейронов на промежуточных слоях для приемлемого времени обучения, например, в течение нескольких недель [2].

Прежде чем нейронная сеть станет выдавать результат, например, классифицировать изображения, она должна пройти этап обучения, то есть этап настройки. На этапе обучения как раз и определяются конфигурация взаимодействия и общая функция нейронов сети. По сути, обучить нейронную сеть означает подобрать функцию преобразования таким образом, чтобы на заданных входах она давала правильные выходы с заданным уровнем ошибки. Затем, после обучения, мы даем на вход сети произвольные данные, и надеемся, что функция нейронной сети подобрана достаточно точно и сеть станет правильно, с нашей точки зрения, классифицировать любые другие входные данные. В популярных сетях перцептронного типа структура сети задается изначально фиксированной, см. например [2], а функция находится подбором коэффициентов связей нейронов промежуточных слоев. Прежде чем переходить к описанию матрицы, заметим, что одновременную связь всех нейронов соседних слоев можно разложить в последовательные связи пар нейронов пользуясь тем что функция нейрона это линейная комбинация выходов нейронов предыдущего слоя и коэффициентов связи. То есть, по крайней мере, для сетей перцептронного типа, каждый нейрон можно представить как принимающий данные только от двух других нейронов.

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

Структура матрицы и нейрона

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

На рис.1 представлен пример бинарной матрицы. Входы и выходы этой матрицы — двоичные четырех-компонентные векторы. Входы подаются снизу, сверху получаем выходные значения. Каждая клетка матрицы это нейрон с двоичной функцией нескольких переменных f. Каждый нейрон имеет горизонтальную и вертикальную перегородки, отделяющие его от соседних нейронов и определяющие перетоки данных. Вертикальная перегородка нейрона, изображена слева от каждого нейрона, может иметь три положения: закрыто (темная полоса), открыта вправо (зеленая стрелка вправо), открыта влево (желтая стрелка влево).

Горизонтальная перегородка, изображена снизу от нейрона, может иметь два положения: закрыто «стоп» (темная полоса) или открыто вверх (зеленая стрелка). Таким образом, переток данных в матрице может быть снизу вверх и влево/вправо. Для того чтобы избежать выделения граничных разрядов данных первый и последний нейроны в каждом ряду логически зациклены, то есть, например, стрелка влево первого нейрона в ряду является входом последнего нейрона в этом же ряду, как показано на рис.1 для нейронов второго ряда.

Рис. 1. Пример бинарной матрицы из 3-х строк и 4-х двоичных входов/выходов.

Структура матрицы подчиняется правилам поэтапного построчного построения. Если данный набор строк нейронов не решает задачу, то к ним добавляются следующие, и так пока целевая функция не будет достигнута.

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

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

1. иметь возможность передачи данных без изменений;
2. уметь передавать константу (0 или 1) без входных данных;
3. не должна зависеть от последовательности применения входных данных от соседних нейронов, то есть нейрон выдает результирующее значение от всех своих входов поступивших как бы одновременно.

Один из вариантов такой функции f это сложение по модулю 2 или исключающее ИЛИ или XOR, как она часто обозначается в языках программирования.
Передача без изменения означает фактическое отсутствие нейрона и нужна только с точки зрения пропускания уровня матрицы без изменения данных.

Кроме обработки и передачи сигнала нейроны также имеют функцию памяти и ее использования или неиспользования в зависимости от функции реализуемой нейроном.
В зависимости от положения (значений) перегородок нейрона и его соседних нейронов, каждый нейрон может иметь от нуля до трех входов (снизу, справа и слева) и всегда один выход (вверх), который, однако, может быть не подключен к нейрону следующей строки, из за положения горизонтальной перегородки верхнего нейрона “стоп”.

Рис. 2. Нейрон с бинарной функцией f, ячейкой памяти Memo и полем Res.

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

Нейрон получает данные на вход, выполняет двоичную функцию нейрона f на основе входов и поля Memo и помещает результат в поле Res. Варианты использования поля Memo могут быть различны. Если выход всей матрицы зависит только от входов сети, то поле Memo является частью конфигурации сети вместе со значениями перегородок нейронов. Если же сеть должна обучаться также и на основе предыдущих значений, то есть обладать памятью, например, для задач реализации искусственной жизни, то поле Memo может принимать вновь вычисленное значение Res как показано на рис. 2 пунктирной стрелкой.

Допустим что функция нейрона f это бинарная операция XOR применяемая последовательно ко всем входным параметрам. Проверим, что она отвечает трем необходимым требованиям.

1. Передача данных без изменений обеспечивается вариантом, изображенным на Рис. 3. Здесь Memo = 0, Горизонтальная нижняя перегородка в значении “вверх”, Левая и правая перегородки в значении “стоп”.

Рис. 3. Вариант параметров нейрона, реализующий передачу входа с предыдущей строки без изменения в случае f = XOR.

2. Передача константы обеспечивается значениями горизонтальной и вертикальных перегородок “стоп”, а значение Memo — это значение передаваемой константы.

Рис. 4. Нейрон с функцией, передающей независимую бинарную константу Memo. Входные значения снизу, слева и справа не используются.

3. Требование независимости значения функции нейрона от последовательности обработки входных значений нейрона обеспечивается ассоциативностью XOR.

Число комбинаций полного перебора функций строки

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

Для варианта нейрона описанного выше в переборе функций нейрона участвуют:

1. горизонтальная перегородка с двумя положениями: стоп и вверх;
2. вертикальная перегородка нейрона с тремя положениями: стоп, влево и вправо;
3. двоичное поле Memo со значениями 0 и 1.

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

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

Для современного персонального компьютера это не очень большое число вычислений. При выборе функции нейрона c меньшим числом вариантов, например, без поля Memo, число комбинаций значительно уменьшается до . Даже такая значительно упрощенная версия функции нейрона демонстрирует уменьшение ошибки обучения в процессе оптимизации. В программных тестах с разными вариантами нейронных функций на языке C# автору удавалось получить скорость перебора в диапазоне 200-600 тысяч вариантов в секунду, что дает полный перебор вариантов функций строки матрицы примерно за 3 секунды. Однако, это не означает, что например, матрица размером 8×8 будет обучена в течении 24 секунд. Дело в том, что возможно несколько вариантов функции строки дающих одно и то же текущее минимальное значение ошибки обучения (метрики). Какая из этих, десятков, сотен или тысяч комбинаций приведет в итоге к нулевой ошибке обучения всей матрицы мы не знаем, и тогда в наихудшем случае нужно будет проверить каждую из них, что приводит к построению дерева оптимизационного поиска.

Естественным образом возникает вопрос, а какая двоичная функция нейрона f является наилучшей для обучения матрицы. Очевидно, что идеальной будет функция обладающая свойством функциональной полноты [3] для строки матрицы в заданном наборе параметров перегородок и поля Memo. В этом случае мы будем иметь большую, если не полную, гарантию нахождения матрицы с нулевой ошибкой обучения. Однако, вопрос нахождения такой функции нейрона еще требует изучения.

Построение дерева оптимизации или поиска нуля ошибки обучения матрицы

Функцию ошибки обучения матрицы будем называть метрикой. Значение метрики показывает степень отклонения выхода матрицы от ожидаемого на обучающих данных.

Пример метрики. Предположим что входы и выходы матрицы это 4-х битные числа. И мы хотим обучить матрицу умножать входные числа на . Допустим, что для обучения используется три входных значения , идеальный выход для которых будут числа .

Тогда входы обучения для матрицы будут четырех-битовые значения: , а выходы, соответственно , по одному биту на нейрон входной и выходной строк, соответственно.
Процесс обучения матрицы состоит в последовательном переборе положений перегородок нейронов и значений полей Memo в нейронах строки, которые вместе выполняют роль параметров поиска. После каждого изменения одного из этих параметров, то есть, например, смены положения горизонтальной перегородки одного из нейронов из положения «стоп» на положение «вверх» или смены значения поля Memo c 1 на 0, получаем текущую комбинацию перегородок и полей и вычисляем значение метрики.
Чтобы получить значение метрики на некоторой комбинации перегородок и полей Memo подставляем значения обучающих входов в матрицу и получаем выходы.
Например, на некоторой комбинации перегородок и полей мы получили выходные значения матрицы . Переводим их в десятичный вид .

Получаем значение метрики для текущих выходов матрицы:

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

Общий алгоритм построения дерева оптимизации матрицы.

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

Заключение

Практические эксперименты показывают что алгоритм обучения матрицы в большинстве случаев сходится. Например, в одном из тестов с функцией нейрона XOR, матрица шириной 8 битов научилась умножать на 2 числа от 1 до 6 с нулевой ошибкой обучения. Подставив на вход 7, на выходе получил 14, значит матрица научилась экстраполировать на один ход вперед, но уже на числе 8 матрица дала неправильный результат. Все обучение заняло несколько минут на домашнем персональном компьютере. Однако эксперименты с более сложными обучающими выборками требуют иных вычислительных мощностей.

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

Источник