11 Б

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


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

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


Алгоритмы без программирования.


LZ77
LZ78
метод Хаффмана


Нужно знать только сам принцип, но знать его хорошо.

Упаковка


Если в файле немного различных байтов, то можно кодировать байты меньшим количеством бит. Например, если в файле всего два символа, то можно кодировать каждый из них одним битом. Если 2 или 3 или 4 – двумя и т.д.


Нужно научится упаковывать файлы (написать программу упаковки и распаковки).


Для этого нужно решить следующие задачи:


1. Прочитать файл побайтно и составить Алфавит – массив (список) байтов этого файла без повторений. И присвоить каждому байту код.
2. Прочитать файл повторно и записать в упакованный файл
<количество символов в алфавите><Алфавит><Количество значимых бит в последнем байте><коды соответствующие символам алфавита><коды символов >


Самое сложное – научиться записывать коды определенным количеством бит. То есть из файла c символами


ABAAAAABВС


получить содержимое упаковки —

<00000011> <01000001> <01000010> <01000011> <00000100> <00010000> <00000100> <00000001> <01100000>
  3 символа     A          B          C   4 бита в хвосте

В последнем байте всего четыре значимых бита 0110, остальные могут быть любыми, при распаковке они игнорируются.


3. Распаковка делается аналогично. Напишите программу для распаковки

RLE

Теория


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


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


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


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


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


Задачи можно и нужно сдавать в тестирующую систему, на Codeforces, обращайтесь к Алексею Кулдошину.

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

Целые числа и битовые операции|Теория|Условия|Вход

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

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

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

а. Определение
б. Доказательство единственности представления любого числа
в. Алгоритмы перевода целых чисел с доказательством
г. Алгоритм быстрого перевода в системы с основанием, являющимся степенью и обратно (*с доказательством)
д. Алгоритмы перевода дробей с доказательствами
*е. Условия появления периода

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

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

Вопросы


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


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