Школа179

Просмотр кода страницы 11 Б страница

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

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

http://sch192.mosuzedu.ru/moodle/mod/quiz/view.php?id=99

====Сжатие данных====
=====RLE=====
[[https://habr.com/post/141827 Теория]]

**Задачи**
Нужно написать программу кодирования и раскодирования. В условии только кодирование.
(Во всех задачах 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
(в последнем блоке байтов получилось меньше)

====Представление чисел в компьютере====
#||Целые числа и битовые операции|((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