\documentstyle[russian]{article}
\textwidth=16.5truecm
\textheight=24truecm
\topmargin=-1cm
\oddsidemargin=0in

%\pagestyle{empty}

\def\graphdescr{
   Ориентированный граф $G$, состоящий из $n$ вершин, задается 
   набором пар чисел $(i,j)$, где $1 \leq i,j \leq n$. Пара $(i,j)$
   при этом означает, что в графе $G$ имеется ребро, ведущее из 
   вершины с номером $i$ в вершину с номером $j$.\\
}

\def\polinomxy{
   Полином 
$p(x,y)=a_{nn} x^n y^n +\ldots+ a_{11}xy + a_{10}x + a_{01}y + a_{00}$ 
степени $2n$ от двух переменных задается набором троек вида: 
   $((n,n, a_{nn}), \ldots, (1,1, a_{11}), (1,0, a_{10}), 
     (0,1, a_{01}), (0,0, a_{00}))$, в котором тройка
   $(i,j, a_{ij})$ предтавляет моном вида $a_{ij} x^i y^j$, 
   причем если коэффициент $a_{ij} = 0$, то соотвествующая тройка в наборе 
   не хранится.
   Например, полином $x^{10} y^{10} + 2 x^5 y^3 - 8y - 3$ представляется 
   набором $((10,10,1),(5,3,2),(0,1,-8),(0,0,-3))$.\\
}

\def\substit{
   Подстановка $\sigma = \left( \begin{array}{llll}
                  1  &  2  & \ldots & n   \\
                 k_1 & k_2 & \ldots & k_n \end{array} \right)$
   задается набором пар вида $((1, k_1), \ldots, (n, k_n))$.\\
}

\def\largint{
   Большое десятичное целое число представляется набором $N$ цифр, 
   составляющих это число.\\
}

\def\matrixdescr{
   Матрица представляется набором своих строк. Например, матрица
   $\left( \begin{array}{lll}
                  1  &  2  & 3\\
                  3  &  1  & 0\\
                 -2  &  2  & 5
           \end{array} \right)$
   представляется списком $((1,2,3) (3,1,0)(-2,2,5))$.\\
}

\begin{document}

\Russian

\begin{center} \begin{bf}
                    Задачи к зачету по курсу\\
                    ЯЗЫКИ ПРОГРАММИРОВАНИЯ\\
                    Языки Refal и Prolog
\end{bf} \end{center}

\begin{enumerate}
\item %1
   Полином $f(x) = a_n x^n + \ldots + a_1 x + a_0$ степени $n$ задается 
   набором пар $((n, a_n), \ldots, (1, a_1), (0, a_0))$, в котором пара 
   $(i, a_i)$ предтавляет моном вида $a_i x^i$, причем если коэффициент 
   $a_i = 0$, то соотвествующая пара в наборе не хранится.
   Например, полином $x^{10} + 2 x^5 - 3$ представляется набором 
   $((10,1),(5,2),(0,-3))$.\\
   Дано два полинома: $f$ и $g$. Найти их произведение $fg$.
\item %2
   Полином степени $n$ задан набором своих корней (корни целые).\\
   Вычислить коэффициенты при степенях $x$ данного полинома. 
\item %3 т
   Полином степени $n$ задается набором коэффициентов при степенях
   $x$ длины $n+1$.\\
   Дано два полинома: $f$ степени $n$ и $g$ степени $m$
   таких, что $n > m$. 
   Реализовать алгоритм деления полиномов с остатком "столбиком", т.е.
   найти пару полиномов $p$ и $r$ таких, что
        $f = pg + r$,
   где степень полинома $r$ меньше $m$.
\item %4
   \polinomxy
   Для данных значений $x_0$ и $y_0$ вычислить $p(x_0,y_0)$.
\item %5
   \polinomxy
   Дано два полинома $p(x,y)$ и $q(x,y)$ степени $2n$ каждый.
   Вычислить коэффициенты при мономах вида $x^2 y^j$ для $0 \leq j \leq n$
   в произведении полиномов $p(x,y)q(x,y)$.
\item %6
   \substit
   Даны две подстановки, найти их произведение.
\item %7 л
   \substit
   Найти подстановку $\sigma^{-1}$, обратную данной подстановке $\sigma$.
\item %8
   \substit
   Циклом в подстановке $\sigma$ называется последовательность чисел
   $a_1, a_2, \ldots, a_m$ таких, что $\sigma(a_i) = a_{i+1}$ для всех 
   $i = 1, \ldots, m-1$ и $\sigma(a_n) = a_1$. \\
   Найти все различные циклы данной подстановки $\sigma$.
\item %9
   \largint
   Дано два больших целых десятичных числа.
   Реализовать алгоритмы сложения и вычитания "столбиком" больших чисел.
\item %10 т
   \largint
   Дано два больших целых десятичных числа.
   Реализовать алгоритм умножения больших чисел "столбиком".
\item %11 т
   \largint
   Дано два больших целых десятичных числа.
   Реализовать алгоритм деления больших чисел "столбиком".
\item %12
   Большое $d$-ичное целое число представляется набором $N$ цифр, 
   составляющих это число, таких что $0 \leq N[i] < d$.\\
   Дано большое целое $d$-ичное число $N$.
   Преобразовать его к целому десятичному числу.
\item %13 т
   Большое $d$-ичное целое число представляется набором $N$ цифр, 
   составляющих это число, таких что $0 \leq N[i] < d$.\\
   Дано основание системы счисления $d$.
   Дано десятичное число $z$.
   Преобразовать $z$ к большому целому $d$-ичному числу.
\item %14 л
   Дано натуральное число $r$. Найти все различные пары натуральных 
   чисел $x,y$ таких, что $r = x * y$.
\item %15
   Дано натуральное число $r$. Найти все различные пары натуральных 
   чисел $x,y$ таких, что $r = x^2 + y^2$.
\item %16
   Дано натуральное число $r$. Найти все его различные разбиения на 
   тройку натуральных слагаемых: $r = x + y + z$.
\item %17
   Дано натуральное число $r$. Найти все различные тройки натуральных 
   чисел $x,y,z$ таких, что $r = x * y * z$.
\item %18
   Дано натуральное число $r$. Найти все различные тройки натуральных 
   чисел $x,y,z$ таких, что $r = x^2 + y^2 + z^2$.
\item %19
   Известно, что всякое натуральное чило единственным образом 
   представимо в виде суммы четырех полных квадратов.\\
   Дано натуральное число $r$. Найти четыре целых числа $a,b,c,d$
   таких, что $r = a^2 + b^2 + c^2 + d^2$.
\item %20 л
   Дано целое число $q$. Найти все простые делители $q$.
\item %21
   Число называется совершенным, если оно равно сумме всех своих
   делителей (включая $1$, но исключая само число).\\
   Дано целое число $q$. Проверить, что $q$ совершенно.
   Найти совершенное число больше $1000$. %8128
\item %22
   Число называется счастливым, если сумма первой половины его цифр 
   равна сумме второй половины цифр.\\
   Дано целое число $q$. Проверить является ли $q$ счастливым.
   Найти 20 первых четырехзначных счастливых чисел.
\item %23 л
   Дан набор целых чисел. Выяснить какое из чисел встречается в
   наборе чаще всего.
\item %24 л
   Дано натуральное число $n$. 
   Построить $n$ первых строк треугольника Паскаля.
\item %25
   Дано натуральное число $n$. Построить множество всех слов длины $n$,
   составленных из символов '0' и '1'.
\item %26 т
   Дано натуральное число $n$. Построить множество всех слов длины $n$,
   составленных из символов '0' и '1', в которых количество нулей и
   единиц совпадает.
\item %27 т
   Даны натуральные числа $n,p,q$. Построить множество всех слов длины $n$,
   составленных из символов '0' и '1', в которых количество нулей равно
   $p$, а количество единиц равно $q$.
\item %28
   Дано слово, составленное из символов '0', '1' и '2'. Отсортировать
   символы в слове так, чтобы сначали в нем шли символы '0', затем символы
   '1', а в конце символы '2'.
\item %29 л
   Квадрат называется магическим, если суммы чисел в каждой строке,
   в каждом столбце и по двум главным диагоналям совпадают.\\
   Проверить, что данная целочисленная матрица является магическим
   квадратом.\\
   Построить магический квадрат размера $4 \times 4$, составленный из 
   попарно различных чисел.
\item %30
   \matrixdescr
   Дана целочисленная матрица. Проверить ее симметричность. 
\item %26 
   \matrixdescr
   Транспонировать данную целочисленную матрицу.
\item %27 л
   \matrixdescr
   Даны две целочисленные матрицы $A$ и $B$. Проверить, что матрица 
   $B$ может быть получена из матрицы $A$ путем перестановки строк
   последней.
\item %31 л
   Подсчитать сколько раз слово 'колокол' встречается в данном
   слове $w$.
\item %32
   Дано два набора символов. Проверить, что первый набор символов является
   подмножеством второго.
\item %33 лл
   Проверить, что образцы 'лиса' и 'сабля' одновременно содержатся 
   в данном слове $w$.
\item %34
   Дано два набора символов. Построить третий набор, составленный из
   различных символов, встречающихся хотя бы в одном из данных наборов.
\item %35
   \graphdescr
   Проверить, что данный граф $G$ является связным.
\item %36
   \graphdescr
   В данном графе $G$ найти цикл длины $3$.
\item %37
   \graphdescr
   Входной (выходной) степенью вершины графа называется количество
   ребер входящих в данную вершину (выходящих из данной вершины) графа.\\
   Вычислить максимальную входную и выходную степени вершин 
   данного графа $G$.
\item %38
   \graphdescr
   Входной (выходной) степенью вершины графа называется количество
   ребер входящих в данную вершину (выходящих из данной вершины) графа.\\
   В данном графе $G$ найти вершину, входная и выходная степени 
   которой совпадают.
\item %39
   \graphdescr
   Петлей называется такое ребро графа, которое входит в ту же вершину,
   из которой выходит.\\
   В данном графе $G$ найти все вершины, имеющие петли.
\item %40
   В игре принимают участие двое. Изначально каждому из участников
   дается по набору натуральных чисел одинакового размера. Игра состоит
   из туров. В каждом туре каждый из участников выбирает из имеющихся у 
   него на данный момент чисел минимальное. Выбранная пара чисел 
   сравнивается. При этом тот у кого выбранное число оказалось меньше
   вычеркивает его из своего набора (при равенстве вычеркиваются оба).
   Побеждает тот, у кого не останется ни одного числа.\\
   Дано два набора. Проверить обладатель какого из них побеждает в
   такой игре.
\end{enumerate}
\end{document}
