Фибонччи и компьютеры
Когда мы рассказывали о Фибоначчи, мы подчеркивали, что в своей знаменитой книге "Liber Abaci", опубликованной в 1202 г., он предложил и решил много новых комбинаторных задач. Наиболее известной из них является "задача о размножении кроликов", при решении которой он и пришел к знаменитой числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, ..., прославившей его имя и ставшей объектом интенсивных математических исследований Фибоначчи Ассоциации
Следующая задача, рассмотренная Фибоначчи, называется "задачей о выборе наилучшей системы гирь для взвешивания на рычажных весах". Она также называется "задачей о гирях" или "задачей о взвешивании". История этой задачи такова. Из сочинений Фибоначчи она перекочевала в сочинения еще одного знаменитого итальянского математика Луки Пачиоли, который был "другом и советником Леонардо да Винчи". Лука Пачиоли поместил ее в свою книгу "Summa de Arithmetica, Geomeytria, Proprtioni et Proportionalita", которую он опубликовал в 1494 г. Эта книга по праву считается математической энциклопедией эпохи Возрождения.
В русской историко-математической литературе "задача о гирях" известна также под названием "задачи Баше-Менделеева". О Баше де Мизириаке мы уже рассказывали. Но кто такой Менделеев? Неужели знаменитый русский химик Дмитрий Менделеев, автор Периодического закона. Да, это именно так. Но почему русский химик вдруг заинтересовался "задачей о гирях"? Ответ на этот вопрос дает ознакомление с некоторыми малоизвестными фактами из жизни гениального русского ученого.
Во время происходивших в 1890 г. студенческих волнений в Петербургском университете Менделеев, который в тот период работал профессором этого университета, выступил на защиту студентов и в качестве протеста подал прошение об отставке с должности профессора университета. В 1892 г. Менделеев был назначен ученым хранителем Депо образцовых гирь и весов, которое по инициативе Менделеева в 1893 г. было преобразовано в Главную палату мер и весов России. Ее директором Менделеев оставался до конца жизни. Таким образом, заключительный этап жизни великого ученого (с 1992 г. и до 1907 г.) был связан с развитием измерительного дела и именно в этот период он заинтересовался "задачей о гирях". Под его непосредственным влиянием было выполнены исследования по этой проблеме и было доказано, что оптимальной является троичная система гирь.
Но теперь обратимся к новейшей истории современных компьютеров. В начале 60-х годов 20-го столетия на стыке измерительной и компьютерной техники возникла новая область - техника аналого-цифрового и цифро-аналогового преобразования информации. Основная задача этой техники состояла в создании устройств, обеспечивающих автоматическое преобразование информации из аналоговой, непрерывной формы в дискретную, цифровую форму. Такие устройства получили название непрерывно-дискретных, или аналого-цифровых преобразователей. Таким образом, основным назначением этих устройств является обеспечение связи компьютеров с объектами, в которых информация представлена в непрерывной, аналоговой форме.
Подобно тому, как задачу взвешивания на рычажных весах можно решить, используя различные наборы гирь, задачу аналого-цифрового преобразования можно решить, используя различные способы или алгоритмы аналого-цифрового преобразования. При этом интерес представляют "оптимальные" или наилучшие алгоритмы аналого-цифрового преобразования. Такая проблема, то есть проблема "синтеза оптимальных алгоритмов аналого-цифрового преобразования", и была поставлена в 1963 г. в качестве темы кандидатской диссертации перед молодым исследователем Алексеем Стаховым, аспирантом кафедры технической кибернетики Харьковского института радиоэлектроники.
В кандидатской диссертации Стахова, защищенной в 1966 г., а затем в докторской диссертации "Синтез оптимальных алгоритмов аналого-цифрового преобразования", защищенной в 1972 г., и были изложены результаты новой математической теории аналого-цифрового преобразования, получившей в дальнейшем название "алгоритмической теории измерения".
В 1957 г. американский математик Джордж Бергман ввел в рассмотрение позиционную систему специального типа, названную им "системой счислением с иррациональным основанием" или "Тау-системой". Хотя статья Бергмана содержала результат принципиального значения для теории систем счисления и современной компьютерной науки, однако в то период она просто не была замечена ни математиками, ни инженерами. Более того. И сам автор статьи Джордж Бергман не понял значения своего открытия для дальнейшего развития теории систем счисления и зарождающейся компьютерной техники. В заключение своей статьи он написал:
"Я не знаю никакого полезного приложения для систем счисления, подобных этой, как умственных упражнения и приятного времяпровождения, хотя эта система счисления может быть полезной для алгебраической теории чисел". Более чем 40 лет прошло с открытия Бергмана и, согласно "математической традиции", настало время по достоинству оценить математическое открытие Бергмана.
Удивительные свойства системы счисления Бергмана
Математическое выражение для системы счисления Бергмана имеет следующий вид:
г де A - некоторое действительное число и ai - двоичные цифры, 0 или 1, i = 0, ±1, ±2, ±3, ti - вес i-й цифры в системе счисления (1), t - основание системы счисления (1).
На первый взгляд, не существует никакой особенности в выражении (1) по сравнению с известными позиционными системами счисления, но это только на первый взгляд. Главная особенность состоит в том, что Бергман использовал иррациональное число
( "золотая пропорция") в качестве основания своей системы счисления (1), названной им "тау-системой".
Рассмотрим "тау-систему" с вычислительной точки зрения. Ее основание t определяет все необычные свойства системы счисления (1). Мы знаем из предыдущих страниц Музея, что "золотая пропорция" обладает следующим свойством:
tn = tn-1 + tn-2. | (2) |
Рассмотрим представления чисел в "тау-системе" (1). Ясно, что сокращенная запись числа A в "тау-системе" (1) имеет следующий вид:
A = anan-1 ... a1a0, a-1a-2 ... a-m. | (3) |
Мы можем видеть, что сокращенная запись числа A представляет собой двоичную кодовую комбинацию, разделенную запятой на две части, левую часть anan-1 ... a1a0, соответствующую "весам": tn, tn-1, ..., t1, t0 = 1, и правую часть a-1a-2 ... a-m, соответствующую "весам": t -1, t -2, ..., t -m. Заметим, что "веса" ti (i =0, ±1, ±2, ±3, ...) задаются математической формулой (2).
Например, рассмотрим двоичную кодовую комбинацию 100101. Ясно, что она представляет собой следующее действительное число:
A = 100101 = t5 + t2 + t0. | (4) |
Используя формулу Бине, мы можем поучить, что число A, задаваемое выражением (4), равно:
Я сно, что основание "тау-системы" представляется в ней традиционным образом, то есть:
Н о из нашего предыдущего опыта мы знаем, что невозможно представить иррациональное число с использованием конечного числа цифр. Именно поэтому возможность представления некоторых иррациональных чисел (степеней "золотой пропорции" и их сумм) с использованием конечной совокупности двоичных цифр есть первый неожиданный результат "тау-системы", который противоречит нашим традиционным представлениям о системах счисления.
Возникает вопрос о представлении натуральных чисел в "тау-системе". Для этого рассмотрим еще раз фундаментальное тождество (2). На кодовом уровне оно имеет следующую кодовую интерпретацию:
100 = 011. | (5) |
Как мы можем использовать кодовое преобразование (5)? Для этого мы рассмотрим "золотую" кодовую комбинацию 100101, которая представляет число (4). Если мы используем преобразование (7) к старшим трем разрядам "золотой" кодовой комбинации" 100101, мы получим новое "золотое" представление числа (4), а именно:
A = t5 + t2 + t0 = 100101 = 011101 = t4 + t3 + t2 + t0.
Заметим, что в этом случае степень "золотой пропорции" t5 заменятся на сумму двух предыдущих степеней t4 + t3 в соответствии с фундаментальным соотношением (2). Заметим также, что это не изменяет число (4). На кодовом уровне такое преобразование представляет собой следующее:
100 ® 011. | (6) |
Это кодовое преобразование называется "разверткой". Обратное преобразование
011 ® 100. | (7) |
называется "сверткой".
Таким образом, числа имеют многозначное представление в "тау-системе". Это - второй неожиданный результат, вытекающий из рассмотрения "тау-системы". Используя введенные выше преобразования "свертки" и "развертки", мы можем получить два крайних "золотых" представления одного и того же числа в "тау-системе". Например, рассмотрим кодовую комбинацию 0111111. Если мы выполним в ней все возможные "свертки" (7), то мы получим первое крайнее "золотое" представление, называемое "минимальной формой":
0111111 = 1001111 = 1010011 = 1010100 ("минимальная форма").
Заметим, что в "минимальной форме" двух единиц рядом не встречается.
Рассмотрим теперь "золотую" кодовую комбинацию 100000, которая представляет иррациональное число
В ыполняя в ней все возможные операции "развертки" (6), мы можем получить второе крайнее "золотое" представление, называемое "максимальной формой":
100000 = 0110000 = 0101100 = 0101011 ("максимальная форма").
Заметим, что в "максимальной форме" двух нулей рядом не встречается.
Покажем теперь, как можно получить все "золотые" представления натуральных чисел, используя операции "свертки" и "развертки". Начнем с числа 1. Оно может быть представлено через "золотую пропорцию" следующим способом:
1 = t0.
Но используя "тау-систему" (1), мы можем представить число t0 = 1 следующим образом:
1 = t0 = 1,00. | (8) |
Заметим, что в "золотом" представлении 1,00 запятая отделяет 0-й разряд от разрядов с отрицательными индексами.
Затем, используя "развертку", мы можем представить число (8) следующим образом:
t0 = 1,00 = 0,11 = t -1 + t -2. | (9) |
А теперь добавим бит 1 в 0-й разряд "золотого" представления 0,11. В результате мы получим "золотое" представление числа 2:
2 = 1,11. | (10) |
Применяя операцию "свертки" к старшим разрядам "золотого" представления (10), мы получаем новое "золотое" представление ("минимальную форму") числа 2:
2 = 10,01 = t1 + t -2.
Добавляя бит 1 в 0-1 разряд "золотого" представления числа 2, мы получаем "золотое" представление" числа 3:
3 = 11,01.
Применяя операцию "свертки" к старшим разрядам "золотого" представления числа 3, мы получаем новое "золотое" представление ("минимальную форму") числа 3:
2 = 100,01 = t2 + t -2.
"Золотые" представления чисел 4 и 5 имеют следующий вид:
4 = 101,01 = t2 + t0 + t -2; 5 = 1000,1001 = t3 + t -1 + t -4.
Продолжая этот процесс, можно получить "золотые" представления всех натуральных чисел в "тау-системе". Это означает, что любое натуральное число может быть всегда представлено в виде конечной суммы степеней золотой пропорции! Это утверждение представляет собой наиболее неожиданный результат, вытекающий из рассмотрения "тау-системы".
Основное преимущество кодов Фибоначчи и кодов золотой пропорции для практических применений состоит в их «естественной» избыточности, которая может использована для целей контроля числовых преобразований.
- Лекция 1. Базовые понятия информации Введение
- Информация, энтропия и избыточность при передаче данных
- Информационные процессы
- Основные структуры данных
- Обработка данных
- Способы представления информации и два класса эвм
- Представление данных в эвм.
- Вопросы и задания
- Лекция 2. Компьютер – общие сведения
- Центральное процессорное устройство
- Устройства ввода/вывода
- Классификация запоминающих устройств
- Оперативная память
- Основные внешние устройства компьютера
- Основные характеристики персональных компьютеров
- Вопросы и задания
- Лекция 3. Многоуровневая компьютерная организация
- Архитектура компьютера
- Классическая структура эвм - модель фон Неймана
- Особенности современных эвм
- Специальное
- Библиотеки стандартных программ и ассемблеры
- Высокоуровневые языки и системы автоматизированного программирования
- Диалоговые ос и субд
- Прикладные программы и case – технологии
- Компьютерные сети и мультимедиа
- Операционные системы
- Лекция 5.Вычислительные системы - общие сведения Введение
- Общие требования
- Классификация компьютеров по областям применения
- Персональные компьютеры и рабочие станции
- Суперкомпьютеры
- Увеличение производительности эвм, за счет чего?
- Параллельные системы
- Использование параллельных вычислительных систем
- Закон Амдала и его следствия
- Назначение процессора и его устройство
- Устройство управления
- Микропроцессорная память
- Основная (оперативная) память - структура адресной памяти
- Интерфейсная часть мп
- Тракт данных типичного процессора
- Команды уу
- Базовые команды
- Трансляторы
- Архитектура системы команд и классификация процессоров
- Микроархитектура процессора Pentium II
- 512 Кбайт
- Вопросы и задания
- Лекция 6 Структурная организация эвм - память Общие сведения
- Верхняя
- Верхняя память (Upper Memory Area) – это 384 Кбайт, зарезервированных у верхней границы системной памяти. Верхняя память разделена на несколько частей:
- Первые 128 Кбайт являются областью видеопамяти и предназначены для использовании видеоадаптерами, когда на экран выводится текст или графика, в этой области хранятся образы изображений.
- Видеопамять
- Иерархия памяти компьютера
- Оперативная память, типы оп
- Логическая организация памяти
- Связывание адресов
- Функции системы управления памятью
- Тэг Строка Слово (байт)
- Способы организации кэш-памяти
- 1. Где может размещаться блок в кэш-памяти?
- 2. Как найти блок, находящийся в кэш-памяти?
- 3. Какой блок кэш-памяти должен быть замещен при промахе?
- 4. Что происходит во время записи?
- Разновидности строения кэш-памяти
- Вопросы и задания
- Лекция 7 Логическая организация памяти Введение
- Адресная, ассоциативная и стековая организация памяти
- Стековая память
- Сегментная организация памяти.
- Косвенная адресация
- Операнд 407 суммируется с
- Типы адресов
- Понятие виртуальной памяти
- Страничное распределение
- Свопинг
- Вопросы и задания
- Лекция 8 Внешняя память компьютера Введение
- Жесткий диск (Hard Disk Drive)
- Конструкция жесткого диска
- Основные характеристики нмд:
- Способы кодирования данных
- Интерфейсы нмд
- Структура хранения информации на жестком диске
- Кластер
- Методы борьбы с кластеризацией
- Магнито-оптические диски
- Дисковые массивы и уровни raid
- Лазерные компакт-диски cd - rom
- Вопросы и задания
- Лекция 9 Основные принципы построения систем ввода/вывода
- Физические принципы организации ввода-вывода
- Интерфейс
- Магистрально-модульный способ построения эвм
- Структура контроллера устройства
- Опрос устройств и прерывания. Исключительные ситуации и системные вызовы
- Организация передачи данных
- Прямой доступ к памяти (Direct Memory Access – dma)
- Логические принципы организации ввода-вывода
- Структура системы ввода-вывода
- Буферизация и кэширование
- Заключение
- Структура шин современного пк
- Мост pci
- Вопросы и задания
- Лекция 10. Bios и его настройки Введение
- Начальная загрузка компьютера
- Вход в bios и основные параметры системы
- Общие свойства – стандартная настройка параметров
- Свойства bios
- Свойства других чипсетов
- Свойства интегрированных устройств
- Свойства слотов pci
- Управление питанием
- Лекция 11 Особенности архитектуры современных вс
- Область применения и способы оценки производительности мвс
- Классификация архитектур по параллельной обработке данных
- Вычислительные Системы
- Параллелизм вычислительных процессов
- Параллелизм на уровне команд – однопроцессорные архитектуры
- Конвейерная обработка
- Суперскалярные архитектуры
- Мультипроцессорные системы на кристалле Технология Hyper-Threading
- Многоядерность — следующий этап развития
- Многопроцессорные архитектуры – параллелизм на уровне процессоров
- Векторные компьютеры
- Использование параллельных вычислительных систем
- Закон Амдала и его следствия
- Вопросы и задания
- Лекция 12 Архитектура многопроцессорных вс Введение
- Smp архитектура
- Mpp архитектура
- Гибридная архитектура (numa)
- Организация когерентности многоуровневой иерархической памяти.
- Pvp архитектура
- Кластерная архитектура
- Проблемы выполнения сети связи процессоров в кластерной системе.
- Лекция 13 Кластерные системы
- Концепция кластерных систем
- Разделение на High Avalibility и High Performance системы
- Проблематика High Performance кластеров
- Проблематика High Availability кластерных систем
- Смешанные архитектуры
- Лекция 14 Высокопроизводительные процессоры
- Ассоциативные процессоры
- Конвейерные процессоры
- Матричные процессоры
- Клеточные и днк процессоры
- Клеточные компьютеры
- Трансгенные технологии
- Коммуникационные процессоры
- Процессоры баз данных
- Потоковые процессоры
- Нейронные процессоры
- Искусственные нейронные сети
- Нейрокомпьютеры
- Процессоры с многозначной (нечеткой) логикой
- Лекция 15 Многомашинные системы – вычислительные сети Введение
- Простейшие виды связи сети передачи данных
- Связь компьютера с периферийным устройством
- Связь двух компьютеров
- Многослойная модель сети
- Функциональные роли компьютеров в сети
- Одноранговые сети
- Сети с выделенным сервером
- Гибридная сеть
- Сетевые службы и операционная система
- Лекция 16. Файловая система компьютера Введение
- Общие сведения о файлах
- Типы файлов
- Атрибуты файлов
- Организация файлов и доступ к ним
- Последовательный файл
- Файл прямого доступа
- Другие формы организации файлов
- Операции над файлами
- Директории. Логическая структура файлового архива
- Разделы диска. Организация доступа к архиву файлов.
- Операции над директориями
- Защита файлов
- Контроль доступа к файлам
- Списки прав доступа
- Заключение
- Лекция 17. Сети и сетевые операционные системы Введение
- Для чего компьютеры объединяют в сети
- Сетевые и распределенные операционные системы
- Взаимодействие удаленных процессов как основа работы вычислительных сетей
- Основные вопросы логической организации передачи информации между удаленными процессами
- Понятие протокола
- Многоуровневая модель построения сетевых вычислительных систем
- Проблемы адресации в сети
- Одноуровневые адреса
- Двухуровневые адреса
- Удаленная адресация и разрешение адресов
- Локальная адресация. Понятие порта
- Полные адреса. Понятие сокета (socket)
- Проблемы маршрутизации в сетях
- Связь с установлением логического соединения и передача данных с помощью сообщений
- Синхронизация удаленных процессов
- Заключение
- Лекция 18. Система счисления и архитектура эвм Введение
- Системы счисления и их роль в истории компьютеров
- «Золотое сечение» и компьютер Фибоначчи
- Геометрическое определение "золотого сечения"
- Алгебраические свойства золотой пропорции
- Рассмотрим теперь "золотую пропорцию"
- Фибонччи и компьютеры
- "Троичный принцип" Николая Брусенцова.
- Список литературы: