Конструктивные свойства множеств

Конструктивное понятие множества

Задачи, модели, алгоритмы, программы

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

1. Содержательная задача ® 2. Математическая модель ®

3. Задача на математической модели ® 4. Алгоритм решения задачи ® 5. Программа

На самом деле не всегда получается идеальная цепочка. В реальности всегда приходится возвращаться и уточнять предыдущие этапы. Роль формального описания на каждом этапе (даже на этапе формулирования содержательной задачи) весьма велика. Причина заключается в том, что разработка программ в настоящее время ведется не программистом-одиночкой, а целым коллективом, где для этих целей вырабатывается свой собственный язык описания цепочки. Более того, в конце 90-х годов появился универсальный язык UML (Unitied Modeling Language), который предлагает стандартный подход к прохождению этой цепочки. Необходимо заметить, если до 90-х годов акцент в обучении программированию падал на изучение инструментов (языки программирования, операционные системы, базы данных), то сейчас все больше и больше обращается внимание на первые четыре этапа.

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

Множества в информатике (в отличие от классической математики) требуют уточнения конструктивного характера.

1) Порождающий механизм для каждого элемента множества. Два способа порождения: а) для конечных множеств – перечисление элементов; б) для бесконечных множеств – алгоритм или правила порождения.

2) Каждый элемент множества должен отличаться от другого. Обычно для описания элементов применяется способ кодирования, такой, что код каждого элемента уникален.

Пример 1.1. Множество натуральных чисел – N = {1, 2, 3, …, 437, …, 1521,}. Каждый элемент множества представляет собой код, построенный из алфавита цифр Z = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Известны способы кодирования двоичных и целых чисел (с плавающей запятой, с фиксированной запятой, обратных и дополнительных кодов).

3) Интерпретация множества (элементов множества) суть приписывание некоторого свойства (набора свойств) именно той совокупности элементов, которые объединены в множество.

Продолжение примера 1.1. Множество натуральных чисел, как указывал французский математик Пеано, «имеет счетную природу». Эту природу можно увидеть, если ввести унарный код для описания натуральных чисел N ={I, II, III, IIII, …, IIIIIIIIIIIIIII, …}.Каждое натуральное число кодируется определённым количеством палочек. В этом случае порождающее правило задаётся операцией приписывания «палочки» к предыдущей последовательности «палочек».

Интерпретация множества натуральных чисел в виде свойства «счетности» формально описывается через операцию «прибавления» единицы и распространяется на двоичные коды или кодирование римскими цифрами.

Интерпретация множества четных чисел добавляет к основным свойствам еще свойство деления элементов множества на «два».

Пример 1.2. В множестве групп МФТИ выделяется множество групп ФОПФ, поступивших в 2002 г. = {221, 222, 223, 224, 225, 226…}.Элемент множества – натуральное число, которое выступает только в виде кода, но не обладает всеми свойствами натуральных чисел (эти коды бессмысленно складывать или умножать). Интерпретация кодов известна каждому физтеху, но не студенту МАИ.

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