- •Московский государственный институт
- •Лекция 1. Базовые понятия информации Введение
- •Информация, энтропия и избыточность при передаче данных
- •Информационные процессы
- •Основные структуры данных
- •Обработка данных
- •Способы представления информации и два класса эвм
- •Представление данных в эвм.
- •Вопросы и задания
- •Лекция 2. Компьютер – общие сведения
- •Центральное процессорное устройство
- •Устройства ввода/вывода
- •Классификация запоминающих устройств
- •Оперативная память
- •Основные внешние устройства компьютера
- •Основные характеристики персональных компьютеров
- •Вопросы и задания
- •Лекция 3. Многоуровневая компьютерная организация
- •Архитектура компьютера
- •Классическая структура эвм - модель фон Неймана
- •Особенности современных эвм
- •Вопросы и задания
- •Библиотеки стандартных программ и ассемблеры
- •Высокоуровневые языки и системы автоматизированного программирования
- •Диалоговые ос и субд
- •Прикладные программы иCase– технологии
- •Компьютерные сети и мультимедиа
- •Операционные системы
- •Лекция 5.Вычислительные системы - общие сведения Введение
- •Общие требования
- •Классификация компьютеров по областям применения
- •Персональные компьютеры и рабочие станции
- •Суперкомпьютеры
- •Увеличение производительности эвм, за счет чего?
- •Параллельные системы
- •Использование параллельных вычислительных систем
- •Закон Амдала и его следствия
- •Вопросы и задания
- •Лекция 6 Структурная организация эвм - процессор Введение
- •Что известно всем
- •Назначение процессора и его устройство
- •Устройство управления
- •Микропроцессорная память
- •Основная (оперативная) память - структура адресной памяти
- •Интерфейсная часть мп
- •Тракт данных типичного процессора
- •Команды уу
- •Базовые команды
- •Трансляторы
- •Архитектура системы команд и классификация процессоров
- •Микроархитектура процессораPentiumIi
- •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. Система счисления и архитектура эвм Введение
- •Системы счисления и их роль в истории компьютеров
- •«Золотое сечение» и компьютер Фибоначчи
- •Геометрическое определение "золотого сечения"
- •Алгебраические свойства золотой пропорции
- •Рассмотрим теперь "золотую пропорцию"
- •Фибонччи и компьютеры
- •"Троичный принцип" Николая Брусенцова.
- •Список литературы:
Алгебраические свойства золотой пропорции
Что же это за "чудо" природы и математики, интерес к которому не только не увядает с течением времени, а наоборот - возрастает с каждым столетием. Для ответа на этот вопрос мы предлагаем напрячь все математические знания и погрузиться в мир математики - только таким путем вы сможете насладиться чудесными математическими свойствами золотой пропорции и через эти математические свойства понять и оценить всю красоту и гармонию золотой пропорции.
Начнем с алгебраических свойств "золотой пропорции". Из уравнения "золотой пропорции"
непосредственно вытекает первое очень простое и тем не менее весьма удивительное свойство золотой пропорции. Если корень t
подставить вместо xв уравнение (1), то мы получим следующее тождество для "золотой пропорции":
Убедимся, что тождество (2) является истинным. Для этого нам необходимо осуществить элементарные математические преобразования над левой и правой частями тождества (2) и доказать, что они совпадают.
Действительно, мы имеем для правой части:
Тождество (2) может быть представлено в виде:
или
Проанализируем, например, тождество (3-b). Известно, что любое число аимеет обратное к нему число1/а. Например, дробь 0.1 является числом, обратным к 10. Традиционный алгоритм получения обратного числа1/аиз исходного числаасостоит в делении числа 1 на числоа. Это довольно сложная процедура. Попробуйте, например, путем деления получить число, обратное к числуа = 357821,093572. Это можно сделать только с помощью современного компьютера.
Рассмотрим теперь "золотую пропорцию"
Как получить из нее обратное число 1/t? Выражение (3-b) дает очень простой ответ на этот вопрос. Для этого достаточно вычесть единицу из "золотой пропорции" t.
Задача о размножении кроликов
Одним из наиболее известных математиков эпохи Средневековья по праву считается Леонардо Пизано Фибоначчи. Позже мы расскажем о Фибоначчи и его роли в развитии западноевропейской математики более подробно. По иронии судьбы Фибоначчи, который внес выдающийся вклад в развитие математики, стал известным в современной математике только лишь как автор интересной числовой последовательности, называемой числами Фибоначчи. Эта числовая последовательность была получена Фибоначчи при решении знаменитой"задачи о размножении кроликов". Формулировка и решение этой задачи считается основным вкладом Фибоначчи в развитие комбинаторики. Именно с помощью этой задачи Фибоначчи предвосхитилметод рекуррентных соотношений, который считается одним из мощных методов решения комбинаторных задач. Рекуррентная формула, полученная Фибоначчи при решении этой задачи, считается первой в истории математики рекуррентной формулой.
Существо своей "задачи о размножении кроликов" Фибоначчи сформулировал предельно просто:
"Пусть в огороженном месте имеется пара кроликов (самка и самец) в первый день января. Эта пара кроликов производит новую пару кроликов в первый день февраля и затем в первый день каждого следующего месяца. Каждая новорожденная пара кроликов становится зрелой уже через месяц и затем через месяц дает жизнь новой паре кроликов. Возникает вопрос: сколько пар кроликов будет в огороженном месте через год, то есть через 12 месяцев с начала размножения?"
Для решения этой задачи, которая наглядно демонстрируется с помощью рисунка, обозначим черезAпару зрелых кроликов, а черезB- пару новорожденных кроликов. Тогда процесс "размножения" может быть описан с помощью двух "переходов", которые описывают ежемесячные превращения кроликов в процессе размножения:
Заметим, что переход (1) моделирует ежемесячное превращение каждой зрелой пары кроликов А в две пары, а именно в ту же самую пару зрелых кроликов А и новорожденную пару кроликов В. Переход (2) моделирует процесс "созревания" кроликов, когда новорожденная пара кроликов В через месяц превращается в зрелую пару А. Тогда, если мы начнем в первом месяце со зрелой пары А, тогда процесс размножения кроликов может быть представлен с помощью Таблицы 1.
Дата |
Пары кроликов |
A |
B |
A + B |
1-го января |
A |
1 |
0 |
1 |
1-го февраля |
AB |
1 |
1 |
2 |
1-го марта |
ABA |
2 |
1 |
3 |
1-го апреля |
ABAAB |
3 |
2 |
5 |
1-го мая |
ABAABABA |
5 |
3 |
8 |
1-го июня |
ABAABABAABAAB |
8 |
5 |
13 |
Заметим, что в столбцах АиВтаблицы 1 указаны количества зрелых и новорожденных пар кроликов в каждом месяце года, а в таблицеА+В- суммарное количество кроликов.
Изучая последовательности А-,В-и(А+В)-чисел, можно установить следующую закономерность в этих числовых последовательностях:каждый член последовательности равен сумме двух предыдущих. Если теперь обозначитьn-й член последовательности, удовлетворяющей этому правилу черезFn, тогда указанное выше общее правило может быть записано в виде следующей математической формулы:
Fn = Fn-1 + Fn-2 |
(3) |
Такая формула называется рекуррентной формулой.
Заметим, что конкретные значения числовой последовательности, порождаемой рекуррентной формулой (3), зависят от начальных значений последовательности F1иF2. Например, мы имеемF1=F2= 1 дляA-чисел и для этого случая рекуррентная формула (3) "генерирует" следующую числовую последовательность:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... . |
(4) |
Для В-чисел мы имеем:F1= 0 иF2= 1; тогда соответствующая числовая последовательность для этого случая будет иметь вид:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... .
Наконец, для (А + В)-последовательности мы имеем:F1= 1 иF2= 2; тогда соответствующая числовая последовательность для этого случая будет иметь вид:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... .
В математике под числами Фибоначчи, как правило, понимается числовая последовательность (4). Числа Фибоначчи обладают удивительными математическими свойствами
Фибоначчи не стал изучать математические свойства полученной им числовой последовательности
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... . |
(1) |
Это за него сделали другие математики. Начиная с 19 в., математические работы, посвященные свойствам чисел Фибоначчи, по остроумному выражению одного математика "начали размножаться как фибоначчиевые кролики".
Следующая задача, рассмотренная Фибоначчи, называется "задачей о выборе наилучшей системы гирь для взвешивания на рычажных весах" или просто "задачей о гирях". В русской историко-математической литературе "задача о гирях" известна под названием "задачи Баше-Менделеева", названной так в честь французского математика 17 в. Баше де Мезириака, который поместил эту задачу в своем "Сборнике приятных и занимательных задач" (1612 г.) и выдающегося русского химика Дмитрия Ивановича Менделеева, который интересовался этой задачей в бытность директором Главной Палаты мер и весов России.
Суть "задачи Баше-Менделеева" состоит в следующем: при какой системе гирь, имея их по одной, можно взвесить всевозможные грузы Qот 0 до максимального грузаQmax, чтобы значение максимального грузаQmaxбыло бы наибольшим среди всех возможных вариантов? Известно два варианта решения этой задачи: (1) когда гири разрешается класть на свободную чашу весов; (2) когда гири разрешается класть на обе чаши весов.
В первом случае "оптимальная система гирь" сводится к двоичной системе гирь: 1, 2, 4, 8, 16, ..., а возникающий при этом "оптимальный" алгоритм или способ измерения "порождает" классическую двоичную систему счисления, лежащую в основе современных компьютеров.
Во втором случае "оптимальной" является "троичная" система гирь: 1, 3, 9, 27, 81, ..., а возникающий при этом способ измерения "порождает" так называемую троичную симметричную систему счисления, которая была использована в "троичном" компьютере "Сетунь", созданном в 50-е годы в Московском университете.
Методологическое значение "задачи о гирях" состоит прежде всего в том, что она является одной из первых "оптимизационных" задач в истории математики. Во-вторых, она касается "проблемы измерения", то есть одной из фундаментальных проблем математики. В третьих, она связана с проблемой систем счисления, одной из фундаментальных проблем современной информатики. Именно развитие этой задачи с указанных точек зрения привело в последние годы к разработке так называемой "алгоритмической теории измерения", о которой мы расскажем позже.
Но возвратимся снова к Фибоначчи и его сочинениям. Хотя Фибоначчи был одним из наиболее ярких математических умов в истории западно-европейской математики, однако его вклад в математику незаслуженно принижен. Наиболее четко значение математического творчества Фибоначчи для математики подчеркнуто русским математиком проф. А.В. Васильевым в его книге "Целое число" (1919 г.):
"Сочинения ученого пизанского купца были настолько выше уровня математических знаний даже ученых того времени, что их влияние на математическую литературу становится заметным только через два столетия после его смерти в конце 15-го века, когда многие из его теорем и задач вводятся другом Леонардо да Винчи, профессором многих итальянских университетов Лукою Пачиоли в его сочинениях и в начале 16-го века, когда группа талантливых итальянских математиков: Сципион дель Ферро, Иероним Кардано, Тарталия, Феррари решением кубического и биквадратного уравнения положили начало высшей алгебре".
Из этого высказывания вытекает, что Фибоначчи почти на два столетия опередил западно-европейских математиков своего времени. Подобно Пифагору, который получил свое "научное образование" у египетских и вавилонских жрецов и затем способствовал передаче полученных знаний в греческую науку, Фибоначчи получил свое математическое образование в арабских учебных заведениях и многие из полученных там знаний, в частности, арабо-индусскую десятичную систему счисления, он попытался "внедрить" в западно-европейскую науку. И подобно Пифагору историческая роль Фибоначчи для западного мира состояла в том, что он своими математическими книгами способствовал передаче математических знаний арабов в западно-европейскую науку и тем самым заложил основы для дальнейшего развития западно-европейской математики.
В 1958 г. "опыты Фехнера" были повторены английскими учеными. Эти опыты вновь оказались весьма благоприятными для золотого сечения. Большинство испытуемых (35%) без промедления указали на "золотой" прямоугольник 21:34. Соседние к нему фигуры (2:3 и 13:23) также были оценены весьма высоко (20% - верхняя фигура и 19% - нижняя). Все остальные прямоугольники получили не более 10%.
Эти же опыты, проведенные в детской аудитории, дали совершенно иные результаты, не обнаружив чувства гармонии, свойственного взрослым. Отсюда было сделано заключение, что, по-видимому, ощущение прекрасного в его наиболее тонких и глубоких сторонах присуще лишь человеку зрелому.
Мир неживой природы - это прежде всего мир симметрии, придающий его творениям устойчивость и красоту. Мир живой природы - это прежде всего мир гармонии, в которой действует "закон золотого сечения".
В мире неживой природы действует так называемый принцип наименьшего действия. В соответствии с этим принципом система постоянно переходит от менее устойчивого к наиболее устойчивому состоянию. При этом всякое тело стремится принять такую форму, при которой оно обеспечивает минимум энергии его поверхности, совместимую с ориентирующими силами. Симметрия порождающей среды, в которой образуется тело, накладывается на симметрию тела. Получающаяся при этом форма тела сохраняет те элементы собственной симметрии, которые совпадают с наложенными на него элементами симметрии среды.
Принципу наименьшего действия подчиняются все системы неорганического мира. В биологическом и растительном мире это принцип не имеет такого широкого распространения. Любое животное или растение стремятся создать такую морфологическую оболочку, которая бы была благоприятна для размножения и годна для сопротивления условиям среды.
В этом случае вступает в действие принцип экономии материи, который не действует в неорганическом мире. Ярким примером этому служит стремление живых организмов к экономии костной субстанции при распределении материи, дающее максимум прочности во всех нужных направлениях.
Кроме этого, живые организмы проявляют лишь одним им свойственный феномен - феномен роста. Неорганические кристаллы увеличиваются путем присоединения идентичных элементов; живой организм растет путем "всасывания", идущего изнутри и направляющегося наружу.
Мы имеем также еще одно коренное различие: молекулярные элементы неорганической материи, не меняются во все время существования данной совокупности, тогда как элементы, образующие живую ткань, в процессе роста сгорают, удаляются и возобновляются, сохраняя общее начертание формы организма. Например, раковина (внешний скелет морских организмов) растет, сохраняя свою первоначальную форму, несмотря на свой асимметричный рост; рога животных растут только с одного конца.