Кодовое пространство

[vlad_light]

Пусть A - некоторое конечное множество, которое мы называем алфавитом. Введём два пространства:
$\Omega _A'=\{a_1a_2...a_k|\forall i=\overline{1,k}:a_i\in A\}$
$\Omega _A=\{a_1a_2...a_k...|\forall i\geq 1:a_i\in A\}$
Введём операцию соеденения: $\forall \sigma ,\omega\in\Omega _A':\sigma\omega=\sigma _1\sigma _2...\sigma _n\omega _1\omega _2...\omega _m$
Сюръекция $\varphi :\Omega\to X$ называется функцией адреса, а пространство $\Omega\subset\Omega _A'\cup\Omega _A$ называется кодовым пространством. Точка $\sigma\in\Omega$ такая, что $\varphi (\sigma)=x$ называется адресом точки $x\in X$.
Это вся теория, теперь задачи.
Определить кодовое пространство и функцию адреса для каждого множества:
1) $X=[0,1]$
2) $X=\{(x,y)\in\mathbb R^2|x^2+y^2=1\}\cap\{(x,y)\in\mathbb R^2|y>0\}$
3) $X=\{(x,y)\in\mathbb R^2|x^2+y^2\leq 1\}$
4) $X=\mathbb N$
5) Числа, которые могут быть записаны в виде $x=\frac{m}{2^n}, m\in\{0,1,...,2^n-1\}, n\in\mathbb N$. Сколько адресов имеет точка $0.25$ в вашей схеме?
1) $\Omega =\Omega _{\{0,..,9\}}, \varphi (\sigma)=0.\sigma _1\sigma _2...$
2) $\Omega =\Omega _{\{0,..,9\}}\cup\Omega _{\{+,-\}}', \varphi (\sigma)=(\omega _00.\sigma _1\sigma _2...,\sqrt{1-0.\sigma _1\sigma _2...})$
3) $\Omega =\Omega _{\{0,..,9\}}\cup\Omega _{\{+,-\}}', \varphi (\sigma)=(\omega _00.\sigma _1\sigma _3...,\omega _10.\sigma _2\sigma _4...)$
4) $\Omega =\Omega _{\{0,..,9\}}, \varphi (\sigma)=1\cdot\sigma _0+10\cdot\sigma _1+...+10^n\sigma _n+...$
5) $\Omega =\Omega _{\{0,..,9\}}, \varphi (\sigma)=0.\sigma _1\sigma _2...; \varphi^{-1}(0.25)=25\overline 0$, т.е. существует всего один адрес.
Проверьте, пожалуйста. Заранее спасибо!:)

[vlad_light]

И следующее задание.
Обозначим $\varphi (\varnothing ):=[0,1]; \varphi (\sigma _1\sigma _2...\sigma _n)=[\frac{m}{2^n},\frac{m+1}{2^n}]:\bigcup\limits_{m=0}^{2^n-1} [\frac{m}{2^n},\frac{m+1}{2^n}]=[0,1],\sigma _i\in\{0,1\}$.
Такое разбиение отрезка $[0,1]$ мы получили в результате деления его на пополам на каждом шаге и каждому меньшому отрезку сопоставляли кодовое число 0 или 1. Понятно, что $\varphi (\sigma _1\sigma _2...\sigma _n)\subset\varphi (\sigma _1\sigma _2...\sigma _{n+1})$. Тогда последовательность $\varphi (\sigma _1\sigma _2...\sigma _n)\to\{x\},n\to\infty$.
Например, будем ставить 0 левым отрезкам и 1 - правым. Тогда
$\varphi (0)=[\frac{0}{2},\frac{1}{2}],\varphi (1)=[\frac{1}{2},\frac{2}{2}]$
$\varphi (00)=[\frac{0}{4},\frac{1}{4}],\varphi (01)=[\frac{1}{4},\frac{2}{4}],\varphi (10)=[\frac{2}{4},\frac{3}{4}],\varphi (11)=[\frac{3}{4},\frac{4}{4}]$
...
Задание:
1) Какие точки имеют более одного адреса?
2) Найдите адрес точки $C=1/3$ и покажите, что у неё нет других адресов.
1) Все точки вида $\frac{m}{2^n}, m\in\{0,1,...,2^n-1\}, n\in\mathbb N$ имеют по два адреса, поскольку их можно "приблизить слева и справа". Например, точка $x=1/2$ имеет адреса $0\overline 1$ и $1\overline 0$.
2) Точка C=1/3 имеет только один адрес \overline {01}. А вот как доказать, что она имеет именно этот адрес пока не могу

(Оффтоп)

Попытки доказательства:
$\frac{m}{2^n}\leq \frac{1}{3}\leq\frac{m+1}{2^n};0<\frac{2^n}{3}-m<1$
Далее $m:=[\frac{2^n}{3}]\Rightarrow 0<\frac{r}{3}<1$, где $r$ - остача от деления на 3, которая равна 1 или 2, поскольку нацело $2^n$ на 3 не делится. Для завершения доказательства, нужно показать, что $r$ будет чередоваться 0 и 1 при увелечении $n$. Вот с этим и возникли затруднения.

[vlad_light]

По поводу пункта (5): точка 0.25 имеет 2 адреса:
$\varphi (25\overline 0)=\varphi (24\overline 9)=0.25$

[Профессор Снэйп]

vlad_light в сообщении #556386 писал(а):

Определить кодовое пространство и функцию адреса для каждого множества:

То есть определить сюрьекцию...

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

[vlad_light]

Надо привести пример произвольной сюръекции. В своём третьем посте я показал, что прообраз точки 0.25 в моей схеме содержит 2 элемента из кодового пространства, тем самым показав, что моё отображение не является биекцией.
Единственное условие - это то, что наше отображение должно быть сюръективным. Других ограничений нет.
И по поводу 2-ой задачи. Как показать, что если $\frac{2^n}{3}=[\frac{2^n}{3}]+\frac{r}{3}$, то $r=(n\:\mathrm{mod }\:2) +1, \forall n\geq 2$?

[Профессор Снэйп]

(Оффтоп)

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

vlad_light в сообщении #556386 писал(а):

Введём операцию соеденения

Эту операцию принято называть не "соединение", а "конкатенация" И если уж на то пошло, то для $\sigma\omega$ можно допускать $\omega \in \Omega_A$. А $\sigma$, к сожалению, приходится всё же брать из $\Omega_A'$.

Задачи правда что скучны. Просят определить сюрьекции континуального множества на счётные и континуальные в явном виде. Да ещё и множества нарочно замысловатые выбирают. Зачем это всё?...

-- Чт апр 05, 2012 21:52:40 --

vlad_light в сообщении #556386 писал(а):

5) $\Omega =\Omega _{\{0,..,9\}}, \varphi (\sigma)=0.\sigma _1\sigma _2...; \varphi^{-1}(0.25)=25\overline 0$, т.е. существует всего один адрес.

А вот и нифига не один. Второй адрес - $0.24$ и $9$ в периоде

-- Чт апр 05, 2012 21:59:13 --

И кстати, тут можно здорово облегчить себе жизнь. Сначала построить "кодирование" отрезка $[0,1]$. Это, слава Богу, довольно естественно, как правильно заметил ТС - бесконечные десятичные дроби (можно, кстати, ещё десятичную точку внести в алфавит, а можно и не вносить ). А затем брать естественные сюрьекции $[0,1]$ на остальные множества и выписывать композицию отображений.

-- Чт апр 05, 2012 22:04:43 --

Пригляделся к третьему пункту - ваще шерсть на загривке дыбом встала. Просят выписать сюрьекцию множества ветвей конечно ветвящегося дерева на полукруг (не полуокружность)! Тут впору ТФКП вспоминать: конформно отображаем квадрат на полукруг, а затем отрезок - на квадрат, стандартным приёмом смешивая две бесконечные последовательности в одну. Впрочем, если к полярным координатам перейти, то можно и без ТФКП

-- Чт апр 05, 2012 22:14:03 --

vlad_light в сообщении #556615 писал(а):

И по поводу 2-ой задачи. Как показать, что если $\frac{2^n}{3}=[\frac{2^n}{3}]+\frac{r}{3}$, то $r=(n\:\mathrm{mod }\:2) +1, \forall n\geq 2$?

$$ \frac{2^n}{3} = z + \frac{r}{3}, $$

где $z$ - целое число, равное этой самой Вашей целой части. Умножьте равенство на $3$, перенесите $r$ в левую часть и узрите, что $2^n - r$ делится на $3$. То есть $r$ - это остаток от деления $2^n$ на $3$.

Далее обычная арифметика остатков. По модулю $3$ имеем $2 = -1$, $-1$ в чётной степени равно $1$, а в нечётной $-1$.

[vlad_light]

Спасибо, с этим разобрался. Теперь ещё одна задачка:
Дан отрезок $[A,B]$. Проведём две окружности с центрами в точках $A$ и $B$ радиуса $|[A,B]|$. Они пересекутся в двух точках (верхнюю обозначим $C$), через них проведём прямую, она разделит отрезок $[A,B]$ пополам в точке $D$. Далее проведём ещё две окружности с центрами в точках $A$ и $B$ радиуса $\frac{|[A,B]|}{2}$. Они пересекут наши предыдущее окружности в 4-ёх точках (верхние обозначим $E$ и $F$). Получим фигуру $CDEF$(обозначим её $S_\varnothing$), которая состоит из 4 дуг, а также 2 отрезка $AD$ и $DB$. Проделаем с получившимися отрезками такую же процедуру и получим ещё 2 фигуры и 4 отрезка. Фигуры обозначим $S_0$ и $S_1$ соответственно. Продолжим данную процедуру до бесконечности.
Далее определим функцию $\varphi(\sigma)=S_\sigma$.
Задачка №1. Показать, что $\varphi (\sigma\overline 0)\in S_\sigma\cap [A,B]$.
Насколько я понял, $\varphi(\sigma\overline 0)=\varphi(\sigma _1\sigma _2...\sigma _n\overline 0)=S_{\sigma _1\sigma _2...\sigma _{n-1}}\cap [A,B]\neq S_\sigma\cap [A,B]$.
Задачка №2. Пускай $X=\{f|f:S\to \{0,1\}\},S=\{S_\sigma |\sigma\in\Omega _{\{0,1\}}'\}$. Пусть $f$ красит нашу фигурку в красный или зелёный цвет(при значениях $0$ и $1$ соответственно). Нужно придумать кодовое пространство и функцию адреса для $X$. Используя функцию адреса, определить адрес некоторой точки $x\in X$, если $f(S_\varnothing )=1$.
Я придумал такое: $\varphi (\sigma)=f_\sigma (S)=f(S_\sigma )$, где $\sigma\in\Omega _{\{0,1\}}'$. Суть второй части задания я так и не понял, приведу текст на английском:

Цитата:

Let $X$ denote the set of all functions $f:S\to\{0,1\}$. Then $X$ may be used to model the set of pictures of $S$ in which some shields are coloured red and the others green. Devise an address function and code space for $X$. Using this address function, give a possible address of a point $x\in X$ represented by the picture in Figure 1.9 with $S_\varnothing$ coloured green.

http://imageshack.us/photo/my-images/193/111dk.jpg/

[Профессор Снэйп]

vlad_light в сообщении #556733 писал(а):

Они пересекутся в двух точках (верхнюю обозначим ) $C$

А если точки $A$ и $B$ находятся на одной вертикальной прямой?

-- Пт апр 06, 2012 00:25:50 --

Позвольте полюбопытствовать: это что Вы за предмет такой изучаете?

-- Пт апр 06, 2012 00:36:04 --

Правда, очень тяжёлое впечатление от задач. Решение каждой очевидно сразу, а объяснять его глубоко в лом. Идеи крайне просты, но на эту простоту наворачивается искусственная "сложность" путём нагромождения несущественных технических деталей.

Вот даже с этими окружностями, кстати... Нахрена нужны все эти замысловатые криволинейные "ромбики", когда можно было обойтись обычными квадратиками и задача бы имела ровно тот же самый смысл?

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

-- Пт апр 06, 2012 00:40:16 --

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

[vlad_light]

Начинаю изучать фракталы по книге SuperFractals, Michael Fielding Barnsley

(Оффтоп)

http://www.amazon.com/SuperFractals-Michael-Fielding-Barnsley/dp/0521844932

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

Цитата:

Ну, в такой-то формулировке, я думаю, решение очевидно.

Ну пока для меня не очень очевдно Щиток нужно красить в цвет последней циферке в коде?

(Оффтоп)

Задачки простые, я согласен. Только вот нужно научиться переводить их на человеческий язык, с этим пока через раз...А в будущем будут более сложные задачки по данной теме и мне нужно хорошо её прочувствовать, поскольку ни с чем подобным ранее не сталкивался. И по поводу книжки: Вы с ней знакомы? Может посоветуете лучше? В этой много цветных картинок и обложка красивая

Кстати, по поводу задачи 1 прокомментируйте, пожалуйста.

[Профессор Снэйп]

vlad_light в сообщении #556755 писал(а):

Начинаю изучать фракталы...

А, ну тогда ладно. Готов поверить, что фракталы именно так и надо изучать.

vlad_light в сообщении #556755 писал(а):

Скажите, функцию адреса я корректно определил или так делать нельзя?

А я чёт не могу до конца понять, что там как определяется. У Вас функция $\varphi$ задана через указание своего значения на произвольном элементе $\sigma \in \Omega'_{\{ 0,1 \}}$. Получается, что область определения $\varphi$ - это множество $\Omega'_{\{ 0,1 \}}$. А затем тут же, без всяких дополнительных пояснений, идёт вопрос о том, чему равно $\varphi(\sigma \overline{0})$. Но ведь $\sigma \overline{0}$ - это вообще не элемент $\Omega'_{\{ 0,1 \}}$! На этом моменте мозг выключается...

А вот который на английском языке вопрос задан - с ним вроде всё понятно. Для начала, чтобы не было лишних нагромождений, отождествим каждый щит $S_\sigma$ с самим $\sigma$. Теперь $X$ - это множество раскрасок пространства $\Omega'_{\{ 0,1 \}}$, из которого берутся сигмы, в два разных цвета. Само множество $\Omega'_{\{ 0,1 \}}$, очевидно, является счётным. Раскрасить счётное множество в два цвета можно континуумом способов. Теперь выкинем штрих и посмотрим на $\Omega = \Omega_{\{ 0,1 \}}$. Оно континуально. Устраиваем произвольную биекцию $\Omega$ на $X$ и дело с концом!

Ну то есть мне, как чистому математику, этого достаточно. А Вам, как будущему "прикладному фрактальщику", наверняка надо предъявить какую-нибудь сюрьекцию $\Omega$ на $X$ в явном виде. Не знаю зачем, но раз такое задание в учебнике дают, то, наверное, зачем-то это нужно. Ну, можно поступить, например, так. Занумеруем элементы $\Omega'_{\{ 0,1 \}}$ "естественным образом": $0 \mapsto \varnothing$, $1 \mapsto 0$, $2 \mapsto 1$, $3 \mapsto 00$ и т. д. Теперь для каждого $\tau = \tau_0\tau_1\tau_2\ldots \in \Omega$ покрасим в красный цвет все сигмы с такими номерами $i$, что $\tau_i = 1$; остальные сигмы покрасим в зелёный цвет. Сопоставили каждому $\tau \in \Omega$ некоторый элемент $X$ - конкретную раскраску. Это сопоставление, очевидно, является сюрьекцией. Более того, биекцией! Так что кодирующую функцию мы предъявили, а раз она биективна, то... Кстати, функция определяется довольно просто, и элемент $\Omega$, кодирующий указанную на рисунке раскраску, тоже выглядит довольно красиво. Как именно? Не буду лишать Вас удовольствия найти этот элемент самостоятельно

[vlad_light]

(Оффтоп)

Цитата:

Готов поверить, что фракталы именно так и надо изучать.

Понимаю, что Вы считаете всё это безделушками, но зато там картинки есть

$\varphi:\Omega\to X, D(\varphi)=\Omega =\Omega _{\{0,1\}}'\cup\Omega _{\{0,1\}}$. Это помогло мозгу включиться?
Пока не понятно со множеством $S$: оно содержит все щитки до некоторого $n$, т.е. $|S|=1+2+4+...+2^n=2^{n+1}-1$, следовательно множество конечно. Если это так, то его можно раскрасить в 2 цвета $2^{2^{n+1}-1}$ способами. Получается, что мы не можем так рассуждать, поскольку не знаем чем ограничено $n$?
По поводу кодовой функции.
$A:\Omega _{\{0,1\}}'\leftrightarrow S;\sigma\leftrightarrow S_\sigma$
$ B:\mathbb N\cup\{0\}\leftrightarrow\Omega _{\{0,1\}}';n=\sum\limits _{k=0}^m \sigma _k2^k\leftrightarrow \sigma _1\sigma _2...\sigma _m=\sigma $.
Тогда кодовую функцию запишем в виде:
$\varphi :\Omega\to X; \omega=\omega _1\omega _2...\omega _m...\mapsto$
$ \{f(S_0)=\omega _1,f(S_1)=\omega _2,...,f(S_\sigma)=f(ABm)=\omega _m,...\}$
Т.е. мы каждому элементу из $\Omega$ предоставили по одной конкретной раскраске всех щитков - элемент $X$. Скажите, я правильно рассуждаю?

[Профессор Снэйп]

vlad_light в сообщении #556831 писал(а):

Пока не понятно со множеством $S$: оно содержит все щитки до некоторого $n$, т.е. $|S|=1+2+4+...+2^n=2^{n+1}-1$, следовательно множество конечно.

Разве? Вы же сами написали, что $S$ - это множество всех щитов! Не "всех до какого-то $n$", а вообще всех.

-- Пт апр 06, 2012 08:44:22 --

vlad_light в сообщении #556831 писал(а):

Это помогло мозгу включиться?

Нет, не помогло. Поскольку Вы сначала определили значения $\varphi$ только на конечных двоичных последовательностях, а затем стали разговаривать о значениях $\varphi$ на бесконечных последовательностях.

[vlad_light]

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

[Профессор Снэйп]

vlad_light в сообщении #557117 писал(а):

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

Да нет, вроде то. Только почему об этом сразу нельзя было сказать?