0
И, кстати говоря — если, вдруг, какая либо строка полностью повторяет пересекающую
, в последнем элементе, диагональ — то восстановление будет возможным только по четырём элементам. Но, это нужно проверять. У меня пока времени нет.
  • avatar
  • worker
  • 03 ноября 2015, 11:43
0
Эта таблица всёго лишь часть таблицы 8х16
То есть если продолжить эту таблицу — то 17 строка будет повторением первой строки и в итоге повторится вся таблица.
  • avatar
  • worker
  • 03 ноября 2015, 11:03
0
Эта таблица всёго лишь часть таблицы 8х16. Плюс первый неявный столбец состоящий из единичек. Исходя из этого синие ячейки восстановимы. Как и вся таблица.
И тут речь не про произвольно загаданные таблицы а определённым образом сформированные.
  • avatar
  • worker
  • 03 ноября 2015, 10:57
0
Имеется ввиду только часть строки и часть диагонали, не полные.
  • avatar
  • worker
  • 03 ноября 2015, 06:49
0
Т.е. второй столбец это всегда либо последовательность 10 либо 01.
  • avatar
  • worker
  • 03 ноября 2015, 06:48
0
Для первой таблицы просто надо знать что первый столбец полностью единичный, а второй столбец состоит из последовательности единиц и нулей. Один из элементов второго столбца восстанавливается по зеленой части, с учётом знания о совпадении строки с диагональю.
  • avatar
  • worker
  • 03 ноября 2015, 06:46
0
На прошлой неделе у меня мысли просто перескочили с одного на другое и я перепутал
всё, а дальше уже думал что по 6 элементам восстановление таки невозможно. А всё -таки возможно.
  • avatar
  • worker
  • 02 ноября 2015, 19:38
0
На самом то деле по шести ячейкам восстановление такого-же плана. Если рассуждать — то получается всего 32 шестибитных числа по которым можно восстановить соответствующие таблицы 8х8, то есть всего 32 значения. Для таблиц 16х16, если предполагать что определённая закономерность подходит к ним ко всем. То получается что во второй половине таблицы будет не больше чем 64 значения — для её «восстанавливающих» шести элементов. Но, это противоречит тому что всего есть 4096 таблиц размерностью 16х16. А «восстанавливающих» комбинаций всего 32*64 = 2048. То есть либо не во всех таблицах 16х16 соблюдается закономерность которую я увидел в двух, либо будут коллизии. Скорее всего первое.

А по шести элементам в таблицах 8х8 возможно восстановление вот так. По первой таблице:

Тут используется факт того что часть строки и часть пересекающей диагонали повторяют друг друга. Выделено красным. Зелёное — это то что известно. Привести любую другую таблицу к такому виду возможно(так чтобы пересечение было именно на четвёртой строке) — лишь бы было повторение части строки пересекающей её частью диагонали. Так как в таблицах можно циклически сдвигать элементы — потому что таблицы имеют свой «период» повторения.

Четвёртая таблица:

А тут при восстановлении надо помнить что «период» этой таблицы равен 16, то есть эта таблица всего лишь часть другой таблицы с размером 8х16.
  • avatar
  • worker
  • 02 ноября 2015, 19:25
0
И, дополню, в качестве «бреда». Сжатие было бы возможно если бы при добавлении
каждой новой восьмёрки бит к первой строке — сохранялась бы определённая закономерность, позволяющая «удалять» по два бита с каждого нового восьмибитного набора столбцов. Но, это вряд-ли возможно.
Для начала тут надо проверить, сохраняется ли закономерность, для всех возможных таблиц 8х8 (их всего 32 штуки), потом проверить для всех возможных таблиц 16х16(таких таблиц 4096) и так далее.
Ради удовлетворения своего интереса проделаю это, как будет время. Хотя и уверен что это ни к чему интересному не приведёт.
  • avatar
  • worker
  • 02 ноября 2015, 16:08
0
Спасибо за подробные объяснения.
Так то я не вёл речь о сжатии данных с помощью этих таблиц. Повторюсь — мне показалось очень интересным то что сами по себе эти таблицы можно восстановить целиком, зная только содержимое определённого набора ячеек.
ПС. И всё таки во всех четырёх таблицах восстановление только лишь по шести ячейкам возможно, в других таблицах пока не проверял. Проверил на двух таблицах 16х16 — в них «самовосстановление» возможно при знании только 12 ячеек. Правда при этом сильно падает диапазон выбираемых ячеек. Но, это возможно. И повторюсь я даже «не заикаюсь» тут о том что это как то поможет сжимать данные. Сам факт «самовосстановления» интересен. И это, скорее, к жанру математических фокусов относится, а не к какой-то серьёзной теории.

За объяснения, ещё раз, спасибо.
  • avatar
  • worker
  • 02 ноября 2015, 15:51
0
Да, ты частично прав. Нагородил я огород.(рука-лицо) С 6 битами для первых трёх таблиц восстановление невозможно.Также как и с 7 битами для четвёртой.
Но, первые три таблицы всё-же можно восстановить зафиксировав только 7 определенных ячеек(например на последнем столбце) — первый столбец известен. А четвёртую таблицу можно восстановить по 8 ячейкам.
  • avatar
  • worker
  • 31 октября 2015, 14:26
0
И снова здарова, блин :).
Ещё нужно отметить как вычисленную ячейку с позицией[5][5]. Так как она является инверсией ячейки с позицией [1][5].
  • avatar
  • worker
  • 30 октября 2015, 20:40
0
И, ещё, про период — у таблицы несколько частей имеют собственные периоды. Первые два столбца имеют период 2, первые 4 столбца имеют период 4, первые 8 столбцов имеют период 8 и так далее. Это нужно иметь ввиду при вычислении номера столбца с инверсиями «половинок».
  • avatar
  • worker
  • 30 октября 2015, 20:28
0
В общем на втором шаге должна получиться такая таблица^

Дальнейшие рассуждения такие-же, только относящиеся к седьмой строке.
  • avatar
  • worker
  • 30 октября 2015, 20:22
0
Блин, пардон, напутал я с шестой строкой. Поторопился и напутал, только не с тем что восстановление возможно. Оно возможно с шестью элементами. Только шестая строка на втором шаге не восстанавливается. Восстанавливается седьмая строка, кроме второго бита в ней.
Сейчас перепишу.
  • avatar
  • worker
  • 30 октября 2015, 20:15
0
Для первой из таблиц, нужно выделить ячейки, например, таким образом:

При восстановлении нужно помнить, что, в столбце с номером (N/2 + 1) нижние четыре элемента это инверсия верхних четырёх элементов. В столбце с номером N нижние четыре элемента повторяют верхние четыре элемента. N это период повторения. Обладая только этой информацией уже можно восстановить содержимое помеченных ячеек на следующем рисунке:

И так как период равен восьми, то, и первый столбец нам известен, весь первый столбец заполнен единичками:


Дальше нужно выяснить значение второго элемента шестой строки. Просто предполагаем одно из значений ноль или единица. И подставляем это значение в эту ячейку. Получаем строку из шести элементов. И вычисляем следующие строки по правилу m[i+1] = m[i]^(m[i]>>1), выдвигаемый бит при этом в седьмой столбец не заносим. Так вот если неправильно выбрать значение второго элемента шестой строки, то на одном из шагов получим противоречие с уже выясненными элементами таблицы. Значит туда надо подставить противоположное значение.
При вычислении следующих строк надо помнить о том что на третьем шаге происходит перемещение на первую строку таблицы.
По крайней мере на четырёх приведённых таблицах это сработало.
На четвёртой таблице нужно помнить что есть неявный первый столбец заполненный единичками.
  • avatar
  • worker
  • 30 октября 2015, 20:10
0
Сейчас проверил — для первых трёх таблиц(период 8) достаточно 6 определённым образом выбранных ячеек для полного восстановления, для четвёртой таблицы (период 16) нужно знать 7 ячеек для полного восстановления таблицы.
  • avatar
  • worker
  • 30 октября 2015, 18:54
0
Для 9 битных чисел(16 элементов в таблице) тоже сходится по способу от steel_ne.
  • avatar
  • worker
  • 30 октября 2015, 18:52
0
Но, способность к «самовосстановлению» у таких таблиц всё же интересна.
  • avatar
  • worker
  • 30 октября 2015, 16:42
0
Понятно. Я складывал обычным образом. Ты прав.
  • avatar
  • worker
  • 30 октября 2015, 16:40