exact-utf8_it.tex

\noindent{\Huge\scshape И}{\LARGE\scshape нформатика}\\
\rule[0.5\baselineskip]{\textwidth}{1pt}

\vspace{0\baselineskip}

\rule{0pt}{0pt}\hfill\parbox[t]{0.923\textwidth}{
{\it\small
\parskip=6pt\parindent=0pt
\noindent Дорогой друг!%\newline %\parfillskip=1fil

% Для того, чтобы принять участие в работе направления точных наук в КЛШ--$\theyear{}$,  тебе предлагается решить приведённые ниже задания. 
Для задач, в которых говорится «Напиши алгоритм или программу», решением может являться как текст программы на известном тебе языке программирования, так и максимально подробный алгоритм их решения. Приводя в качестве решения код программы, обязательно снабди его подробными комментариями. 
% Если ты отправляешь решение в тетради, компактно распечатай тексты своих программ моноширинным шрифтом (например, гарнитурой Courier) и вклей в тетрадь.
Не забывай: чем оптимальнее и красивее окажется твоё решение, тем выше оно будет оценено.
}
}
\vspace{1\baselineskip}

\subsection*{Задание 7.}
    Старина Джек решил прочитать все книги, стоящие в шкафчике на его рабочем месте. Буквально на третьей он открыл для себя ценнейшее литературное произведение современности и страсть как захотел  поделиться этим достоянием с товарищем Мэтью. Но вот беда — Джек работает смотрителем на маяке и уйти со смены нет никакой возможности, а Мэтью настолько ленив, что ни за что на свете не потащит свои старые кости дальше крыльца собственного дома. Однако пару лет назад они оба ходили на лекции по телетайпу и в совершенстве овладели стандартом $ITA2$ (международный телеграфный алфавит №$2$). У Джека есть мощный фонарь, скоро будет смеркаться, а вечером Мэтью наверняка усядется в кресло-качалку на веранде, возьмёт в руки не менее яркий фонарь и будет смотреть в сторону моря, где стоит маяк Джека, у которого в руках фонарь.
    
    
    Помоги Джеку закодировать текст в поток битов (коротких/длинных вспышек фонарика). И что самое важное — помоги Мэтью принять этот поток и расшифровать, при условии что он слабоват на глаза, да и яркий свет самого маяка иногда сбивает с толку, и с вероятностью $0,05$ Мэтью примет «$1$» за «$0$». Последний факт подразумевает, что помимо передачи самого послания, друзьям будет необходимо обмениваться некой служебной информацией для валидации передаваемого, чтобы Мэтью мог обнаружить ошибку в приёме и попросить Джека отправить часть сообщения повторно, ибо недопустимо литературные шедевры коверкать. Для упрощения будем считать, что Джек обладает орлиным зрением и все ответы Мэтью воспринимает без ошибок, а протокол передачи им обоим пришёл в голову одновременно и одинаковый.
    
    
    В качестве ответа принимается программа, читающая файл с текстом «шедевра» и выводящая на экран все этапы выполнения передачи с соблюдением вышеозначенных условий, либо проработанный алгоритм работы таковой.
    
    
    Ну и да — остановись, подумай про оверхэд. 
    
    
    P.S. Для работы программы используй следующий текст:\\ \url{http://lib.ru/RBACH/seagullengl.txt}

\subsection*{Задание 8.}
Рассмотрим достаточно длинную символьную последовательность $\mathfrak{S}$ из алфавита  $\aleph  =
\{0; 1\}$ длины $N$ (в практических приложениях $N \sim  10^{10}$). Требуется найти все повторы длины не менее $D$ и, в частности, найти наидлиннейший повтор $D^{\ast}$. Повтором считается любая подпоследовательность $\mathfrak{L}\subset \mathfrak{S}$, встречающаяся в $\mathfrak{S}$ два и более раз; при этом взаимное расположение $\mathfrak{L}$ не важно. Здесь простейший способ: последовательно перебрать все подпоследовательности, начиная с коротких и заканчивая длинными. Введем понятие \textsl{сложности алгоритма} поиска повторов. Будем называть сложностью алгоритма поиска повторов число сравнений символов, производимых для гарантированного обнаружения всех $\mathfrak{L}$.

Прямой перебор требует очень большого числа сравнений: для поиска повторов длины $l$ потребуется $\sim  N \times  l$ сравнений, что при больших $N$ и $l$ делает его весьма затратным и невыгодным.

На примере этой задачи:
\begin{list}{\asbuk{nnn})}{\usecounter{nnn}\leftmargin=6mm \labelwidth=5mm \topsep=0mm \labelsep=2mm \itemsep=0pt \parsep=0mm \itemindent=-1pt}
\item предложи свой алгоритм поиска повторов, более быстрый и экономный;
\item максимально строго и точно оцени сложность предлагаемого тобою алгоритма в терминах, введёных выше;
\item предложи тест, на котором можно было бы сравнивать разные алгоритмы и поясни, может ли такой тест быть универсальным~— то есть, не зависящим от конкретного языка программирования и
вычислительного устройства;
\item попробуй обобщить предлагаемый тобою алгоритм на (конечный) алфавит произвольной мощности.
\end{list}

%Подсказка: очевидно, что даже самый хороший алгоритм будет работать \textbf{разное} время с последовательностями разной длины. Время работы алгоритма является функцией длины $N$ последовательности. Установить вид этой функции и означает зачастую описать сложность алгоритма. Программисты склонны сравнивать сложность и трудоёмкость алгоритмов из расчёта «на один символ»; впрочем, вид функциональной зависимости числа требуемых (элементарных) операций от длины $N$ последовательности и отвечает на этот вопрос. 

\subsection*{Задание 9.}
Даны $N$ простых дробей: $a_0/b_0$, $a_1/b_1$, \ldots, $a_{n-1}/b_{n-1}$.
    
Найди такую наименьшую положительную несократимую простую дробь, что при делении на каждую из заданных, она будет давать целое число.
$1 \leq a_i \leq 10^9$,
$1 \leq b_i \leq 10^9$,
$1 \leq N \leq 50$.
Программа получает на вход число $N$. Затем $N$ раз получает на вход числа $a_i$ и $b_i$ через пробел. На экран нужно через пробел вывести числа $x$ и $y$, обозначающие соответственно числитель и знаменатель найденной дроби.
        
Построй график, отметив на нем время работы твоей программы в зависимости от $N$ в пределах от $3$ до $20$. 

% \subsection*{Задание 8.}
%     Даны $N+1$ простых дробей: $a_0/b_0$, $a_1/b_1$, \ldots, $a_n/b_n$.
%     Найди такую наименьшую положительную несократимую простую дробь, что при делении на каждую из заданных, она будет давать целое число.

%     $1 \leq a_i \leq 10^9$,
%     $1 \leq b_i \leq 10^9$,
%     $1 \leq N \leq 50$.
    
%     Программа получает на вход число $N$. Затем $N+1$ раз получает на вход числа $a_i$ и $b_i$ через пробел.
    
%     На экран нужно через пробел вывести числа $x$ и $y$, обозначающие соответственно числитель и знаменатель найденной дроби.
    
%     Оцени время работы алгоритма в зависимости от числа $N$. Построй график, отметив на нём время работы твоего алгоритма в зависимости от $N$ в пределах от $3$ до $20$.

% \subsection*{Задание 9.}
% % \aleph -> \Lambda
% % mathfrak -> заменил L, T, G на B, D, U, они более читаемы
%     Рассмотрим (достаточно длинную) символьную последовательность
%     $\mathfrak{B}$ из конечного алфавита $\Lambda$\footnote{$\Lambda$ — заглавная Лямбда} (например, $\Lambda = \{0,1\}$); пусть её длина $N$ (в практических приложениях $N\approx 10^{10}$). Стоит следующая задача: найти все повторы длины не менее $\mathfrak{D}$, в частности, найти
%     наидлиннейший повтор~$\mathfrak{U}$. Данная задача является классической задачей информатики%, теории алгоритмов и т.\,п
%     . Несмотря на это, люди изобретают всё новые алгоритмы для её решения. Простейший из них~— метод грубой силы (brute force)~— заключается в том, чтобы последовательно перебрать все подпоследовательности, начиная с коротких и заканчивая длинными. Такой алгоритм позволяет нам ввести важное понятие \textsl{сложности алгоритма}. Будем называть сложностью алгоритма поиска повторов число 
%     сравнений символов, производимых в ходе работы алгоритма.
%     % сравнений символов, которое необходимо проделать, чтобы решить задачу.
    
%     Вообще, в теории алгоритмов дают более строгие и точные определения сложности, основывающиеся на точном указании того, что можно считать в программе \textit{элементарной операцией}, но для наших целей хватит того представления, которое введено.
%     Понятно, что метод грубой силы требует очень большого числа сравнений: для поиска повторов длины~$l$ потребуется~$\sim N\times l$ сравнений, что при больших~$N$ и~$l$ делает алгоритм весьма затратным и невыгодным.

%     А теперь на примере этой задачи:\\
%     а) предложи свой алгоритм поиска повторов, более быстрый и экономный;\\
%     б) максимально строго и точно оцени сложность предлагаемого тобою алгоритма в терминах, введённых выше;\\
%     в) предложи тест, на котором можно было бы сравнивать разные алгоритмы и поясни, может ли такой тест быть универсальным~— то есть, не зависящим от конкретного языка программирования и вычислительного устройства.