Введение. Предмет информатики.

Вычислительная техника и информационные технологии сейчас являются неотъемлемой частью жизни. Персональные компьютеры, мобильные телефоны, сеть Интернет – вам, конечно, знакомы все эти вещи.

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

Теоретические основы информатики нужны не только в качестве исторической справки. Нередко при разработке программного обеспечения, крайне важным оказывается понимание принципов, на которых построены современные вычислительные машины. Непонимание этих принципов может приводить к неожиданным и неприятным сюрпризам.

Сама по себе наука информатика – это наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации. Темы, которыми занимается информатика, включают теорию вычислимости (что можно и что нельзя реализовать в программах), теорию сложности вычислений (как наиболее эффективно решить ту или иную вычислительную задачу), структуры и базы данных (как эффективно хранить и получать информацию), и т.д.

Теоретические основы лежат в основном в области математики. Именно на них сосредоточим свое внимание.

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

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

Использование арабской системы в счетных машинах представляет некоторые трудности. Первые счетные машины были механическими (т.н. арифмометры), и использовали именно арабскую систему счисления. В качестве ранних примеров можно привести:

• Суммирующая машина Паскаля – 1642 г.
• Счетная машина Лейбница – 1673 г.
• Аналитическая машина Бэббиджа – 1848 г.

Последняя являлась универсальной вычислительной машиной, прототипом современных ЭВМ, однако так и не была построена. Впрочем, если бы она была построена, она была бы огромна и требовала бы парового движителя для своей работы.

Принципы, заложенные Бэббиджем, однако, не пропали. В 1937 году немецкий студент Конрад Цузе построил арифмометр, основанный на проекте Бэббиджа, однако использующий двоичную систему счисления. Использование двоичной системы оказалось гениальным ходом – арифмометр Цузе умещался на столе. Считается, что именно использование двоичной системы принесло Цузе успех там, где Бэббидж потерпел неудачу.

Позже, в 1941 году, Цузе создал аналогичную счетную машину на телефонных реле, что стало прообразом первых ЭВМ.

На этом закончим исторический экскурс, и попробуем разобраться, что же такое система счисления.

Позиционные системы счисления. Основные определения.

Система счисления или нумерация

способ записи чисел

Цифры

символы, при помощи которых записываются числа

Алфавит системы счисления

совокупность цифр, используемых в данной системе счисления

Размерность системы счисления

количество цифр в алфавите системы счисления

Позиционная система счисления

такая система счисления, в которой количественный эквивалент цифры зависит от ее положения в записи числа

Арабская десятичная система счисления является позиционной: значения цифр умножаются на “веса” соответствующих разрядов. Например, \(8347 = 8\cdot 1000 + 3\cdot 100 + 4\cdot 10 + 7\cdot 1\).

Базис позиционной системы счисления

Последовательность чисел, каждое из которых задает количественный эквивалент соответствующего разряда

Основным достоинством практически любой позиционной системы счисления является возможность записи любого числа при помощи конечного набора цифр.

Традиционная система счисления

позиционная система счисления, базис которой образуют члены геометрической прогрессии, а значения цифр есть целые неотрицательные числа

Базис десятичной системы счисления образуется геометрической прогрессией со знаменателем \(10\), двоичной и восьмеричной, соответственно, \(2\) и \(8\).

Основание традиционной системы счисления

знаменатель геометрической прогрессии, члены которой образуют базис системы счисления

Традиционные системы счисления иначе называют P-ичными. Например, двоичная, третичная, четвертичная, пятиричная, и т.п.

В P-ичных системах размерность алфавита равна основанию.

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

Основанием P-ичной системы счисления может быть любое натуральное число большее 1.

Для однозначного определения позиционной системы счисления необходимо и достаточно указать ее базис.

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

Что касается алфавита систем счисления, условимся, что для первых 10 символов мы используем арабские цифры 0, 1, … 9. Для следующих – латинские буквы A, B, C, …, Z. Для всех остальных, если понадобится, будем указывать десятичный номинал числа в квадратных скобках, например, [42].

Единственность представления чисел в P-ичных системах счисления

Если одно и то же целое число можно представить в P-ичной системе счисления несколькими способами, это не кажется слишком удобным. Однако, сделать этого нельзя. Покажем это.

Теорема о единственности представления чисел в P-ичной системе счисления

Пусть \(P\in \mathbb{N}\) и \(P>1\). Тогда \(\forall X \in \mathbb{N},\, \exists!\) представление вида \[X = \sum_{i=0}^n a_i P^i,\] причем \(a_n\neq 0\), \(0\leq a_i < P\)

Доказательство

Сначала докажем существование по методу индукции.

1. Базис индукции. Существует представление \(1 = 1\).

2. Предположение индукции. Пусть существует представление \(X = \sum_{i=0}^n a_i P^i,\) удовлетворяющее условиям теоремы.

3. Докажем, что существует представление \(X + 1 = \sum_{i=0}^m b_i P^i,\) которое так же удовлетворяет условиям теоремы.

   По предположению индукции, \[ X + 1 = \sum_{i=0}^n a_i P^i + 1\]

   Тогда \[ \sum_{i=0}^n a_i P^i + 1 = \sum_{i=0}^m b_i P^i\]

   Рассмотрим случай \(a_0 < P-1\). Тогда \[ a_n P^n + a_{n-1} P^{n-1} + \ldots + a_1 P^1 + a_0 + 1 = b_m P^m + b_{m-1} P^{m-1} + \ldots + b_1 P^1 + b_0\] По методу неопределенных коэффициентов, \(b_0 = a_0+1\), \(b_i = a_i\), \(0 \leq b_i < P\), \(m=n\), \(a_n\neq 0 \Rightarrow b_m\neq 0\).

   Рассмотрим случай \(a_0 = P-1\). Тогда \[ a_n P^n + a_{n-1} P^{n-1} + \ldots + a_1 P^1 + P-1 + 1 = b_m P^m + b_{m-1} P^{m-1} + \ldots + b_1 P^1 + b_0\] \[ a_n P^n + a_{n-1} P^{n-1} + \ldots + (a_1+1) P^1 = b_m P^m + b_{m-1} P^{m-1} + \ldots + b_1 P^1 + b_0\] По методу неопределенных коэффициентов, \(b_0 = 0\).

   Рассмотрим случай, когда \(a_1<P-1\). Тогда, по аналогии, \(b_1 = a_1+1\), \(b_i = a_i\), \(0 \leq b_i < P\), \(m=n\), \(a_n\neq 0 \Rightarrow b_m\neq 0\).

   Иначе, если \(a_1 = P-1\), то \[ a_n P^n + a_{n-1} P^{n-1} + \ldots + (P-1+1) P^1 = b_m P^m + b_{m-1} P^{m-1} + \ldots + b_1 P^1\] \[ a_n P^n + a_{n-1} P^{n-1} + \ldots + (a_2+1) P^2 = b_m P^m + b_{m-1} P^{m-1} + \ldots + b_1 P^1\]

   По методу неопределенных коэффициентов, \(b_1 = 0\).

   Рассуждая далее по аналогии, либо \(\exists k\leq n: a_k<P-1, \forall i<k:\: a_i=P-1\), либо \(\forall i\in[0,n],\, a_i=P-1\).

   В первом случае имеем: \[ a_n P^n + \ldots + (a_k+1) P^k = b_m P^m + b_{m-1} P^{m-1} + \ldots + b_0,\] и по методу неопределенных коэффициентов, \(\forall i\in [0,k-1]:\: b_i = 0;\) \(b_k = a_k+1;\) \(\forall i\in [k+1,n]: b_i = a_i;\) \(m=n\) – удовлетворяет условиям теоремы.

   Во втором случае \[ P P^n = b_m P^m + b_{m-1} P^{m-1} + \ldots + b_0\] \[ P^{n+1} = b_m P^m + b_{m-1} P^{m-1} + \ldots + b_0\] По методу неопределенных коэффициентов, \(\forall i\in[0,n]:\:b_i=0;\) \(b_m=1;\) \(m=n+1\).

Существование доказано.

Докажем единственность от противного.

Предположим, что существует два представления \[X_1 = \sum_{i=0}^n a_i P^i\] \[X_2 = \sum_{i=0}^m b_i P^i\] \[ X_1 = X_2 \]

Для начала покажем, что, если \(m>n\), то \(X_2 > X_1\). Для этого оценим \(X_2\) снизу наименьшим возможным числом: \(b_m=1\), \(b_{i\neq m} = 0\). С другой стороны, оценим \(X_1\) сверху наибольшим возможным числом: \(a_i = P-1\). Получим:

\[X_1 \leq (P-1) \sum_{i=0}^n P^i\] \[X_2 \geq P^m\]

По формуле первых n членов геометрической прогрессии, \[\sum_{i=0}^n q^n = \frac{q^{n+1}-1}{q-1}\]

\[ \sum_{i=0}^n P^i = \frac{P^{n+1}-1}{P-1},\] Тогда \[X_1 \leq P^{n+1}-1 < P^{n+1}\]

Если \(m>n\), то \(P^m \geq P^{n+1}\), и, следовательно, \(X_2 > X_1\), что противоречит предположению \(X_2 = X_1\). Следовательно, \(m=n\).

Пусть теперь \(\exists k: \forall i\in [n,k-1],\, a_i=b_i, a_k\neq b_k\). Оценим разность \(X_1 - X_2\) по модулю снизу.

\[ | X_1 - X_2 | = | \sum_{i=0}^{k} (a_i-b_i) P^i | \geq |a_k-b_k| P^k - \sum_{i=0}^{k-1} |a_i-b_i| P^i.\]

Пусть \(|a_k-b_k| = 1\) (минимально), а \(|a_{i<k}-b_{i<k}| = P-1\) (максимально). Тогда

\[ |a_k-b_k| P^k - \sum_{i=0}^{k-1} |a_i-b_i| P^i \geq P^k - (P-1)\sum_{i=0}^{k-1} P^i\] \[ P^k - (P-1)\sum_{i=0}^{k-1} P^i = P^k - (P^k - 1) = 1\]

Получаем, что \(| X_1 - X_2 | \geq 1,\) следовательно, \(X_1 \neq X_2\). Мы пришли к противоречию, следовательно, \(\forall i: a_i = b_i\), и, значит, представления \(X_1\) и \(X_2\) эквивалентны. \(\blacksquare\)

В теории чисел так же доказывается другая теорема: любое неотрицательное вещественное число можно представить (не обязательно единственным образом) в виде \[ X = \sum_{i=-\infty}^n a_i P^i. \]

Пример неоднозначного представления вещественных чисел можно привести, используя десятичные периодические дроби: \(0,1(9) = 0,2\). Можете доказать это утверждение самостоятельно (подсказка: использовать разложение в степенной ряд и формулу суммы бесконечно убывающей геометрической прогрессии)

Числа, представление которых содержит отрицательные степени основания системы счисления \(P\) будем называть P-ичными дробями.

Представление чисел в позиционных системах счисления.

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

Развернутая форма записи числа

запись числа в виде степенного ряда по степеням числа P.

Свернутая форма записи числа

запись подряд коэффициентов разложения с указанием P в виде индекса.

Рассмотрим разложение числа 14 в ряд по степеням двойки:

\[ 14 = 8 + 4 + 2 = 1\cdot 2^3 + 1\cdot 2^2 + 1\cdot 2^1 + 0 \cdot 2^0 \]

Мы можем записать это разложение в свернутом виде: \(1110_2\). Мы получили двоичную запись числа 14, или, для краткости, двоичное число¹. Аналогично можно получить P-ичную запись любого числа.

Следует оговориться, что “14” в данном случае – десятичная запись, и вообще следовало бы указать это: \(14_{10}\). Для простоты, условимся, что если число указано без индекса, подразумевается десятичная запись, если явно не указано иное.