Скрипты 2012-2013

ФТ-102

Виртуальная машина
Требуется
1. придумать собственный низкоуровневый язык, выразительные способности которого будут достаточны для решения простых вычислительных задач;
2. написать на этом языке программу вычисления факториала натурального числа и программу нахождения наибольшего общего делителя двух натуральных чисел;
3. написать на JScript виртуальную машину исполняющую программы, написанные на разработанном языке.

Float
Написать программу, которая работает в одном из двух режимов: перевод или выполнение арифметических операций.
В первом режиме программа считывает из файла in.txt строку. 1) Если строку мож- но интерпретировать как число, в файл out.txt записывается внутреннее представление этого числа, в частности, если число по модули превосходит (2−2−23)·2127, в файл out.txt записывается внутреннее представление бесконечности. 2) Если строку нельзя интерпре- тировать как число в файл out.txt записывается внутреннее представление не числа.

Во втором режиме программа считывает из файла in.txt строку, содержащую два числа, разделенных операцией + или -. Программа переводит операнды во внутреннее представление и выполняет сложение/вычитание над операндами в их внутреннем пред- ставлении согласно правилам стандарта IEEE 754. В файл out.txt записывается результат выполнения арифметической операции во внутреннем и в десятичном виде.
Режим работы указывается в качество параметра командной строки.

Реализовать свой тип Float. Реализовать следующие функции:
1) преобразование из строки с научной записью числа в массив битов
2) преобразование из массива битов в строку с научной записью числа
3) сложение двух битовых массивов
4) умножение двух битовых массивов
5) сравнение двух битовых массивов
Обязательно должны быть Na N? и ±inf.
После запуска в программу вводятся две строки с научной записью чисел и операция.

RLE
За реализацию одного алгоритма максимум - 5 баллов.

Энтропия Shannon
На вход подается строка — последовательность букв. Требуется
1. построить алфавит (т.е. множество всех различных символов исходной строки) и найти частоту для всех символов алфавита;
2. для полученной таблицы рассчитать энтропию согласно H(X) = − Сумма (i= 1..n)
p_i * log_n (p_i).

Поиск подстроки в строке bruteforce & hash
1) Brute Force
2) хэш = сумма кодов
3) хэш = сумма квадратов кодов
4) Хэш Рабина-Карпа
5) Предлагаем провести несколько тестов, которые позволят оценить время работы алгорит- мов поиска подстроки в строке. Проводя эксперименты, надо соблюдать рад требований. Во-первых, не нагружать систему посторонними задачами. Если параллельно с программой поиска работает ещё десяток приложений (решается сложная система уравнений в MATLAB, просчитывается трехмерная сцена в 3d Max, играется музыка и т.д.), все это существенно исказит результаты. Во-вторых, эксперимент должен быть проведен неодно- кратно, чтобы усреднить полученные результаты и тем самым снизить влияние случайных факторов.
Готовя отчет по результатам экспериментов, необходимо описывать систему. Указывать по крайней мере тактовую частоту процессора, объем оперативной памяти, операци- онную систему. Отчет должен быть таким, чтобы посторонний человек мог, прочитав его, в точности воспроизвести описанный эксперимент и получить аналогичный результат.
ТЕСТ No 1. Увеличение длины строки, в которой ищется подстрока (brute force).
В тексте, например, «Война и мир» Л.Н. Толстого ищем подстроку «княз Андрей». Сравнить время поиска в первом томе, первых двух томах, первых трех томах, во всех четырех.
ТЕСТ No 2. Увеличение длины искомой подстроки (brute force).
В тексте, например, «Война и мир» Л.Н. Толстого ищем последовательно подстроки «княз», «княз Андрей», «княз Андрей Болконский». Сравнить время поиска. Соотносится ли время поиска как 5:12:23? Объяснить результат. Как это согласуется (не согласуется) с общей теорией.
Сделать то же для подстрок «фортификация которых производилась» и « которых про- изводилсь» (первый символ пробел).
ТЕСТ No 3. Сравнение brute force и хэшей.
Строка — миллион букв a. Подстроки T1 = a.(100 раз)..ab и T2 = ba.(100 раз)..a. Сравнить время работы двух вариантов поиска (brute force и хэши) в каждом из случаев. Результаты объяснить.
Правда ли, что хэши всегда быстрее brute force?

Поиск подстроки в строке с использованием ДКА

Поиск подстроки в строке, Бойер-Мур

Сжатие по Хаффману
Сжать сообщение. Построить дерево. Вывести его. Восстановить сообщение.

Алгоритм Дейкстры, обратная польская запись
Перевести математическое выражение из инфексной записи в обратную польскую запись. Реализовать вычисления выражения в ОПЗ

Шифр Цезаря
Закодировать сообщение. Декодировать. Либо вывести все варианты, либо учитывая частоты символов вывести подходящий вариант(ы) - будет учитываться в дополнительные 2 балла

Код Хэмминга
Закодировать сообщение. Декодировать. Отлавливание ошибок. Исправление.

КН-104

Виртуальная машина
Требуется
1. придумать собственный низкоуровневый язык, выразительные способности которого будут достаточны для решения простых вычислительных задач;
2. написать на этом языке программу вычисления факториала натурального числа и программу нахождения наибольшего общего делителя двух натуральных чисел;
3. написать на JScript виртуальную машину исполняющую программы, написанные на разработанном языке.

Float
Написать программу, которая работает в одном из двух режимов: перевод или выполнение арифметических операций.
В первом режиме программа считывает из файла in.txt строку. 1) Если строку мож- но интерпретировать как число, в файл out.txt записывается внутреннее представление этого числа, в частности, если число по модули превосходит (2−2−23)·2127, в файл out.txt записывается внутреннее представление бесконечности. 2) Если строку нельзя интерпре- тировать как число в файл out.txt записывается внутреннее представление не числа.

Во втором режиме программа считывает из файла in.txt строку, содержащую два числа, разделенных операцией + или -. Программа переводит операнды во внутреннее представление и выполняет сложение/вычитание над операндами в их внутреннем пред- ставлении согласно правилам стандарта IEEE 754. В файл out.txt записывается результат выполнения арифметической операции во внутреннем и в десятичном виде.
Режим работы указывается в качество параметра командной строки.

Реализовать свой тип Float. Реализовать следующие функции:
1) преобразование из строки с научной записью числа в массив битов
2) преобразование из массива битов в строку с научной записью числа
3) сложение двух битовых массивов
4) умножение двух битовых массивов
5) сравнение двух битовых массивов
Обязательно должны быть Na N? и ±inf.
После запуска в программу вводятся две строки с научной записью чисел и операция.

RLE
За реализацию одного алгоритма максимум - 5 баллов.

Энтропия Shannon
На вход подается строка — последовательность букв. Требуется
1. построить алфавит (т.е. множество всех различных символов исходной строки) и найти частоту для всех символов алфавита;
2. для полученной таблицы рассчитать энтропию согласно H(X) = − Сумма (i= 1..n)
p_i * log_n (p_i).

Поиск подстроки в строке bruteforce & hash
1) Brute Force
2) хэш = сумма кодов
3) хэш = сумма квадратов кодов
4) Хэш Рабина-Карпа
5) Предлагаем провести несколько тестов, которые позволят оценить время работы алгорит- мов поиска подстроки в строке. Проводя эксперименты, надо соблюдать рад требований. Во-первых, не нагружать систему посторонними задачами. Если параллельно с программой поиска работает ещё десяток приложений (решается сложная система уравнений в MATLAB, просчитывается трехмерная сцена в 3d Max, играется музыка и т.д.), все это существенно исказит результаты. Во-вторых, эксперимент должен быть проведен неодно- кратно, чтобы усреднить полученные результаты и тем самым снизить влияние случайных факторов.
Готовя отчет по результатам экспериментов, необходимо описывать систему. Указывать по крайней мере тактовую частоту процессора, объем оперативной памяти, операци- онную систему. Отчет должен быть таким, чтобы посторонний человек мог, прочитав его, в точности воспроизвести описанный эксперимент и получить аналогичный результат.
ТЕСТ No 1. Увеличение длины строки, в которой ищется подстрока (brute force).
В тексте, например, «Война и мир» Л.Н. Толстого ищем подстроку «княз Андрей». Сравнить время поиска в первом томе, первых двух томах, первых трех томах, во всех четырех.
ТЕСТ No 2. Увеличение длины искомой подстроки (brute force).
В тексте, например, «Война и мир» Л.Н. Толстого ищем последовательно подстроки «княз», «княз Андрей», «княз Андрей Болконский». Сравнить время поиска. Соотносится ли время поиска как 5:12:23? Объяснить результат. Как это согласуется (не согласуется) с общей теорией.
Сделать то же для подстрок «фортификация которых производилась» и « которых про- изводилсь» (первый символ пробел).
ТЕСТ No 3. Сравнение brute force и хэшей.
Строка — миллион букв a. Подстроки T1 = a.(100 раз)..ab и T2 = ba.(100 раз)..a. Сравнить время работы двух вариантов поиска (brute force и хэши) в каждом из случаев. Результаты объяснить.
Правда ли, что хэши всегда быстрее brute force?

Поиск подстроки в строке с использованием ДКА

Поиск подстроки в строке, Бойер-Мур

Сжатие по Хаффману
Сжать сообщение. Построить дерево. Вывести его. Восстановить сообщение.

Алгоритм Дейкстры, обратная польская запись
Перевести математическое выражение из инфексной записи в обратную польскую запись. Реализовать вычисления выражения в ОПЗ

Шифр Цезаря
Закодировать сообщение. Декодировать. Либо вывести все варианты, либо учитывая частоты символов вывести подходящий вариант(ы) - будет учитываться в дополнительные 2 балла

Код Хэмминга
Закодировать сообщение. Декодировать. Отлавливание ошибок. Исправление.

КН-102

Виртуальная машина

Float

RLE
За реализацию одного алгоритма максимум - 5 баллов.

Shannon

Сжатие Хаффмана

Поиск паттерна в строке
1) Brute Force
2) хэш = сумма кодов
3) хэш = сумма квадратов кодов
4) Хэш Рабина-Карпа

Automaton

Boyer-Moore

Коллоквиум

Польская нотация

Шифр Цезаря

Хемминг

Поиск подстроки в строке. Итоги