Связь информатики и алгебры

Взаимосвязь математики и информатики

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

• алгебра логики;
• системы счисления;
• теория вероятностей и математическая статистика;
• теория графов;
• теории языков и трансляций;
• теория множеств;
• теория алгоритмов.

Рассмотрим особенности алгебраического и информационного подходов на примерах систем счисления и теории алгоритмов.

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

Десятичное счисление, используемое людьми в повседневной деятельности, возникло потому, что 10 пальцев на руках оказались на ранних этапах развития человечества удобным средством счета. Следует отметить, что уже в древности и Средневековье использовались и другие системы счисления, в частности, двенадцатиричная: купцам было удобно считать дюжинами, т.е. используя как основание системы счисления число 12, поскольку это число легко делится на 2, 3, 4, и 6. От двенадцатиричной системы счисления во многих языках остались специальные числительные (eleven и twelve в английском, elf и zwolf в немецком).

Рисунок 1. Двенадцатиричная система счисления. Автор24 — интернет-биржа студенческих работ

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

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

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

Алгоритмы в алгебре и информатике

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

Рисунок 2. Деление в столбик - пример математического алгоритма. Автор24 — интернет-биржа студенческих работ

Математику интересует всё разнообразие способов решить ту или иную задачу, в том числе те, которые не всегда дают правильный результат (для частных случаев), или не имеют решения. Например, существуют десятки алгоритмов для нахождения площади прямоугольного треугольника (теорема Пифагора). Среди них не только арифметические, но и графические, и основанные на физических моделях.

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

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

• слиянием,
• вставками,
• выбором,
• пузырьковая и т.д.

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

Рисунок 3. Сравнение алгоритмов сортировки с точки зрения эффективности. Автор24 — интернет-биржа студенческих работ