Теория алгоритмов (обозначения)

[Soundelly]

Здравствуйте! Я учусь в педагогическом университете заочно и лекции нам читают в очень маленьком объеме. По дисциплине под названием "теория алгоритмов" нет методичек, а в библиотеках никаких книг не предлагают, дабы "разобрали", как говорят.
Мне нужно решить 3 задания, которые вижу впервые, и даже сослаться нечего (на лекциях молодой педагог вычитывал совсем другие темы, к сожалению).
Задания:

1) Доказать:
$(x .. y) .. z = (x .. z) .. y$ (в формуле на месте .. стоит знак, которого я не видела никогда - минус, над которым точка. есть предположение, что предполагается под ним брать значения переменных, различных по знаку. но это лишь мое предположение, и я совсем не уверена в его правоте).

2) Составить программу машин Тьюринга, вычисляющих следующие функции:

в первом примере система:

$f(a) = 0, a ... 2 (mod 4) ;1, -| a ... 2 (mod 4)$ - здесь под ... понимается знак, который пишется как три черты друг над другом. значения знака я не знаю.

второй:

$f(a)=2a+1$


у меня к вам просьба - объясните мне, пожалуйста, символику! просто из всего этого знакомым является только слово mod.

Спасибо!

[Mishgun]

На счет знака минус с точкой я не знаю. Наверняка где-то в лекциях было определение. А три черты означают тождественное равенство. В вашем случае, видимо, f(a) = 0, если a равно 3 по модулю 4 и f(a) = 1, если a не равно 3 по модулю 4.

[Xaositect]

Вот такой минус с точкой я видел в паре книг по рекурсивным функциям.
$a\mathop{\dot{-}} b = \begin{cases} a-b,&\ a\geq b\\0,&\ a<b\end{cases}$

[Xaositect]

А три черты - это традиционное обозначение для равенства по модулю
$a\equiv b(\mathrm{mod}\ n)$ означает, что $a$ и $b$ имеют одинаковые остатки при делении на $n$

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

Xaositect в сообщении #212797 писал(а):

Вот такой минус с точкой я видел в паре книг по рекурсивным функциям.
$a\mathop{\dot{-}} b = \begin{cases} a-b,&\ a\geq b\\0,&\ a<b\end{cases}$

(Оффтоп)

Вспомнил, как когда-то давно пришлось поломать голову над рисованием этого минуса с точкой в \TeX. То, что здесь предложил Xaositect, выглядит не очень красиво: точка располагается над минусом слишком высоко. Самое лучшее, что в результате удалось изобрести, выглядело так:

$$ a \mathop{\frac{\,.\,}{}} b $$

Точка, увы, всё равно слишком высоко над чертой. Однако чуть-чуть пониже :)

[RIP]

(Оффтоп)

Можно подключить пакет mnsymbol и использовать команду \dotminus.

[AGu]

(Оффтоп)

Профессор Снэйп в сообщении #215633 писал(а):

Самое лучшее, что в результате удалось изобрести, выглядело так:

$$ a \mathop{\frac{\,.\,}{}} b $$

Точка, увы, всё равно слишком высоко над чертой. Однако чуть-чуть пониже :)

$a\mathop{\overset{\boldsymbol\cdot}{\smash-\vrule width 0pt height 1pt}}b$

$a\mathop{\overset{\boldsymbol\cdot}{\smash-\vrule width 0pt height 1pt}}b$

Параметром height можно регулировать положение точки.