* - необязательные задания вопросы для получения оценки "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. Распаковка делается аналогично. Напишите программу для распаковки
**Задачи** Нужно написать программу кодирования и раскодирования. В условии только кодирование. (Во всех задачах 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, обращайтесь к Алексею Кулдошину.
====Представление чисел в компьютере==== #||Целые числа и битовые операции|((http://server.179.ru/tasks/cpp/theory/19-bits.html Теория))|((http://server.179.ru/tasks/cpp/2019b3/21-bits.html Условия))|((http://server.179.ru/cgi-bin/new-client?contest_id=834&locale_id=1 Вход )) |# До "О" включительно ====Системы счисления==== **Вопросы** 1. Какие системы счисления называются позиционными и непозиционными? *2. Нетрадиционные позиционные системы счисления (факториальная, троичная уровновешенная (симметричная), фибоначчивая) 3. p-ичные системы счисления а. Определение б. Доказательство единственности представления любого числа в. Алгоритмы перевода целых чисел с доказательством г. Алгоритм быстрого перевода в системы с основанием, являющимся степенью и обратно (*с доказательством) д. Алгоритмы перевода дробей с доказательствами ""*""е. Условия появления периода
**Задачи** [[https://informatics.msk.ru/moodle/mod/statements/view.php?id=34400#1 Контест]] (три последние задачи со звездочкой)
====Количество информации==== **Вопросы**
1. Что такое информация? 2. Алфавитный и содержательный подход к измерению информации. 2. Что такое бит, байт, килобайт? 3. Формула Хартли 4. Доказательство формулы Хартли для N - не точной степени двойки
**Задания** 1. Написать программу на любом языке, которая выводит заданный файл в двоичном и шестнадцатиричном представлении Например, для какого-то файла из 3-х байт 00001100 11100000 11111111 и 0С E0 FF
---- адрес оригинала: ((/Информатика/Архив/2019/11Б))