\documentclass[12pt]{extreport}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}        % Кодировка входного документа;
                                    % при необходимости, вместо cp1251
                                    % можно указать cp866 (Alt-кодировка
                                    % DOS) или koi8-r.

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol}
\usepackage{indentfirst}
\usepackage{verbatim}
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning}
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}

%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\newtheorem{Remark}{Замечание}
%%\newtheorem{Def}{Определение}
\newtheorem{Claim}{Утверждение}
\newtheorem{Cor}{Следствие}
\newtheorem{Theorem}{Теорема}
\theoremstyle{definition}
\newtheorem{Example}{Пример}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}

%% \newenvironment{Example} % имя окружения
%% {\par\noindent{\bf Пример.}} % команды для \begin
%% {\hfill$\scriptstyle\qed$} % команды для \end






%\date{22 июня 2011 г.}
\let\leq\leqslant
\let\geq\geqslant
\def\MT{\mathrm{MT}}
%Обозначения ``ажуром''
\def\BB{\mathbb B}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\SS{\mathbb S}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}
\def\FF{\mathbb F}
%греческие буквы
\let\epsilon\varepsilon
\let\es\varnothing
\let\eps\varepsilon
\let\al\alpha
\let\sg\sigma
\let\ga\gamma
\let\ph\varphi
\let\om\omega
\let\ld\lambda
\let\Ld\Lambda
\let\vk\varkappa
\let\Om\Omega
\def\abstractname{}

\def\R{{\cal R}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%% Enumerations %%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\Rnum}[1]{\expandafter{\romannumeral #1\relax}}
\newcommand{\RNum}[1]{\uppercase\expandafter{\romannumeral #1\relax}}

%%%%%%%%%%%%%%%%%%%%% EOF Enumerations %%%%%%%%%%%%%%%%%%%%%

\usepackage{xparse}
\usepackage{ifthen}
\usepackage{bm} %%% bf in math mode
\usepackage{color}
%\usepackage[usenames,dvipsnames]{xcolor}

\definecolor{Gray555}{HTML}{555555}
\definecolor{Gray444}{HTML}{444444}
\definecolor{Gray333}{HTML}{333333}


\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\newcounter{prvar}

\def\beforPRskip{
	\bigskip
	%\vspace*{2ex}
}

\def\PRSUBskip{
	\medskip
}


\def\pr{\beforPRskip\noindent\stepcounter{problem}{\bf \theproblem .\;}\setcounter{subproblem}{0}}
\def\pru{\beforPRskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^\circ$\!\!.\;}\setcounter{subproblem}{0}}
\def\prstar{\beforPRskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^*$\negthickspace.}\setcounter{subproblem}{0}\;}
\def\prpfrom[#1]{\beforPRskip\noindent\stepcounter{problem}{\bf Задача \theproblem~(№#1 из задания).  }\setcounter{subproblem}{0} }
\def\prp{\beforPRskip\noindent\stepcounter{problem}{\bf Задача \theproblem .  }\setcounter{subproblem}{0} }

\def\prpvar{\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem \;$\langle${\rm\Rnum{\theprvar}}$\rangle$.}\setcounter{subproblem}{0}\;}
\def\prpv{\beforPRskip\noindent\stepcounter{prvar}{\bf Задача \theproblem \,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$.  }\setcounter{subproblem}{0} }
\def\prv{\beforPRskip\noindent\stepcounter{prvar}{\bf \theproblem\,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}.\setcounter{subproblem}{0} }

\def\prpstar{\beforPRskip\noindent\stepcounter{problem}{\bf Задача $\bf\theproblem^*$\negthickspace.  }\setcounter{subproblem}{0} }
\def\prdag{\beforPRskip\noindent\stepcounter{problem}{\bf Задача $\theproblem^{^\dagger}$\negthickspace\,.  }\setcounter{subproblem}{0} }
\def\upr{\beforPRskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem .  }\setcounter{subproblem}{0} }
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\PRSUBskip\noindent\stepcounter{subproblem}{\sf \thesubproblem .} }
\def\prsubr{\PRSUBskip\noindent\stepcounter{subproblem}{\bf \asbuk{subproblem})}\;}
\def\prsubstar{\PRSUBskip\noindent\stepcounter{subproblem}{\rm $\thesubproblem^*$\negthickspace.  } }
\def\prsubrstar{\PRSUBskip\noindent\stepcounter{subproblem}{$\text{\bf \asbuk{subproblem}}^*\mathbf{)}$}\;}

\newcommand{\bracketspace}[1]{\phantom{(}\!\!{#1}\!\!\phantom{)}}

\DeclareDocumentCommand{\Prpvar}{ O{null} O{} }{
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem
% 	\ifthenelse{\equal{#1}{null}}{  }{ {\sf $\bm\langle$\bracketspace{#1}$\bm\rangle$}}
%	~\!\!(\bracketspace{{\rm\Rnum{\theprvar}}}).  }\setcounter{subproblem}{0}
%	\;(\bracketspace{{\rm\Rnum{\theprvar}}})}\setcounter{subproblem}{0}
%
	\,{\sf $\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}}.

}
%\DeclareDocumentCommand{\Prpvar}{ O{level} O{meta} m }{\prpvar}


\DeclareDocumentCommand{\Prp}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача \theproblem
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.}

\DeclareDocumentCommand{\Pr}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf\theproblem
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.}

%\DeclareDocumentCommand{\Prp}{ O{level} O{meta} }

\DeclareDocumentCommand{\Prps}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^* $
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}

\DeclareDocumentCommand{\Prpd}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^\dagger$
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}


\def\prend{
	\bigskip
%	\bigskip
}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% EOF Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%\usepackage{erewhon}
%\usepackage{heuristica}
%\usepackage{gentium}

\usepackage[portrait, top=3cm, bottom=1.5cm, left=3cm, right=2cm]{geometry}

\usepackage{fancyhdr}
\pagestyle{fancy}
\renewcommand{\headrulewidth}{0pt}
\lhead{\fontfamily{fca}\selectfont {Основные алгоритмы 2021} }
%\lhead{ \bf  {ТРЯП. } Семинар 1 }
%\chead{\fontfamily{fca}\selectfont {Вариант 1}}
\rhead{\fontfamily{fca}\selectfont Домашнее задание 1}
%\rhead{\small 01.09.2016}
\cfoot{}

\usepackage{titlesec}
\titleformat{\section}[block]{\Large\bfseries\filcenter {\setcounter{problem}{0}}  }{}{1em}{}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Обозначения и операции %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
                                                                    
\newcommand{\divisible}{\mathop{\raisebox{-2pt}{\vdots}}}           
\let\Om\Omega


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Shen Macroses %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\w}[1]{{\hbox{\texttt{#1}}}}


\begin{document}
	


\pr Как модифицировать алгоритм Флойда-Уоршелла, чтобы он находил не только длины кратчайших путей между всеми парами вершин, но и сами пути?

\pr Как используя выходные данные алгоритма Флойда-Уоршелла проверить, что в графе есть цикл отрицательного веса?

\pr В ориентированном взвешенном графе есть ровно одно ребро ($u \to v$) с отрицательным весом. Описать эффективный алгоритм поиска кратчайшего пути между заданной парой вершин $(a,b)$ "--- вход задачи: матрица весов и вершины $a$ и $b$.


\pr В Главе 2 [ДПВ] (раздел 2.5) приведён алгоритм Штрассена для умножения матриц сложностью $O(n^{\log_2 7})$.

\prsub Объясните почему с его помощью нельзя ускорить алгоритмы поиска транзитивного замыкания (поиска вершин, достижимых из каждой вершины) и поиска кратчайших путей, основанных на быстром возведении в степень до $O(n^{\log_2 7}\log n)$?

\smallskip

\noindent\textsl{Указание: булева алгебра $\{ \lor, \land\}$ и тропическая алгебра $\{\min, +\}$ не являются кольцами.} 

\prsub Постройте алгоритм, который на основе алгоритма Штрассена находит матрицу транзитивного замыкания ($a_{ij} = 1$ тогда и только тогда, когда $j$ достижима из $i$) оптимальнее, чем за $O(n^{3}\log n)$ и оцените его сложность.

%\pr Постройте алгоритм, который находит транзитивное замыкание графа за $O(|V||E|)$.

\prend   

\pr Предложите $O(|V|+|E|)$ алгоритм, который находит центр дерева (вершину, максимальное расстояние от которой до всех остальных минимально). Докажите его корректность и оцените асимптотику.


\pr Вершинным покрытием (vertex cover) графа $G(V,E)$ называется множество его вершин $S \subseteq V$, которое содержит хотя бы один конец каждого ребра графа. Постройте линейный алгоритм, который находит минимальное (по числу вершин) вершинное покрытие для дерева (вход задачи).


\Pr[null][Шень \textbf{1.3.3}] 
Даны две последовательности $\w{x[1]}\ldots\w{x[n]}$
и~$\w{y[1]}\ldots\w{y[m]}$ целых чисел. Постройте алгоритм, который находит максимальную
длину последовательности, являющейся подпоследовательностью
обеих последовательностей. Сложность алгоритма $O(nm)$.

\prend   

\prstar Всюду далее предполагаем граф ориентированным и взвешенным. Наша задача в том, чтоб найти кратчайшие пути между всеми парами вершин. Мы уже рассмотрели алгоритм Флойда--Уоршелла, однако сейчас попробуем решить ту же задачу, используя известные алгоритмы поиска кратчайших путей от заданной вершины до всех остальных.

\prsub Если веса рёбер неотрицательны, мы можем использовать асимптотически более быстрый алгоритм Дейкстры

\prsubr какова сложность выполнения алгоритма ``запустить алгоритм Дейкстры из каждой вершины''?

Если есть отрицательные ребра мы можем воспользоваться алгоритмом Беллмана--Форда, но запуск его на каждой вершине даёт очень медленный алгоритм. Попробуем усовершенствовать алгоритм Дейкстры.

Напрямую нельзя ни прибавить ко всем рёбрам одно число, ни класть в очередь с приоритетом вершину после релаксации ребра 

\prsubr почему?

\prsub Пусть наш граф имеет не только взвешенные рёбра, но и взвешенные вершины, каждой вершине $v$ сопоставлено действительное число $c(v)$, которое мы будем называть стоимостью вершины. Пусть вес ребра $(u,v)$ это $w(u,v)$.
Зададим новую функцию весов рёбер
$$w'(u,v) = c(u) + w(u,v) - c(v)$$
Тогда при выходе из вершины мы платим $c(u)$, при входе в вершину мы получаем обратно $c(v)$.

\prsubr Доказать, что для любых двух вершин $u,v$ кратчайший путь между ними при весовой функции $w$ совпадает с кратчайшим путём при весовой функции $w'$ при любом выборе функции $c$.

\prskip 

Итак, если мы выберем функцию $c$ так, чтобы все веса $w'$ были неотрицательны (и сделаем это достаточно быстро), мы сможем использовать алгоритм Дейкстры и получить эффективный алгоритм поиска всех кратчайших путей.

Пусть вершина $s$ такова, что все вершины графа достижимы из неё. 

\prsubr Доказать, что если $c(v) = d(s,v)$, где $d(s,v)$ — кратчайшее расстояние между вершинами $s$ и $v$ в исходном графе, то $w'$ неотрицательна для всех рёбер графа.

\prskip

Что делать, если в графе нет такой вершины $s$?

\prsubr Модифицируйте исходный граф так, чтобы для некоторой известной вершины все остальные вершины были достижимы из неё.

\prskip

Осталось лишь свести все шаги вместе:

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

\prsubr Модифицируйте алгоритм так, чтобы он корректно искал все кратчайшие расстояния без ограничений на наличие циклов, а именно: если пути из $s$ в $t$ не существует, алгоритм выдает на этой паре $+\infty$, если существует путь из $s$ до некоторого цикла отрицательной длины и путь из этого цикла до $t$, алгоритм выдает на этой паре $-\infty$, иначе алгоритм выдаёт корректное значение кратчайшего расстояния.

\prstar С помощью неизвестного пока вам алгоритма быстрого преобразования Фурье можно умножать многочлены степени $n$ за $O(n \log n)$ арифметических действий. Предполагая, что вы можете использовать этот алгоритм, как подпрограмму, предложите $O(k \log k \log n)$ алгоритм вычисление $f(n)$, где $f$~"--- линейная рекуррента $k$-го порядка, заданная первыми $k$ элементами.

\end{document}
  