Языки и методы программирования
Записи лекций
Борисенко В.В.
Филиал МГУ в г. Душанбе. Весенний семестр 2020-21 уч.г.
Классификация языков
1. Языки "низкого" и высокого уровня
Языки высокого уровня независимы от компьютера и ОС
Языки низкого уровня -- Ассемблер (макро-Ассемблер)
Языки высокого уровня:
FORTRAN
ALGOL -> Pascal -> Modula-2 -> Oberon
C -> C++ -> Java, C#
Unix -> Internet (1970) (WWW, http, html 1989 г.)
Microsoft NETBIOS WinNT 1992 Win95 TCP/IP
Объектно ориентированные языки
class
SmallTalk Xerox оконная система
Forte, Eiffel, ...
C++ (Б.Страуструп) 1985, 1998 Version 3,
2011 Modern C++
(C++ -- промежуточное положение между
традиционными и чисто ООЯ)
Java (начало 1990-х)
C# конфликт между Sun Microsystems vs. Microsoft
Visual Java
Java Script
.Net C#, Visual Basic, CLR C++ (Managed C++)
_gc
Функциональные языки vs. императивные языки
Императивные языки -- это то, к чему мы привыки:
FORTRAN, C, C++, Java, C#, VB, ...
Есть переменные, циклы, команды, исполняемые
во времени. Есть описания (изъявительное наклонение)
и команды (повелительное наклонение)
extern int abcd;
int n;
n = 5;
++n; // n == 6
int k = 2*n + 4;
n = 0;
int i = 0;
while (i < n) {
. . .
++i;
}
f(n); // Side effect: изменение глоб. переменной
f(n); // При втором вызове функция может выполнить
// другое действие
Функциональные языки
Нет переменных!
n = 1000
Это просто обозначение константы! Не переменная
Нет циклов (потому что нет переменных и ничего
меняться не может).
Основные объекты в функциональных языках -- это функции
и списки.
Математическая функция sin(x) не имеет никаких
посторонних эффектов
sin(1) -- это всегда одно и то же число
Функциональные языки максимально приближают
программирование к математике.
Haskell, Prolog, ...
Наша первая тема -- язык Haskell
http://mech.math.msu.su/~vvb/
vladimir_borisen@mail.ru
C_n,k = C_(n-1),k + C_(n-1),(k-1)
Списки в Haskell
list comprehension
S = { x | x <- 1, 2, ..., 20, x четное }
Операции со списками
Напишем функцию, проверяющую простоту числа
isPrime m возвращает True/False
Идея: делим на все пробные делители до квадратного корня
Пробные делители -- это список, который мы сформируем
http://mech.math.msu.su/~vvb/
Если в теме n задач, то студент с номером по журналу k выбирает задачу
с номероm m:
m == k (mod n)
m - k делится но n
Файлы с программой на Haskell имеют расширение *.hs
В интерпретаторе, чтобы загрузить файл с программами,
используется команда
:l first.hs
:load first.hs
Пара простых чисел (p, p+2) называется близнецами
(3, 5), (5, 7), (11, 13), ... (101, 103), ... (1019, 1021), ...
Задача: найти все пары простых чисел-близнецов в диапазоне [1..1000]
Решение: используем list comprehension
[ (p, p+2) | p <-[1..998], isPrime p, isPrime (p + 2) ]
notepad в Windows -- очень плохой редактор
Вместо него я советую использовать notepad++
создать на диске D: директорию
d:\users\PMI3
создать поддиректорию Haskell
d:\users\PMI3\Haskell
В этой директории создать файл first.hs
В него записать программу
==================== 8-Jan-2021 ==========================
Полусовершенные числа -- числа, которые могут быть представлены
в виде суммы подмножества своих собственных делителей
(совершенные -- сумма всех собственных делителей)
12 -- полусовершенное число
делители [1,2,3,4,6]
12 = 1 + 2 + 3 + 6
= 2 + 4 + 6
Задача о рюкзаке:
дан набор чисел s и некоторое число n.
Можно ли из некоторого подмножества этих чисел
составить сумму n?
Эта задача Np-полная: если мы ее решим за полиномиальное
время, то тогда все задачи из класса P тоже решаются
за полиномиальное время.
Класс P -- это те задачи, для которых ответ проверяется за
полиномиальное время.
Тупое решение задачи о рюкзаке:
перебрать все подмножества множества s, для каждого
подсчитать сумму его элементов.
Сколько всего подмножеств? 2^|s|
Время работы алгоритма экспоненциальное
Множество из 1000 элементов время работы t = 2^1000
Число n полусовершенное <=> задача о рюкзаке для множества всех
делителей числа n решается
положительно для рюкзака объема n
=====================================
Задача о пифагоровых тройках
(a, b, c) -- целые числа
a^2 + b^2 == c^2
(3, 4, 5)
(6, 8, 10) -- тоже пифагорова тройка
(9, 12, 15)
(k*3, k*4, k*5)
=======================================
Pattern matching
Подбор шаблона
Пример: вычисление НОД двух целых чисел
gcd a b
Для каких-то пар мы уже знаем ответ:
gcd(a, a) = a
Число 0 делится на любые ненулевые числа
d | m <=> найдется k: k*d = m
Для m = 0 и любого d возьмем k = 0
m = k*d
0 = 0*d
=> gcd(m, 0) = m
gcd(a, a) = a
gcd(a, 0) = a
gcd(m, n) = gcd(n, r), где r -- остаток от деления m на n
Утверждение: у пар (m, n) и (n, r) одинаковые множества общих делителей
Доказательство:
d | m, d | n => d | r ?
m = q*n + r, |r| < |n|
r = m - q*n, d|m, d|n => d | m - q*n
Обратно
d | n, d | r => d | m = q*n + r
-------------------
Сумма элементов пустого списка равна 0
0 + x == x для любого x
sum h : t = h + sum t
sum [3, 5, 7] = 3 + sum [5, 7]
sum [3] = 3 + sum []
x + 0 = x
0 -- нейтральный элемент для операции +
x * 1 = x
1 -- нейтральный элемент для операции *
min(x, y) -- какой нейтральный элемент?
min(+infinity, y) = y
ПЕРЕРЫВ ДО 15:49
Новая конструкция: подбор шаблона (Pattern matching)
Также конструкция where
knapsack :: (Num a, Eq a) => [a] -> a -> (Bool, [a])
knapsack [] 0 = (True, [])
knapsack [] v = (False, [])
knapsack (h:t) v
| fst tailsack1 = (True, snd tailsack1)
| fst tailsack2 = (True, h : snd tailsack2)
| otherwise = (False, [])
where tailsack1 = knapsack t v
tailsack2 = knapsack t (v - h)
Конструкция let -- in
Рассотрим на примере расширенного алгоритма Евклида
Теорема
Пусть m, n -- два целых числа m, n <- Z
Тогда d = gcd(m, n) выражается в виде
d = u*m + v*n
где u, v <- Z
Алгоритм, который по числам m, n находит числа
d = gcd(m, n), u, v, называется Расширенным алгоритмом Евклида.
Обычный алгоритм Евклида
Дано: m, n
Надо: получить d = gcd(m, n)
a = m; b = n
цикл пока b != 0
| инвариант: gcd(a, b) == gcd(m, n)
| r = a%b
| a = b; b = r
конец цикла
ответ = a
Расширенный алг. Евклида
Идея:
выполняем обычный алг. Евклида, при этом храним
выражения a и b в виде линейных комбинаций исходных чисел m, n
Инвариант:
gcd(a, b) == gcd(m, n)
a == u1*m + v1*n
b == u2*m + v2*n
(a, b) <= (b, r)
a = q*b + r => r = a - q*b
u1' = u2
v1' = v2
b' = r = a - q*b = (u1*m + v1*n) - q*(u2*m + v2*n)
= (u1 - q*u2)*m + (v1 - q*v2)*n
u2' = u1 - q*u2
v2' = v1 - q*v2
u1' = u2
v1' = v2
u2' = u1 - q*u2
v2' = v1 - q*v2
Конструкция let -- in
Это выражение виде
let
x = ...
y = ...
z = ...
in
выражение (x, y, z, ...)
f4 = let n = 2; k = 3 in n^k + 1
================= 9 Jan 2021 ================================
Функции, аргументами которых являются функции
(Higher order functions)
map
filter
foldl
foldr
Работа со списками
zip
take
span
. . .
===============
Функция map f l
Первый аргумент -- некоторая функция f от одного аргумента
Второй аргумент -- список l
map создает новый список той же длины, применяя функцию f
к каждому элементу списка l
====================
Лямбда-функция -- анонимная функция, которая используется
лишь один раз. Она определяется прямо там,
где потом используется
Пример: напечатать квадраты первых 20 натуральных чисел
map (\ x -> x^2) [1..20]
=======================
Функция filter p l
Первым ее аргументом является предикат p, т.е.
функция от одного аргумента, принимающая логическое
значение (определяет некоторый признак элемента).
Например, функция even, которая возвращает True,
если ее аргументом является четное целое число,
и False, если нечетное;
или функция odd (нечетное число)
Вторым аргументом функции filter является список l.
Результатом является список, состоящий из тех элементов
списка l, которые удовлетворяют предикату p.
===========================================================
foldl (сложить слева направо; l от слова left)
foldl f accumulator l
Первый аргумент -- функция, зависящая от двух аргументов
f accumulator currentElement -> accumulator
Второй аргумент -- начальное значение аккумулятора
Третий аргумент -- список, который просматривается слева направо
Пример: получить сумму элементов списка
foldl (+) 0 [1,2,3,4]
=====================================
foldr (сложить справа налево; r от слова right)
foldr f accumulator list
Первый аргумент -- функция, зависящая от двух аргументов
f currentElement accumulator -> accumulator
Второй аргумент -- начальное значение аккумулятора
Третий аргумент -- список, который просматривается справа налево
(от конца к началу)
Пример: инвертировать элементы списка
foldr (\ x acc -> acc ++ [x]) [] [1,2,3,4,5]
==========================================================
Типичная схема вычисления функции на списках
использует pattern matching и рекурсию
Пример: найти сумму элементов списка
mySum :: (Num a) => [a] -> a
mySum [] = 0
mySum (h:t) = h + sum t
1 + 2 + 3 + 4 + ... + n = n*(n+1)/2
1^2 + 2^2 + 3^2 + 4^2 + ... + n^2 = n*(n + 1)*(2*n + 1)/6
myMax :: (Ord a) => [a] -> a
myMax [] = error "Maximum of empty list is undefined"
myMax [x] = x
-- Плохо!
-- myMax (h:t)
-- | h > myMax t = h
-- | otherwise = myMax t
myMax (h:t)
| h > maxOfTail = h
| otherwise = maxOfTail
where maxOfTail = myMax t
========================================================
Хвостовая рекурсия (tail recursion)
Иногда ее называют рекурсией с аккумулятором
Пример на языке C++: вычисление факториала числа
ПЕРЕРЫВ ДО 11:35
===============================================
Задача: дан список, надо перенумеровать его элементы
[20, 33, 7, 45] ->
[(1, 20), (2, 33), (3, 7), (4, 45)]
Это легко сделать с помощью функции zip
zip [111, 222, 333] [20, 71, 44]
результат: [(111,20), (222,71), (333,44)]
zip [1,2,3,4,5,6,7,8,9,10] [2,3,5,7,11,13,17,19]
результат: [(1,2), (2,3), (3,5), (4,7), (5,11), (6,13), (7,17), (8,19)]
zip [1..] [2,3,5,7]
результат: [(1,2),(2,3),(3,5),(4,7)]
==================================================
Если у нас есть алгоритм, который использует цикл
while (или for, ...), то его можнол преобразовать
в алгоритм, использующий хвостовую рекурсию.
int a, b, c; double u, v; ...
while (условие) {
// переменные a, b, c, u, v...
// как-то меняются в цикле
// Набор этих переменных можно рассматривать как
// аккумулятор
(a, b, c, u, v...) = действие(
(a, b, c, u, v...),
очередной элемент исходных данных
);
}
return (a, b, c, u, v...);
===================================
То же самое при помощи хвостовой рекурсии
A tailRecursiveFunction(
(a, b, c, u, v...),
исходные данные
) {
if (исходные данные исчерпаны)
return (a, b, c, u, v...);
else
return tailRecursiveFunction(
действие(a, b, c, u, v...),
исходные данные - очередной атом данных
);
}
Пример 1: алгоритм быстрого возведения в степень.
Дано: x
n -- Целое неотрицательное число n >= 0
Надо: вычислить x^n
Применим схему построения цикла с помощью инварианта
p*y^k == x^n == const
Начальные значения:
p = 1, y = x, k = n
Условие завершения цикла: k == 0, тогда ответ в переменной p
Действие в цикле:
k четное => k = k/2, y = y*y
k нечетное => k = k-1, p = p*y
log_2 (1000000) ~ 20
2^10 = 1024 ~ 1000 = 10^3
2^10 ~ 10^3
1000000 = 10^6 = (10^3)^2 ~ (2^10)^2 = 2^20
log_2 (1000000) ~ 20
===========================
ПЕРЕРЫВ до 14:00
ПЕРЕРЫВ ЗАКОНЧИЛСЯ!!!
===============================
Разложение целого числа на множители (факторизация числа)
factor -- множитель
to factorize -- разложить на множители
factorize 100
[5,5,2,2]
factorize 1024
[2,2,2,2,2,2,2,2,2,2]
factorize 17
[17]
Наивный алгоритм: число простых < n ~ n/ln(n)
формула Чебышева
делим на все числа d, начиная с 2, до квадратного корня из n
(d -- пробный делитель, trial divisor)
делим на d пока делится;
как только число n перестало делиться на d, увеличиваем d на 1
Схема Горнера вычисления значения многочлена в точке t.
Коэффициенты многочлена заданы по убывнию степеней
p_n(x) = a0*x^n + a1*x^n-1 + ... + an
Вычислить p(t)
Идея:
p(x) = 2x^2 - 3x + 7 =
= (2*x - 3)*x + 7
p(x) = 3x^3 + 11x^2 + 7*x + 4
= ((3*x + 11)*x + 7)*x + 4
p_n+1(x) = a0*x^(n+1) + a1*x^n + ... + a_n+1 =
= p_n(x)*x + a_n+1
vladimir_borisen@mail.ru
Душанбе, ДЗ2
===================================================
11 Jan 2021
Хвостовая рекурсия. Вычисление функций с использованием
аккумулятора
Список: * * * * * * * * * h * * * * * * * * *
------------------
Обработанная часть непрочитанная часть
аккумулятор --
содержит значение
ф-ции на обработанной
части
Отщепляем один элемент
из головы необработанной
части и перевычисляем
значение аккумулятора
* * * * * * * * * h * * * * * * * * *
Конец, когда непрочитанная
часть станет пустой
Тогда аккумулятор
будет содержать
значение ф-ции на
обработанной части, которая равна всему
исходному списку
Примеры:
Вычисление суммы элементов списка
mySum :: (Num a) => [a] -> a
mySum lst = mySum' 0 lst
mySum' :: (Num a) => a -> [a] -> a
mySum' acc [] = acc
mySum' acc (h:t) = mySum' (acc + h) t
Функция индуктивная, если в качестве аккумулятора достаточно
использовать значение функции
Индуктивные функции:
1) сумма элементов последовательности;
2) произведение элементов последовательности;
3) максимум/минимум элементов последовательности;
4) значение многочлена в заданной точке, коэффициенты
идут по убыванию степеней (схема Горнера).
myProduct :: (Num a) => [a] -> a
myProduct lst = myProduct' 1 lst
myProduct' :: (Num a) => a -> [a] -> a
myProduct' acc [] = acc
myProduct' acc (h:t) = myProduct' (acc*h) t
myMax :: (Ord a) => [a] -> a
myMax [] = error "maximum of empty list"
myMax (h:t) = myMax' h t
myMax' :: (Ord a) => a -> [a] -> a
myMax' acc [] = acc
myMax' acc (h:t)
| acc >= h = myMax' acc t
| otherwise = myMax' h t
Схема Горнера
p(x) = 22*x^3 + 77*x^2 + 11*x + 33
Список коэффициентов: [22, 77, 11, 33]
Надо вычислить значение многочлена в точке x = t
p(t) = ((22*t + 77)*t + 11)*t + 33
Добавим коэффициент 44 в конец списка
[22, 77, 11, 33, 44]
pp(t) = (((22*t + 77)*t + 11)*t + 33)*t + 44
pp(t) = p(t)*t + 44
Итак, при добавлении нового коэфф. в конец списка
надо старое значение домножить на t и прибавить новый
коэффициент
polValueDescending :: (Num a) => [a] -> a -> a
polValueDescending coeffs x =
polValueDescending' 0 coeffs x
polValueDescending' :: (Num a) => a -> [a] -> a -> a
polValueDescending' acc [] x = acc
polValueDescending' acc (h:t) x =
polValueDescending' (acc*x + h) t x
Функция "Значение многочлена в точке, коэффициенты по убыванию
степеней" является индуктивной:
при добавлении нового коэффициента в конец списка ее новое
значение можно вычислить, зная только ее старое значение
и добавленный коэффициент.
Функция "Значение многочлена в точке, коэффициенты по возрастанию
степеней" уже не является индуктивной
polValueAscending :: (Num a) => [a] -> a -> a
polValueAscending coeffs x =
polValueAscending' (0, 1) coeffs x
polValueAscending' :: (Num a) => (a, a) -> [a] -> a -> a
polValueAscending' (value, xn) [] x = value
polValueAscending' (value, xn) (h:t) x =
polValueAscending' (value + h*xn, xn*x) t x
Задача 3
Вычислить коэффициенты производной многочлена,
коэффициенты задаются по возрастанию степеней.
polDerivativeAscending :: (Num a) => [a] -> [a]
polDerivativeAscending [] = []
polDerivativeAscending (h:t) =
polDerivativeAscending' ([], 1) t
polDerivativeAscending' :: (Num a, Integral n) => ([a], n) -> [a] -> [a]
polDerivativeAscending' (der, _) [] = der
polDerivativeAscending' (der, n) (h:t) =
polDerivativeAscending' (der ++ [fromIntegral n*h], n+1) t
ПЕРЕРЫВ до 15:45
polAntiDerivativeAscending :: (Fractional a) => [a] -> [a]
polAntiDerivativeAscending lst = polAntiDerivativeAscending' ([0], 1) lst
polAntiDerivativeAscending' :: (Fractional a, Integral n)=>([a], n)->[a]->[a]
polAntiDerivativeAscending' (antiDer, n) [] = antiDer
polAntiDerivativeAscending' (antiDer, n) (h:t) =
polAntiDerivativeAscending' (antiDer ++ [h/fromIntegral n], n+1) t
----------------------------------------------------------------------------
Задачи попроще
1. Найти среднее арифметическое элементов числовой последовательности
meanAriphm :: (Fractional a) => [a] -> a
meanAriphm [] = error "Mean of empty list"
meanAriphm lst =
let (s, n) = meanAriphm' (0, 0) lst
in s / fromIntegral n
meanAriphm' :: (Fractional a, Integral n) => (a, n) -> [a] -> (a, n)
meanAriphm' acc [] = acc
meanAriphm' (s, n) (h:t) = meanAriphm' (s+h, n+1) t
2. Определить число различных элементов в списке
numberOfDifferentElems :: (Eq a, Integral n) => [a] -> n
numberOfDifferentElems lst = len (numberOfDifferentElems' [] lst)
numberOfDifferentElems' :: (Eq a) => [a] -> [a] -> [a]
numberOfDifferentElems' acc [] = acc
numberOfDifferentElems' acc (h:t)
| h `elem` acc = numberOfDifferentElems' acc t
| otherwise = numberOfDifferentElems' (h:acc) t
Самостоятельная работа
1. Вычислить среднее геометрическое элементов положительной
числовой последовательности
[1,2,3,4]
meanGeom = (1*2*3*4) ** (1/4)
2. Вычислить среднее гармоническое элементов положительной
числовой последовательности
[1,2,3,4]
meanHarm = 1/s, где s есть среднее значение обратных величин
s = (1/1 + 1/2 + 1/3 + 1/4)/4
meanHarm = 4/(1/1 + 1/2 + 1/3 + 1/4)
Вы едете на автомобиле дистанцию в 100 км
Первые 50 км со скоростью 50 км/ч,
вторые 50 км со скоростью 100 км/ч.
Средняя скорость на дистанции есть среднее гармоническое
t1 = 50/v1 = 1
t2 = 50/v2 = 1/2
v = 100/(t1 + t2) = 100/1.5 = 100*2/3 = 66.666666666
meanHarm = 2/(1/50 + 1/100) = 2 / (3/100) = 200/3 = 66.6666666666
=====================================================================
12 Jan 2021
Алгоритмы Полларда факторизации чисел
(методы Монте-Карло)
Работаем в кольце вычитов по модулю m
Тупое определение:
Zm = {0, 1, 2, ..., m-1}
операции +, -, *
x + y -> (x + y)%m
x*y -> (x*y)%m
Математическое определение:
На множестве Z задаем отношение эквивалентности
x ~ y <==> m | (x - y)
Кольцо Zm есть фактор-множество Z/~
x ~ x' => x+y ~ x'+y'
y ~ y'
Какие классы в фактор-множестве Z/~ ???
{ ..., -3m, -2m, -m, 0, m, 2m, 3m, ... }
{ ..., -3m+1, -2m+1, -m+1, 1, m+1, 2m+1, 3m+1, ... }
{ ..., -3m+2, -2m+2, -m+2, 2, m+2, 2m+2, 3m+2, ... }
. . .
{ ..., -2m-1, -m-1, -1, m-1, 2m-1, 3m-1, 4m-1, ... }
Всего ровно m классов, остатки этих чисел в каждом классе
{ 0, 1, 2, ..., m-1 }
. . . . . . . . . . . . . . . . . . . . . . . > x
0 1 2 m m+1
Система остатков: в каждом классе выбирается ровно 1
представитель. Система остатков содержит ровно m элементов.
Систем остатков бесконечно много. Но популярны только две системы:
Пример для Z7
1) неотрицательная система остатков
{ 0, 1, 2, 3, 4, 5, 6 }
2) симметричная система остатков (минимальная по абс. величине)
{ -3, -2, -1, 0, 1, 2, 3 }
При нечетном m. При четном m, например, m = 6
{ -3, -2, -1, 0, 1, 2 }
-3 == 3 (mod 6)
-3 + -3 == 0
3 + 3 == 0
В Z7 элементы -4, 3, 10, 17, 73, 773 -- это одно и то же!
Это представители одного и того же класса, один и тот же
элемент фактор-множества.
"Целые числа" типа int в C/C++ -- это элементы кольца вычетов
Zm, m = 2^32
Алгоритмы факторизации чисел
Схема RSA шифрования с открытым
ключом.
Несимметричная схема:
E: Zm -> Zm Enryption
открытая (public)
процедура
D: Zm -> Zm Decryption
секретная (secret,
private) процедура
x -- исходное сообщение
y = E(x) -- закодированное сообщение
D(y) = x -- расшифровка
D(E) = 1 -- тождественное отображение
в множестве Zm
ED = 1
D(x) -- посылаю всем
E(D(X)) -- могут прочесть все
Посольку D известно только обладателю секретной процедуры,
то таким образом обладатель D удостоверяет свою личность
(электронная подпись, электронные деньги и т.п.)
Построение отображений E, D:
E: Zm -> Zm Enryption
открытая (public)
процедура
D: Zm -> Zm Decryption
секретная (secret,
private) процедура
m = p*q, где p, q -- большие простые числа
(200 десятичных цифр)
m открыто, разложение m на множители секретно
e -- любое число,
d -- обратное к e число в кольце
вычетов по модулю phi(m),
где phi(m) -- функция Эйлера
Для m = p*g
phi(m) = (p - 1)*(q - 1)
e*d = 1 (mod phi(m))
E: x -> x^e (mod m)
D: y -> y^d (mod m)
Пара (m, e) -- открытый ключ
Пара (m, d) -- секретный ключ
Для вычисления d по e надо знать функцию Эйлера,
а для этого надо знать p, q, т.е. разложить m
на множители.
Квантовый комп., алгоритм Шора факторизации
ПЕРЕРЫВ до 15:48
p = 623642843
q = 745809853 -- секретные числа (представление m = p*q секретно)
m = p*q = 465118977062332079 -- открытое число
phi(m) = (p - 1)*(q - 1) =
= 465118975692879384 -- секретное
e = 388096057 -- открытое число
d = 289684309574665705 -- секретный ключ
x = 123456789 -- исходное сообщение
y = x^e (mod m) =
= 228857286184325533 -- зашифрованное сообщение
z = y^d (mod m) = 123456789 -- расшифрованное сообщение
=========================================================
Итак, задача факторизации чисел очень важна в связи с
алгоритмами криптографии, электронной подписи,
криптовалютами и т.п.
Она интересна и просто с математической точки зрения.
Есть два простых и изящных алгоритма факторизации Полларда:
rho-алгоритм и p-1-алгоритм.
1. Рассмотрим rho-алгоритм -- основан на поиске цикла в
рекуррентной последовательности.
Надо разложить m на множители.
f: x -> x^2 + 1 (mod m) f: Zm -> Zm
Возьмем случайную начальную точку, например, x0 = 2
Рассмотрим бесконечную последовательность
x0, x1 = f(x0), x2 = f(x1), x3 = f(x2), ...
Так как |Zm| < infinity, то последоватльность циклическая
S = { x0, x1, x2, x3, x4, ... }
Теперь пусть p | m -- собственный делитель числа m
S1 = { x0' = x0 (mod p), x1' = x1 (mod p), x2' = x2 (mo p), ... }
|Zp| < |Zm|, т.к. p | m
Последовательность S1 тоже циклическая, и с большой вероятностью
ее цикл меньше, чем цикл S
xi != xj (mod m)
xi == xj (mod p) => p | (xi - xj), m не делит (xi - xj) =>
p | d = gcd (xi - xj, m)
m не делит d
=> d -- нетривиальный делитель числа m
Задача нахождения цикла в поледовательности x0, x1, x2, x3, ... (mod p)
x0 <--> x1 d = gcd(x0 - x1, m)
x1 <--> x3 d = gcd(x1 - x3, m)
x2 <--> x5 d = gcd(x2 - x5, m)
x3 <--> x7 d = gcd(x3 - x7, m)
x4 <--> x9
x5 <--> x11
x6 <--> x13
x7 <--> x15
. . .
x_i <--> x_2*i+1
Алгорит факторизация(m)
| x0 = 2
| x1 = f(x0)
| d = gcd(x0 - x1, m)
| numSteps = 0
| цикл пока d == 1 и numSteps < 10000000
| | x0 = f(x0)
| | x1 = f(f(x0))
| | d = gcd(x0 - x1, m)
| | numSteps += 1
| конец цикла
| ответ = d
конец алгоритма
==============================================
13 Jan 2021
Некоторые алгоритмы теории чисел
Zm -- кольцо вычетов по модулю m
Если p -- простое число, то
Zp является полем, т.е. всякий ненулевой элемент обратим
x != 0 (mod p) => существует y: y*x == 1 (mod p)
Теорема: группа обратимых элементов конечного поля является циклической.
Группа называется циклической, если она порождается одним элементом
(все элементы группы есть степени одного элемента a
1, a, a^2, a^3, ..., a^n = 1 (а -- поворот на угол 2*pi/n)
Группа обратимых (= ненулевых) элементов поля Zp порождается одним
элементом. Такой элемент называется примитивным корнем из 1 порядка p.
Пример: p = 97
Найдем примитивный корень:
a: a^96 == 1 (mod 97)
a^k != 1 (mod 97) при 1 < k < 96
=================================================
y^2 = a*x^3 + b*x + c Эллиптическая кривая
=================================================
(p-1)-алгоритм Полларда факторизации целых чисел
Малая теорема Ферма
Пусть p -- простое число. Пусть b -- любое целое число,
отличное от нуля по модулю p.
Тогда
b^(p-1) == 1 (mod p)
Пусть надо разложить число m но множители.
m = p1^e1 * p2^e2 * ... *pk^ek
Пусть p1-1 является гладким числом
число s является N-гладким, если оно раскладывается
в произведение небольших степеней простых чисел:
s = q1^t1 * q2^t2 * ... * ql^tl
qi^ti < N
Примеры гладких чисел:
495032064800 = 32*25*49*13*19*41*43*29 где 32, 25, 49, ..., 29 < 100
Если p | m -- простое число, p-1 является N-гладким =>
p | (b^(N!) - 1)
ПЕРЕРЫВ до 13:45
=================================
Перерыв закончился
m -- число, которое мы раскладываем на множители
Пусть p | m и p-1 -- N-гладкое число:
p-1 = t1*t2*...*tl, ti < N
Возьмем любое (случайное) число b, например, b = 2
Тогда по Малой Теореме Ферма
b^(N!) == 1 (mod p)
поскольку p-1 -- гладкое, то (p-1) | N!
N! = (p - 1)*s
b^(N!) = b^((p-1)*s) = ( b^(p-1) )^s == (1)^s (mod p) == 1
=> p | gcd (b^(N!) - 1, m)
Алгоритм на псевдокоде
x1 = b -- случайное (например, b = 2)
x2 = b^2 (mod m), d = gcd(x1 - 1, m)
Если d != 1, то нашли делитель m
Иначе, если d == 1, то продолжаем:
x3 = x2^3 (mod m) d = gcd(x3 - 1, m)
x4 = x3^4 (mod m) d = gcd(x4 - 1, m)
. . .
xN = x_N-1^N (mod m) d = gcd(x_N - 1, m)
Задача 1
Вычислить целую часть квадратного корня из целого числа неограниченной длины.
Решение методом деления пополам
Задача 2
Китайская теорема об остатках
Даны два взаимно простых числа p1, p2
и остатки r1, r2
Найти x: x == r1 (mod p1)
x == r2 (mod p2)
p1 = 5, r1 = 3
p2 = 11, r2 = 4
найти x: x == 3 (mod 5)
x == 4 (mod 11)
4, 15, 26, 37, 48, 59, ...
Ответ: x = 48
x == r1 (mod p1) => x = r1 + k*p1 для некоторого k
Надо найти k из второго уравнения
r1 + k*p1 == r2 (mod p2)
k*p1 = (r2 - r1) (mod p2)
Домножим равенство на u = p1^(-1) (mod p2) u -- обратный элемент
u = invMod p1 p2
Получаем k = (r2 - r1)*u (mod p2)
invMod x m -- u такое, что u*x == 1 (mod m)
sqrt(a)
[b , e]
b^2 <= a < e^2
c = (b + e)/2
c^2 <= a ==> [c, e]
==> [b, c]
b c e
Задача 1:
sqroot a = sqroot' 1 a a
sqroot' b e a
| e - b <= 1 = b
| b*b == a = b
| a < c*c = sqroot' b c a
| otherwise = sqroot' c e a
where c = (a + b) `div` 2
Задача 2
chineseTheorem p1 p2 r1 r2 =
let
u = invMod p1 p2
k = ((r2 - r1)*u) `mod` p2
in
r1 + k*p1
x == r1 (mod p1) => x = r1 + k*p1 для некоторого k
Надо найти k из второго уравнения
r1 + k*p1 == r2 (mod p2)
k*p1 = (r2 - r1) (mod p2)
Домножим равенство на u = p1^(-1) (mod p2) u -- обратный элемент
u = invMod p1 p2
Получаем k = (r2 - r1)*u (mod p2)
=====================================================================
14 Jan 2021
Китайская теорема об остатках
m1, m2, ..., mk
gcd(mi, mj) = 1 при i != j
Пусть m = m1*m2*...*mk
Тогда Zm =~ Zm1 x Zm2 x ... x Zmk
x = (x1, x2, ..., xk)
Операции совершаются покомпонентно
Пример: m1 = 5, m2 = 7
m = 35
Z35 ==~ Z5 + Z7
11 ~ (1, 4)
20 ~ (0, -1)
11+20 = 31 ~ (1, 3)
m = p1^e1 * p2^e2 * ... * pk^ek
Китайская теорема об остатках сводит
изучение колец вычетов по произвольному модулю
к кольцам вычетов по модулю степени простого числа
Z_105 105 = 3*5*7
Сколько квадратных корней из единицы в Z_105?
x*x == 1 (mod 105)
Сколько квадратных корней из единицы в Z_5?
Z5 = { 0, 1, 2, 3, 4 }
- -
Ответ: 2 корня 1^2 == 1, (-1)^2 == 1
Теорема Безу: уравнение степени n имеет не больше чем n корней в
любом поле
В Z_3 есть ровно 2 квадр. корня из 1
Аналогично в Z_7 есть ровно 2 квадр. корня из 1
Z_105 = Z_3 x Z_5 x Z_7
x ~ (x1, x2, x3)
x^2 ~ (x1^2, x2^2, x3^2)
Ответ: 8 корней
(1, 1, 1)
(-1, 1, 1)
(1, -1, 1)
(-1, -1, 1)
. . .
(-1, -1, -1)
Для k = 2
m1 m2: gcd(m1, m2) = 1
r1, r2
Найти x: x == r1 (mod m1),
x == r2 (mod m2)
Из первого уравнения
x = k*m1 + r1
Найдем k из второго уравнения:
k*m1 + r1 == r2 (mod m2) (*)
Поскольку числа m1, m2 взаимно простые, то m1 обратимо в
кольце вычетов по модулю m2
u = inverse(m1, m2)
u*m1 == 1 (mod m2)
Число u вычисляется с помощью расш. алг. Евклида
Домножим уравнение (*) на u:
u*(k*m1 + r1) == u*r2 (mod m2)
k*(u*m1) == u*(r2 - r1) (mod m2)
k == u*(r2 - r1) (mod m2)
--------------------------------------------
Работа с вещественными числами (тип Double)
Пример 1: найти корень функции y = f(x) на отрезке [a, b]
методом деления отрезка пополам
Дано: значения ф-ции на концах отрезка разных знаков
rootOfFunction :: (Floating a) => (a -> a) -> (a, a) -> a
---------------------------------------------------
Пример 2: вычисление y = log_a(x)
Для определенности, считаем, что a > 1
Для a < 1 log_1/a (x) = -log_a (x)
y == log_a(x) <==> a^y == x
Задано x, надо найти y
Инвариант цикла a^y * z^t = x = const
Меняются 3 величины y, z, t так,
что сохраняется инвариант
Завершение цикла a^y ~ x, тогда ответ в y
достаточно, чтобы z^t ~ 1
А для последнего достаточно
1/a <= z <= a,
|t| <= eps
Начальные условия y = 0, z = x, t = 1
Действия: z > a => z = z/a, y = y + t
z < 1/a => z = z*a, y = y - t
иначе => z = z*z, t = t/2
Пример 3. Суммирование ряда для sin(x)
sin(x) = x - x^3/3! + x^5/5! - x^7/7! + ...
===================================================
16 Jan 2021
Вычисление y = actg(x)
Разложение в ряд
arctg(y) = x - x^3/3 + x^5/5 - x^7/7 + ...
Радиус сходимости ряда R = 1
Сходится абсолютно при |x| < 1
При х = 1 сходится, но очень медленно
pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...
Для знакопеременного ряда точность вычисления суммы <= первого отброшенного
члена => для точности 1e-6 надо просуммировать ~500000 членов
При x = (-1) или |x| > 1 ряд расходится.
Тем не менее функция arctg(x) определена для любых x.
Идея та же, как и в случае sin:
сводим вычисление функции y = arctg(x) при |x| >= 1
к вычислению функции y' = arctg(z) для некоторого z: |z| < 1
y = arctg(x)
Надо найти z: y/2 = arctg(z)
y = 2*arctg(z)
tg(y) = tg(2*arctg(z))
x = tg(2*arctg(z)) = 2 tg( arctg(z) )/( 1 - tg^2(arctg(z)) ) =
---------------------------------------
Применим формулу tg(2a) = sin(2a)/cos(2a) =
2sin(a)cos(a)/(cos^2(a) - sin^2(a)) = разделим на cos^2(a)
= 2tg(a)/(1 - tg^2(a))
-------------------------------------
tg( arctg(z) ) = z
x = 2*z/(1 - z^2) Из этого уравнения выразим z
x*(1 - z^2) = 2*z где x известен, z неизвестно
x*(z^2 - 1) = -2*z
x*z^2 + 2*z - x = 0
z = (-2 +- sqrt(4 + 4x^2))/(2*x) = (sqrt(1 +- x^2) - 1)/x
Окончательно получаем формулу
y = arctg(x) =>
y/2 = arctg(z), где z = (sqrt(1 + x^2) - 1)/x
y = 2*arctg(z)
Можно показать, что для любых x выполняется неравенство
|z| < 1
Вычисление квадратного корня методом итераций Ньютона
x0 -- очередное приближение корня, в начале x0 = 1+a
f(x) = x^2 - a корень этой функции = sqrt(a)
y = f(x0) = x0^2 - a
dx = x0 - x1 = f(x0)/f'(x0) = (x0^2 - a)/(2*x0)
x1 = x0 - dx = x0 - (x0^2 - a)/(2*x0) =
= (2*x0^2 - x0^2 + a)/(2*x0) = 1/2 * (x0 + a/x0)
Условие завершения итераций: |x0 - x1| <= eps
==================================================
Модули, конструирование собственных типов
Загрузка модуля: import ModuleName
Пример: import Data.List
Фунция
find even [2,3,5,7,11,13,19]
Just 2
возвращает значение типа Maybe a,
где a -- тип элементов списка
"Maybe a" принимает 2 значения:
Just a
Nothing
Это полиморфный тип, параметризованный именем другого типа a
Аналогия -- механизм template в C++
std::map<std::string, int>
Создание собственных модулей
============================
В модуле определяются свои собственные типы данных и
функции, которые работают с ними. В модуле могут содержаться
впомогательные функции, которые не экспортируются.
Модуль имеет заголовок, в котором перечисляются типы и
функции, которые экспортируются.
Пример определения собственного типа данных
data Color = Black White Red Green Blue Yellow Magenta Cyan
Рассматриваем модуль R2Graph, в котором определены типы
вектор на плоскости R2Vector
точка R2Point
треугольник Triagle
прямая линия Line
окружность Circle
Ищем пересечение прямых прямых (p1, v1) и (p2, v2) -- это точка q
Точка q на прямой (p1, v1) =>
q = p1 + v1*t
Пусть n2 = normal(v2)
Точка q на второй прямой =>
(q - p2)*n2 = 0
Из этих двух уравнений находим t
(p1 + v1*t - p2)*n2 = 0
(p1 - p2)*n2 + t*v1*n2 = 0
t = (p2 - p1)*n2 / (v1*n2)
http://mech.math.msu.su/~vvb/
exp(x) = 1 + x + x^2/2! + x^3/3! + ...
x = n + r, |r| < 1
e^x = e^(n+r) = e^n * e^r
e^n, где n -- целое, вычисляем просто как e^n,
где e = 2.718281828459045
e^r вычисляется как сумма ряда
Задача.
Дан треугольник. Вычислить его вписанную окружность.
Главная идея -- работать с геометрическими объектами
вместо того, чтобы производить вычисления с координатами.
История: геометрия считалась искусством, алгебра -- ремеслом.
Рене Декарт: придумал метод координат, с помощью которого
геометрия сводится к алгебре.
Пойдем назад: забудем про метод координат и попытаемся
решать геометрические задачи геометрическими методами,
не опускаясь до тупого метода координат.
Для этого у нас есть объекты типа точка и вектор,
точки модно вычитать и получать векторы, к точке можно
прибавить вектор и получить новую точку, сдвинутую на вектор;
можно вычислять скалярные произведения векторов, нормаль к вектору
(или к плоскости в 3-мерном пространстве), нормализовать векторы,
находить длину вектора или расстояние между точками.
==============================================================
19 Jan 2021
Обработка текстов
Используем модуль Data.Char
isSpace c -- проверка, является ли символ с пробельным
(пробел, перевод строки, табуляция)
isAlpha c -- проверка, является ли символ с буквой (Alphabet)
isDigit c -- десятичная цифра
. . .
ord c -- Code Point (целое число) в кодировке Unicode
char codePoint -- символ с данной кодовой точкой
Цель: написать компилятор арифметических формул,
позволяющий вычислить значение любой формулы
123456
(-1*2) + (3*4 + 5)*6 = 100
(1 + 2/3)*(4 + 56) = 100
1+(2+3+4)*(5+6) = 100
Идея: преобразуем обычную запись формулы в обратную польскую запись.
Для вычисления RPN (Reverse Polish Notation) используется
стековый вычислитель.
Полская запись (прямая и обратная) были предложены
польском математиком (мат. логика) Ян Лукасиевич в начале XX века.
Он предложил две формы записи арифметических формул,
позволяющих не использовать скобки.
В обычной записи (инфиксной) знак операции указывается
между аргументами
2 + 3
(4 + 5)*6
4 + 5*6
В прямой польской записи (префиксной) знак операции указывается
перед аргументами:
+ 2 3 == 2 + 3
* + 4 5 6 == (4 + 5)*6
+ 4 * 5 6 == 4 + 5*6
Гораздо популярнее обратная польская запись: знак операции
указывается после аргументов
2 3 + == 2 + 3
4 5 + 6 * == (4 + 5)*6
4 5 6 * + == 4 + 5*6
Для вычисления обратной польской записи используется
стековый калькулятор (стековый вычислитель).
В математике
pow(2, 0.5) -- прямая польская запись, знак функции в
математике обычно указывается перед
аргументами.
(f*g)(x) = f(g(x)) композиция отображений
выполняется справа налево
Иногда в математике знак отображения записывается после
аргумента: вместо f(x) пишем (x)f
(x)(f*g) = ((x)f)g композиция отображений
выполняется слева направо.
Для вычисления RPN используется стековый вычислитель:
он имеет память, представленную стеком (LIFO:
top, push x, pop)
(1 + 2/3)*(4 + 56) = 100
Он работает следующим образом.
Читаем обратную польскую запись слева направо.
Если прочитали число, то добавляем его в стек.
Если очередной символ -- бинарная операция,
то снимаем со стека 2 числа, выполняем операция
и добавляем назад в стек результат этой операции.
| 2 | + | 5 |
| 3 | | 6 |
| 6 | +---+
+---+
(1 + 2/3)*(4 + 56) RPN:
1 2 3 / + 4 56 + *
Как меняется стек при вычислении по этой формуле:
|1| |2| |3| / |0.666| + |1.666| |4 | |56 | + |60 | * |100|
+-+ |1| |2| |1 | +-----+ |1.666| |4 | |1.666| +---+
+-+ |1| +-----+ +-----+ |1.666| +-----+
+-+ +-----+
Результат вычисления получается на вершине стека.
ПЕРЕРЫВ до 11:30
Обратная польская запись используется во многих языках
программирования для внутреннего представления программы:
Java, bytecode (файл с расширением *.class)
C#, Visual Basic, другие языки из платформы .Net Microsoft
Visual C++, MFC <--> Visual Basic
Для внутреннего представления программ в .Net
используется промежуточный язык CIL
Common Intermediate Language
Managed C++, CLR C++ _gc
(Common Language Runtime)
CIL представляет собой обратную польскую запись программы
Для исполнения CIL используется "компиляция на лету"
JIT -- Just In Time compiling.
25.4 mm = 1"
В графике единица измерения 1pt = 1/72"
Цель:
написать программу на Haskell, где мы вводим тектовую запись
формулы и программа вычисляет и печатает ее значение.
Для этого формула сначала переводится в обратную польскую запись,
затем значение обратной польской записи вычисляется с помощью
стекового вычислителя.
Часть 1. Перевести текст формулы в обратную польскую запись --
это делается парсером (~ компилятор).
Часть 2. Стековый вычислитель: на вход подается обратная польская
запись, на выходе вычисляется ее значение.
Компилятор работает в 2 шага:
1) текст (поток символов) преобразуется в поток лексем.
Лексема -- это одно слово текста. В нашем случае лексемы --
это
-- число,
-- знаки операций +, -, *, /, ^
-- круглые скобки (, )
-- имена функций
sin(10.3)^2 + cos(10.3)^2 -> переводим в списко лексем
(Name, "sin", 0.0)
(LPar, "(", 0.0)
(Number, "10.3", 10.3)
(RPar, ")", 0.0)
(Pow, "^", 0.0)
(Number, "2", 2.0)
(Plus, "+", 0.0)
...
2) поток лексем, который записывает исходную формулу,
преобразуется в поток лексем, представляющий обратную
польскую запись.
Программа, выполняющая шаг 1) в части 1, называется сканером
или лексическим анализатором.
Программа, выполняющая шаг 2) в части 1, называется парсером
(от слова to parse -- разбирать) или синтаксическим анализатором.
Используем функции для работа со списками:
самая важная функция для нас -- это функция span
span предикат список
Функция span разбивает список на 2 части:
начало списка, состоящее из его элементов,
удовлетворяющих предикату, из оставшейся части списка
Рассмотрим простую задачу: разбить текст на слова.
Функции show и read
===================
show преобразует объект в текст, который его представляет
read делает обратное действие: по тексту создает объект
show pi
"3.141592653589793"
x = read "3.141592653589793"::Double
ПЕРЕРЫВ до 14:00
lst: [1, 2, 3]
head lst -> 1 -> 2 -> 3 -> null
^
|
head n -> 200
n = 200:lst
n: [200, 1, 2, 3]
Мораль: опрерация : добавления элемента в начало списка
на порядок более эффективная, чем операция ++
добавления второго списка в конец первого списка.
Мы реализовали сканнер: текст превращает в список лексем.
Теперь надо реализовать парсер: поток лексем превратить
в обратную польскую запись, тоже состоящую из лексем.
Методы построения парсеров -- это целая большая теория,
связанная с теорий формальных языков и грамматик.
Все алгоритмы разбора делятся на 2 класса:
1) рекурсивный, или нисходящий разбор;
2) восходящий разбор, или разбор с помощью
конечного автомата со стеком.
+---------
| AbcDAcB <-- abcsacaceva
+---------
сдвиг
+---------
| AbcDAcBa <-- bcsacaceva
+---------
свертка по правилу E -> AcBa
+---------
| AbcDE <-- bcsacaceva
+---------
Алгоритм Дийкстры преобразования формулы к ее обратной польской записи
"Сортировочная станция" Shunting Yard
2 + 3
2, 3, +
(1 + 2/3)*(4 + 56)
1, 2, 3, /, 4, 56, +, *
2 + 3
2, 3, +
2 + 3 * 5 +, * операции запоминаются в стеке
2, 3, 5, *, +
Моделью стека является запасной путь, на который мы составляем вагоны
2 * 3 + 5 Стек: *
2, 3, *, 5, + Стек: +
Трактовка скобок:
Открывающая скобка просто добавляется в стек оперций и скобок
Закрывающая скобка выкидывает из стека все операции вплоть
до открывающей скобки и затем взаимно уничтожается с открывающей
скобкой.
Пример:
( 1 + 2 / 3 ) * ( 4 + 56 )
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 Стек: пустой
Формула: пустая
1 Стек: (
Формула: 1
2 Стек: (
Формула: 1
3 Стек: + (
Формула: 1
4 Стек: + (
Формула: 1, 2
5 Стек: / (
Формула: 1, 2, +
6 Стек: / (
Формула: 1, 2, +, 3
7 Стек: пустой
Формула: 1, 2, +, 3, /
8 Стек: *
Формула: 1, 2, +, 3, /
9 Стек: ( *
Формула: 1, 2, +, 3, /
10 Стек: ( *
Формула: 1, 2, +, 3, /, 4
11 Стек: + ( *
Формула: 1, 2, +, 3, /, 4
12 Стек: + ( *
Формула: 1, 2, +, 3, /, 4, 56
13 Стек: *
Формула: 1, 2, +, 3, /, 4, 56, +
14 Стек: пустой
Формула: 1, 2, +, 3, /, 4, 56, +, *
Пример:
((2 + 3) - (4 + 5)) * 6
*
2, 3, +, 4, 5, +, -, 6, *
2 - 3 + 5
2, 3, -, 5, +
============================================================
22 Jan 2021
Проект "Компилятор формул"
Формула включает знаки арифметических операций
+, -, *, /, %, ^, (, ),
sin, cos, exp, sqrt, ... -- функции от 1 аргумента
Одна из задач -- реализовать функции от нескольких
аргументов
atan2(y, x), powmod(a, n, m), loga(a, x), ...
Два варианта компилятора формул:
1) простой вариант -- вообще без функций,
2) со стандартными функциями от одного аргумента.
Компилятор работает в 3 этапа:
1) сканер -- преобразует входной текст, т.е. список символов,
в список лексем (тип Token{ Lexeme, String, Double } );
2) парсер -- преобразует исходный список лексем, представляющий
формулу, в список лексем, представляющий обратную польскую
запись (RPN) тоё же самоё формулы;
3) интерпретатор, который вычисляет значение формулы,
представленной как обратная польская запись исходной формулы
(список лексем).
Реализация сканера -- основана на функции spanToken,
которая выделяет первую лексему из текстовой строки
spanToken "25.3 - 17.8"
(Token {lexeme = Number, text = "25.3", value = 25.3}," - 17.8")
Название span используется потому, что в Haskell есть функция
span, которая из списка выделяет его начало, состоящее из элементов,
удовлетворяющих некоторому условию (предикату). Мы постоянно
используем эту стандартную функцию при реализации компилятора формул.
================================================================
Реализация парсера, преобразующего поток лексем, представляющий
формулу в обычной (инфиксной) записи в обратную польскую запись,
основана на алгоритме Дийкстры "Сортировочная станция"
Shunting Yard.
В этом алгоритме используются 2 списка
1) выходная формула -- это список лексем, представляющий
обратную польскую запись. Список наращивается с конца;
2) стек операций и скобок -- это список лексем, который
наращивается с начала (по дисциплине работы стека).
Удобно представлять стек операций, развернутый задом наперед,
т.е. начало списка (вершина стека) изобращается в правом конце
текста.
+-------
Стек | ( + * <- \
+------- \ Стрелка
<<< 2 + 3*5 Входная формула
Выходная +----------- /
формула |3 4 / <- /
+-----------
читаем исходную формулу слева направо,
1) если очередная лексема -- это число, то
записываем ее в конец выходной формулы;
2) если очередная лексема -- это знак операции,
то она записывается в стек операций (в голову стека);
3) при этом перед добавлением операции в стек из стека
выкидываются все те операции, которые можно выполнить до
операции, которая добавляется в стек: это либо операции
с более высоки приоритетом, либо операция с тем же
приоритетом лево-ассоциативная (a - b - c, операция
минус выполняется слева направо, "a b - c -";
a^b^c операция возведения в степень выполняется
справа налево, "a b c ^ ^");
"выкидывается из стека" означает "записывается в
конец выходной формулы";
4) левая (открывающая) скобка всегда просто добавляется
в стек;
5) правая (закрывающая) скобка выкидывает из стека
все операции вплоть до первой открывающей скобки,
после чего пара скобок взаимно уничтожаются.
6) в конце, когда заканчивается входная формула,
все оперции из стека операций выкидываются в выходную
формулу.
Пример:
(2 - 3*5 + 7)/(18 - 7)
Cтек Empty
Выходная формула Empty
Оставшаяся часть входной формулы (2 - 3*5 + 7)/(18 - 7)
Cтек (
Выходная формула Empty
Оставшаяся часть входной формулы 2 - 3*5 + 7)/(18 - 7)
Cтек (
Выходная формула 2
Оставшаяся часть входной формулы - 3*5 + 7)/(18 - 7)
Cтек ( -
Выходная формула 2
Оставшаяся часть входной формулы 3*5 + 7)/(18 - 7)
Cтек ( -
Выходная формула 2 3
Оставшаяся часть входной формулы *5 + 7)/(18 - 7)
Cтек ( - *
Выходная формула 2 3
Оставшаяся часть входной формулы 5 + 7)/(18 - 7)
Cтек ( - *
Выходная формула 2 3 5
Оставшаяся часть входной формулы + 7)/(18 - 7)
Cтек ( +
Выходная формула 2 3 5 * -
Оставшаяся часть входной формулы 7)/(18 - 7)
Cтек ( +
Выходная формула 2 3 5 * - 7
Оставшаяся часть входной формулы )/(18 - 7)
Cтек Empty
Выходная формула 2 3 5 * - 7 +
Оставшаяся часть входной формулы /(18 - 7)
Cтек /
Выходная формула 2 3 5 * - 7 +
Оставшаяся часть входной формулы (18 - 7)
Cтек / (
Выходная формула 2 3 5 * - 7 +
Оставшаяся часть входной формулы 18 - 7)
Cтек / (
Выходная формула 2 3 5 * - 7 + 18
Оставшаяся часть входной формулы - 7)
Cтек / ( -
Выходная формула 2 3 5 * - 7 + 18
Оставшаяся часть входной формулы 7)
Cтек / ( -
Выходная формула 2 3 5 * - 7 + 18 7
Оставшаяся часть входной формулы )
Cтек /
Выходная формула 2 3 5 * - 7 + 18 7 -
Оставшаяся часть входной формулы Empty
Cтек Empty
Выходная формула 2 3 5 * - 7 + 18 7 - /
Оставшаяся часть входной формулы Empty
ПЕРЕРЫВ до 11:25
Усложнение: обработка имени функции
. . .
5) правая (закрывающая) скобка выкидывает из стека
все операции вплоть до первой открывающей скобки,
после чего пара скобок взаимно уничтожаются.
6) в конце, когда заканчивается входная формула,
все оперции из стека операций выкидываются в выходную
формулу;
7) если входная лексема -- имя стандартной функции,
то оно просто добавляется в стек операций (вслед за
этим в стек операций будет добавлени открывающая
скобка, например, sin(2 + 3.14158 / 3)
8) при обработке правой (закрывающей) скобки после
взаимного уничтожения двух скобок на вершине стека
операций будет имя функции, то оно выкидывается из стека
в конец выходной формулы.
Пример: 10 + sin(3.14158/4)
Cтек Empty
Выходная формула Empty
Оставшаяся часть входной формулы 10 + sin(3.14158/4)
Cтек Empty
Выходная формула 10
Оставшаяся часть входной формулы + sin(3.14158/4)
Cтек +
Выходная формула 10
Оставшаяся часть входной формулы sin(3.14158/4)
Cтек + sin
Выходная формула 10
Оставшаяся часть входной формулы (3.14158/4)
Cтек + sin (
Выходная формула 10
Оставшаяся часть входной формулы 3.14158/4)
Cтек + sin (
Выходная формула 10 3.14158
Оставшаяся часть входной формулы /4)
Cтек + sin ( /
Выходная формула 10 3.14158
Оставшаяся часть входной формулы 4)
Cтек + sin ( /
Выходная формула 10 3.14158 4
Оставшаяся часть входной формулы )
Cтек +
Выходная формула 10 3.14158 4 / sin
Оставшаяся часть входной формулы
Cтек
Выходная формула 10 3.14158 4 / sin +
Оставшаяся часть входной формулы
=====================================================
Операции ввода-вывода в языке Haskell и грязный код
Грязный tainted (грязный, испорченный, загнивающий, падший).
Обычный код в языке Haskell называется "чистым" (pure).
Чистый код -- это когда любая функция не имеет никаких
побочных эффектов и всегда возвращает один и тот же
результат при одних и тех же аргументах.
В частности, чистые функции не могут ничего читать с
консоли или из файла. Чистые функции не могут возвращать
случайных чисел (не бывает датчиков случайных чисел и т.п.).
Грязные функции противоречат идеологии Хаскеля, поэтому
они четко отделены от чистых функций и имеют тип
IO + плюс тип возвращаемого значения.
ПЕРЕРЫВ до 14:00
Грязный (испорченный, предательский, гнилой) код
Исполняется в функции main
main :: IO ()
main = put
==============================================
32 Jan 2021
Тип данных "Отображение" Map
Модуль Data.Map
отображение == ассоциативный массив ==
нагруженное множество
На C++ класс std::map<KeyType, ValueType>
содержит пары (ключ, значение ключа)
каждый ключ содержится только в одном экземпляре
(key1, value1) in map,
(key2, value2) in map => key1 != key2
Как бы ключи отображаются на значения:
Map: key -> value
Ассоциативный массив, потому что во многих языках
с отображением можно работать как с массивом.
В обычном массиве индексы -- это целые числа.
В ассоциативном массиве индексами являются ключи,
т.е. элементы любого типа. Например, в C++
#include <map>
#include <string>
using namespace std;
. . .
map<string, int> phonebook;
phonebook["Ivan Petrov"] = 1234567;
int num = phonebook["Sidorov"];
Ограничение на тип ключей: они должны быть сравнимы
==, !=, <, <=, >, >=
Это требование объясняется тем, что реализация отображения
(как и множества set) использует (сбалансированные)
бинарные деревья поиска (C++ использует красно-черные
деревья), так что операции выполняюся за время O(log n),
где n -- число элементов в множестве.
Пример: множество банковских счетов.
Ключи: идентификаторы счетов (в Росии это
строка из 20 цифр)
Значения ключей: вся информация, связанная со счетом
(имя владельца, его паспортные данные, баланс счета,
список транзакций и т.п.).
Мы рассмотрим простой пример: телефонная книга.
Ключи: имена людей (текстовые строки)
Значения ключей: телефоны (тоже текстовые строки)
В Haskell для использования типа данных Map надо
импортированть модуль Data.Map
Проблема в том, что в нем много функций, имена которых
совпадают с функциями в модуле Prelude. Принято всегда
использовать квалифицированный импорт:
квалифицированное имя функции или типа данных
состоит из имени модуля, точки и дальше имени функции
или типа.
Map -- имя типа
Квалифицированное имя:
Data.Map.Map
Обычно пишут так:
-- import Data.Map
import qualified Data.Map as Map
Квалифицированное имя:
Map.Map
Конкретный тип: (Map.Map String Integer) -- имя типа,
нагруженное множество, отображающее ключи типа String
на значения типа Integer
log_2(1000000) ~
1024 = 2^10 ~ 1000 = 10^3
2^10 ~ 10^3
1000000 = 10^6 = (10^3)^2 ~ (2^10)^2 = 2^20
log_2(1000000) ~ log_2(2^20) = 20
Функции для работы с Map
Map.insert key value map
Добавить ключ key со значением value к нагруженному множеству map
Map.lookup key map
Найти значение ключа key
Функция Map.lookup возвращает значение типа Maybe ТипЗначения
т.е.
Just значениеКлюча
если ключ найден, и
Nothing
если ключ не найден.
Map.delete key
Удалить ключ и его значение из множества.
Создать нагруженное множество из списка пар (key, value)
можно с помощью функции
Map.fromList lst
Обратная функция: получить список пар типа (key, value)
из нагруженного множества
Map.toList map
==========================================================
Работа с файлами
import System.IO
main = do
contents <- readFile "girlfriend.txt"
putStr contents