Системы счисления: основные определения

Тема "Системы счисления" рассматривается в школе в 6 классе для тех, кто занимается по УМК Босовой, рассчитанному на 5-7 класс; возвраты к ней осуществляются в старшей школе, и для тех, у кого информатика началась в 7 классе, 10 класс становится первой встречей с этой темой - в пределах курса информатики.
Отмечу, что меняется не принцип заданий, но их сложность. Одним из самых сложных моментов понимания не сложной в принципе темы является необходимость вспоминать начальную школу: арифметические действия в столбик, дошедшие до автоматизма и утерявшие осознанность.

Итак,
Основные определения

Система счисления (СС) - способ записи числа с помощью письменных знаков (цифр).
Обращаю ваше внимание на то, что понятие цифр включает, помимо привычных нам арабских, любые знаки, используемые для записи числа: в римской и шестнадцатеричной системах в роли цифр выступают различные буквы латинского алфавита, в славянской буквенной - отмеченные определённым символом знаки кириллицы etc.

СС имеет даёт представления множества чисел (целых и/или вещественных).

СС даёт каждому числу уникальное представление (или, по крайней мере, стандартное представление).

Основание системы счисления - количество цифр, используемых для записи числа.
Основание СС указывает на количество единиц младшего разряда, образующих одну единицу старшего.

Так, десятичная СС состоит из 10 цифр: 0 ... 9.
Возьмём наименьшую из цифр - это нуль - и будем последовательно прибавлять по единице:
0+1=1; 1+1=2; 2+1=3; ... 8+1=9; 9+1=10 - 9 - последняя из цифр, при очередном сложении мы получаем 0, и 1 переходит в старший разряд.

Для восьмеричной системы, состоящей из 8 цифр: 0 ... 7.

Вес цифры - количественное значение, которое вносит цифра в число.
Разряд - позиция цифры в записи числа.

Пример: число 6437 имеет 7 в первом разряде, 3 во втором, 4 в третьем, 6 в четвёртом.

Если в СС вес цифры зависит от разряда, то такую СС называют позиционной, если не зависит, то такая СС называется непозиционной.

Пример: привычная нам десятичная система является позиционной; римская - непозиционной.

Решение задачи B12 (2012)

Задача

В языке запросов поискового сервера для обозначения логической операции ИЛИ используется символ "|", а для логической операции И - символ "&".
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Запрос	Найдено страниц (в тысячах)
Шахматы | Теннис	7770
Теннис	5500
Шахматы & Теннис	1000

Какое количество страниц (в тысячах) будет найдено по запросу Шахматы?

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Решение

Рассмотрим найденные по запросам наборы страниц как множества, мощность которых нам известна. 

Отношения между множествами и операции над ними

Отношения между множествами

Выше мы встретились с тем, что одно множество может являться частью другого. В самом общем случае все множества являются частью универсума - множества, включающего в себя все мыслимые множества (в рамках конкретной задачи).

Такое отношение называется включением множества A в множество B:
A ⊆ B, если каждый элемент множества A является также элементом множества B.
В этом случае множество B включает в себя множество А.

Говорят, что множество А строго включено в множество B, если А включено в B и не равно ему:
A ⊂ B
В этом случае множество B строго включает в себя множество А; А является собственным множеством множества В.

Собственное множество — множество, которое является частью другого и не равно ему. В обоих случаях принято называть множество А подмножеством множества В; в свою очередь, множество В будет надмножеством множества А.

Два множества A и B будут равны, если каждый элемент A будет также являться элементом B, и каждый элемент множества B будет также являться элементом A
A = B
В таком случае можно сказать, что каждое из них будет подмножеством (надмножеством) другого.

Говорят, что множества не пересекаются, если у них нет общих элементов.

Множества A и B находятся в общем положении, если существует элемент (хотя бы один), принадлежащий исключительно множеству A, элемент, принадлежащий исключительно множеству B, а также элемент, принадлежащий обоим множествам.

Операции над множествами

Если имеется два множества или более, то с ними можно выполнить ряд операций. К таким операциям относятся:
- пересечение,
- объединение,
- дополнение,
- разность,
- симметрическая разность.
Все перечисленные операции, кроме дополнения, являются бинарными, т. е. выполняющимися с двумя множествами. Дополнение — унарная операция (выполняемая с одним множеством), которая, однако, может быть осуществлена лишь с учётом всех других множеств, предоставленных по условию задачи: дополнение всегда осуществляется до конкретного множества.
При этом пересечение, объединение и дополнение являются базовыми операциями, через которые могут быть выражены остальные.

Основные понятия теории множеств

Не новость, что информатика неразрывно связана с математикой, и подготовка к сдаче ЕГЭ требует актуализации знаний по многим темам, оказавшимся "на обочине" школьного курса.

В школьном курсе математики отводится очень мало времени на такой обширный и важный раздел, как теория множеств, хотя множества как таковые встречаются довольно часто; в то же время, в рамках ЕГЭ по информатике экзаменуемым предлагается задача, решение которой полностью основано на действиях со множествами.

Рассмотрим основные определения теории множеств.

Теория множеств — это раздел дискретной математики , в котором рассматриваются множества, их свойства и операции над ними.

Само понятие множества вводится аксиоматически и не может быть определено через какие-либо элементарные понятия. Однако мы можем дать описательное определение множества, например, в формулировке Бертрана Рассела:

Множество есть совокупность различных элементов, мыслимая как единое целое.

Согласно Георгу Кантору, под множеством мы понимаем соединение в некое целое M определённых хорошо различимых предметов m нашего созерцания или нашего мышления (которые будут называться элементами множества M).

Из любого определения следует, что все элементы множества различны и уникальны. Если два элемента совпадают, считается, что они представляют собой один  и тот же элемент.