Математические основы информатики

* – необязательные задания вопросы для получения оценки "5"

http://sch192.mosuzedu.ru/mood[..]/quiz/view.php?id=99

Сжатие данных

RLE

Теория

Задачи
Нужно написать программу кодирования и раскодирования. В условии только кодирование.
(Во всех задачах 0 и 1 в скобках означают бит, при кодировании используется соответствующий байт)

1. Строка символов кодируется так: <количество><символ><количество><символ>...
Например, aaabbbbbbbbbbbbdccc кодируется строкой 3a12b1d3c

2. То же, но числа заменяются байтами, что позволяет кодировать длины повторений до 256 (0 означает 1,
все единицы – 256)

3. То же, но старший (седьмой) бит байта означает тип подпоследовательности: 0 с повторениями, 1 без повторений.
(0 в оставшейся части означает 1, все единицы 128)
Например строка aaaabcdaabbb кодируется как (00000011)a(10000010)bcd(00000001)a(00000010)b

4* Иногда эффективно кодировать повторения из нескольких байт.
Программа должна принимать количество байт в блоке.
В первом байте файла записывается это количество минус один.
Например, abababaabab при двухбайтном сжатии кодируется как (00000001)(00000010)ab(10000010)aabab
(в последнем блоке байтов получилось меньше)

Представление чисел в компьютере

До "О" включительно

Системы счисления

Вопросы
1. Какие системы счисления называются позиционными и непозиционными?
*2. Нетрадиционные позиционные системы счисления (факториальная, троичная уровновешенная (симметричная), фибоначчивая)
3. p-ичные системы счисления

Задачи
Контест (три последние задачи со звездочкой)

Количество информации

Вопросы

1. Что такое информация?
2. Алфавитный и содержательный подход к измерению информации.
2. Что такое бит, байт, килобайт?
3. Формула Хартли
4. Доказательство формулы Хартли для N – не точной степени двойки

Задания
1. Написать программу на любом языке, которая выводит заданный файл в двоичном и шестнадцатиричном представлении
Например, для какого-то файла из 3-х байт
00001100 11100000 11111111
и 
0С E0 FF