Алгоритм решения на зачет по информатике
1. Тема: Использование информационных моделей (таблицы, диаграммы, графики).
Перебор вариантов, выбор лучшего по какому-то признаку.
· полезно знать, что такое граф (это набор вершин и соединяющих их ребер) и как он описывается в виде таблицы, хотя, как правило, все необходимые объяснения даны в формулировке задания
· чаще всего используется взвешенный граф, где с каждым ребром связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки
Тема: Кодирование и декодирование информации
· кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)
· обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход
· один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)
· кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование
· закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;
· закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;
· условие Фано – это достаточное, но не необходимое условие однозначного декодирования
Тема: Кодирование растровых изображений
· для хранения растрового изображения нужно выделить в памяти I = N · i битов, где N – количество пикселей и i – глубина цвета (разрядность кодирования)
· количество пикселей изображения N вычисляется как произведение ширины рисунка на высоту (в пикселях)
· глубина кодирования – это количество бит, которые выделяются на хранение цвета одного пикселя
· при глубине кодирования i битов на пиксель код каждого пикселя выбирается из 2i возможных вариантов, поэтому можно использовать не более 2i различных цветов
· нужно помнить, что
1 Мбайт = 220 байт = 223 бит,
1 Кбайт = 210 байт = 213 бит
Тема: Кодирование чисел. Системы счисления.
o принципы кодирования чисел в позиционных системах счисления
o 
чтобы перевести число, скажем, 12345N, из системы счисления с основанием 
в десятичную систему, нужно умножить значение каждой цифры на в степени, равной ее разряду:
§ 4 3 2 1 0 ← разряды
§ 1 2 3 4 5N = 1·N4 + 2·N3 + 3·N2 + 4·N1 + 5·N0
o последняя цифра записи числа в системе счисления с основанием – это остаток от деления этого числа на
o две последние цифры – это остаток от деления на 
, и т.д.
o число 10N записывается как единица и N нулей: 
o число 10N-1 записывается как N девяток: 
o число 10N-10M = 10M · (10N-M – 1) записывается как N-M девяток, за которыми стоят M нулей: 
o число 2N в двоичной системе записывается как единица и N нулей: 
o число 2N-1 в двоичной системе записывается как N единиц: 
o число 2 N– 2 K при K < N в двоичной системе записывается как N–K единиц и K нулей: 
o поскольку 
, получаем 
, откуда следует, что 
o число 3N записывается в троичной системе как единица и N нулей: 
o число 3N-1 записывается в троичной системе как N двоек: 
o число 3N – 3M = 3M · (3N-M – 1) записывается в троичной системе как N-M двоек, за которыми стоят M нулей: 
можно сделать аналогичные выводы для любой системы счисления с основанием a:
a. число aN в системе счисления с основанием a записывается как единица и N нулей: 
b. число aN-1 в системе счисления с основанием a записывается как N старших цифр этой системы счисления, то есть, цифр (a-1): 
c. число aN – aM = aM · (aN-M – 1) записывается в системе счисления с основанием a как N-M старших цифр этой системы счисления, за которыми стоят M нулей: 