Скрипты 2015-2016

ФТ-101

Энтропия
Подсчитать энтропию для входной строки.
1 вариант: основание логарифма = 2
2 вариант: основание логарифма = N (размерность алфавита)

Примеры запуска:
>node entropy.js asdf
2
>node entropy.js a
0

RLE
Реализовать кодирование/декодирование RLE.
1 вариант: Jump,
2 вариант: Escape

Примеры запуска:
Содержимое in.txt закодировать, результат поместить в out.txt
>node rle.js encode in.txt out.txt

Содержимое out.txt раскодировать, результат поместить в in2.txt
>node rle.js decode out.txt in2.txt

Сравнить начальный файл с результатом кодирования/раскодирования
>fc in.txt in2.txt


===
Jump: Акулин, Арсланова, Ветошкин, Гайнанов, Дубровин, Евдокимов, Котляров, Крыловская, Липин, Лисовенко, Первунин, Пешков, Смирнов, Сумина, Яркеев

float
Примеры запуска:

Перевод из десятичного представления числа во float: вывести двоичное представление, hex. Реализовать перевод из float в десятичное число.
>node float.js encode 1.5
00111111110000000000000000000000 3FC00000 ~ 1.5

>node float.js encode 1.5
00111111110000000000000000000000 3FC00000 ~ 1.5

Перевести оба числа во float, сложить (посчитать разность), после вывести результат в двоичном, шестнадцатеричном и десятичном виде.
>node float.js sum 1.5 + 0.5
01000000000000000000000000000000 40000000 ~ 2

>node float.js encode 0.1
00111101110011001100110011001101 3DCCCCCD ~ 0.10000000149011612

>node float.js encode aaa
01111111111111111111111111111111 7FFFFFFF ~ NaN

>node float.js encode 9999999999999999999999999999999999999999999999
01111111100000000000000000000000 7F800000 ~ +Infinity

>node float.js encode 0.000000000000000000000000000000000000001
00000000000010101110001110011000 000AE398 ~9.99998814006869E-40

VM
Придумать свой низкоуровневый язык (в языке не должно быть команд %, Abs)
Написать интерпретатор, понимающий придуманный язык.

На созданном языке реализовать:
1) нахождение n-го члена Фибоначчи
2) нахождение НОД

Примеры запуска:
> node interpretator.js fib.txt
Введите номер:
3
2

> node interpretator.js fib.txt
Введите номер:
-4
Некорректный ввод

> node interpretator.js node.txt
Введите первое число:
-4
Введите второе число:
6
2

Дейкстра
>node dijkstra.js in2post (a+b*c)/d
abc*+d/

>node dijkstra.js post2in abc*+d/
(a+b*c)/d

>node dijkstra.js in2post ы))))))
Error: ...

Хаффман
Реализовать кодирование Хаффмана.

При кодировании вывести в консоли:
- в первой строке - теоретическое сжатие *
- во второй - получившееся сжатие * (без учета таблицы символов)
Оба числа округлить до 2 знаков после запятой.

Закодировать содержимое in.txt, таблицу соответствия символам кодов поместить в table.txt, результат в виде набора 1 и 0 - в out.txt
>node huffman.js encode in.txt table.txt out.txt
2.20
2.18

Раскодировать содержимое in.txt, таблицу соответствия символам кодов брать из table.txt, результат в виде строки - в out.txt
>node huffman.js decode in.txt table.txt out.txt
ok

Замечания:
*) под сжатием понимается отношение объема текста на входе к объему текста на выходе
**) table.txt в своем формате
***) если при раскодировании возникла ошибка, то пишем в консоли
error: здесь описание ошибки
В out.txt помещаем то, что смогли раскодировать

5ки+кр

Коллоквиум

bm+hashes
> node hash.js str.txt substr.txt [-t] [-b] [--h1] [--h2] [--h3] [-n N]

Вывести индексы (начинаются с 0) вхождений текста из substr.txt в тексте из str.txt. Для хэшей в отдельной строке вывести число коллизий. После вывода каждого алгоритма вывести пустую строку.
! Если вхождений нет, то выводим пустую строку вместо списка.
! сравнивать подстроки нужно посимвольно
! Строки заканчиваем символами \r\n

Описание ключей:
-t - в отдельной строке выводить время работы каждого алгоритма
-b - брутфорс
--h1, --h2, --h3 - хэши, сумма кодов, сумма квадратов кодов, Рабина-Карпа соответственно
-n N - если параметр задан, то выводим первые N вхождений (если нашли меньше, то выводим все)

Примеры:
> node hash.js str.txt substr.txt -b -t
1, 6, 12, 24
Time: 24ms

> node hash.js str.txt substr.txt -b --h1 -t -n 2
1, 6
Time: 24ms

1, 6
Collisions: 6
Time: 44ms

> node hash.js str.txt substr.txt --h1 --h2 -n 2
1, 6
Collisions: 6

1, 6
Collisions: 12

Auto
> node auto.js str.txt substr.txt [-t] [-s] [-n N]

Вывести индексы вхождений текста из substr.txt в тексте из str.txt. Индексы начинаются с 0

Описание ключей:
-t - в отдельной строке выводить время работы каждого алгоритма
-s - после всего вывода отобразить таблицу автомата
-n N - если параметр задан, то выводим первые N вхождений (если нашли меньше, то выводим все)

Примеры:
> node auto.js str.txt substr.txt -t
1, 6, 12, 24
Time: 24ms

> node auto.js str.txt substr.txt -s -t -n 2
1, 6
Time: 24ms
| a | и | c
-------------
0| 1 | 0 | 0
...

Б-М
Реализовать поиск подстроки в строке при помощи алгоритма Бойера-Мура.
Эвристика плохого символа: 3 балла
Эвристика совпавшего суффикса: +4 балла

> node bm.js str.txt substr.txt [-t] [-n N]

Вывести индексы вхождений текста из substr.txt в тексте из str.txt. Индексы начинаются с 0

Описание ключей:
-t - в отдельной строке выводить время работы каждого алгоритма
-n N - если параметр задан, то выводим первые N вхождений (если нашли меньше, то выводим все)

Примеры:
> node bm.js str.txt substr.txt -t
1, 6, 12, 24
Time: 24ms

> node bm.js str.txt substr.txt -t -n 2
1, 6
Time: 24ms

Hamming
Реализовать кодирование Хэмминга.

На html-странице должны быть:
- поле ввода с атрибутом id="input"
- кнопка для кодирования с атрибутом id="encodeButton"
- кнопка для проверки закодированного текста с атрибутом id="checkButton"
- кнопка для декодирования с атрибутом id="decodeButton"
- элемент html-разметки с атрибутом id="resultContainer"

В результате кодирования в контейнере с результатом должен оказаться закодированный текст, состоящий из нулей и единиц (нумерация слева направо). Исходный текст берется из поля input, состоит только из 0 и 1

В результате проверки в контейнере с результатом должна оказаться либо строка "Correct", либо "Error: N", где N - индекс ошибочного символа (нумерация с единицы). Кавычки и переводы строк выводить не надо. Исходный текст для проверки берется из поля input, состоит только из 0 и 1

В результате декодирования в контейнере с результатом должен оказаться раскодированный текст (исправленный, если в этом есть необходимость), состоящий из нулей и единиц. Исходный текст берется из поля input, состоит только из 0 и 1

Подстроки
Провести сравнительный анализ работы алгоритмов поиска подстроки в строке:

BF
Hash (сумма кодов)
Hash (сумма квадратов)
Hash (Рабина — Карпа)
Auto
BM

Необходимо исследовать работу в зависимости от объема входных данных (объем текста, длина подстроки), т.е.. длинный текст + длинная подстрока, короткий текст + длинная подстрока и т.д. Для каждого объема данных и алгоритма провести не менее 10 тестов.

По результатам тестов подготовить отчет, в котором сделать вывод о том какой алгоритм и в каких условиях ведет себя лучше. В отчете в обязательном порядке должны быть графики (больше графиков).

Caesar
Реализовать шифр Цезаря (4 балла)

Необходимо шифровать только символы выбранного алфавита (рус/англ). Все остальные символы игнорируются и в выходной файл не попадают. Символы в выходном файле должны быть в нижнем регистре. Алфавит задается параметром -l, который может принимать значение en либо ru. Алфавит по умолчанию - английский.

Шифрование: shift - любое целое число
>node caesar.js encode in.txt out.txt shift -l en

Дешифровка: на консоль выводим сдвиг, по котороум текст был зашифрован (из интервала [0,N), где N - количество символов в алфавите, в out.txt - расшифрованный текст
>node caesar.js decode in.txt out.txt -l en
Console output: shift

Реализовать шифр Виженера (7 баллов)

Необходимо шифровать только символы выбранного алфавита (рус/англ). Все остальные символы игнорируются и в выходной файл не попадают. Символы в выходном файле должны быть в нижнем регистре. Алфавит задается параметром -l, который может принимать значение en либо ru. Алфавит по умолчанию - английский.

Шифрование
>node vigenere.js encode in.txt out.txt code_word -l ru

Дешифровка: на консоль выводим слово, по которому текст шифровали, в out.txt - расшифрованный текст
>node vigenere.js decode in.txt out.txt -l ru
Console output: code_word

! Кодировка входного файла - ANSI
!! Букву ё заменяем на е

Life
Реализовать life (можно с использованием шаблона, лежащего в папке на дропбоксе). В интерфейсе должны быть следующие элементы:
- текстовое поле, в котором написано число - количество итераций жизни в секунду
- кнопка "Start" (при нажатии на нее итерации сменяют друг друга автоматически с заданным периодом)
- кнопка "Pause", при нажатии на которой "жизнь останавливается" на текущем состоянии
- кнопка "Step", при нажатии на которую во вселенной генерируется следующее поколение
- вселенная в виде матрицы, каждую клетку можно оживить/умертвить нажатием на нее

1 вариант ([Акулин, Котляров]): вселенная зациклена (справа от правой границы идет левая граница).
2 вариант ([Крыловская, Яркеев]): вселенная ограничена размерами поля (вышедший за границы пропадает навсегда)

Результат в виде ревью-реквеста со ссылкой на Жизнь в описании. Ключи для dreamspark для Azure у Даши (староста)

Activity