Основные этапы развития информационных технологий.

Основные этапы развития информационных технологий.

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

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

2. Появление речи - самого совершенного в живой природе способа обмена информацией (1 000 000 лет назад).

3. Появление письменности - способа долговременного хранения информации (30 000 лет назад).

4. Изобретение книгопечатания - способа тиражирования информации (середина XV века).

5. Развитие средств механизации и автоматизации обработки информации (с начала XVI века).

a. 1500 г., Леонардо да Винчи, эскиз суммирующего устройства

b. 1623 г., Вильгельм Шиккард, действующее суммирующее устройство

c. 1641-1645 г.г., Блез Паскаль, суммирующая машина

d. 1671-1674 г.г., Готфрид Лейбниц, арифмометр

e. 1801-1808г.г., Жозеф Жаккард, автоматический ткацкий станок

f. 1822 г. Чарльз Бэббидж, описание "разностной" машины

g. 1834 г., Чарльз Бэббидж, эскиз "аналитической" машины

h. 1843 г., Ада Лавлейс, основы программирования, первая в мире программа для аналитической машины Беббиджа (расчет чисел Фиббоначи)

i. 1887 г., Герман Холлерит, первый табулятор

j. 1897 г., Герман Холлерит, основание фирмы Tabulating Machine Company, впоследствии IBM (International Business Machines)

Программа представляет собой план выполнения действий, записанный в специальной, понятной исполнителю действий форме.

6. Электромеханические машины (конец XIX века).

a. 1939-1941 г.г., Конрад Цузе, Германия, машина "Z-3", память - 64 числа, сложение 0,3 секунды, умножение 5 секунд.

b. 1937-1944 г.г., Говард Айкен, фирма IBM, механическая машина "Марк-1",

c. 1947 г., Говард Айкен, фирма IBM, электромеханическая машина "Марк-2", умножение 0,7 секунд

d. 1957 г., Н. И. Бессонов, СССР, электромеханическая машина "РВМ-1", умножение за 0,05 с., лучшая в мире релейная машина

7. Электронные вычислительные машины (ЭВМ) или компьютеры, середина XX века

e. 1937-1942 г.г., Дж. Атанасов и К. Берри, США, первая полностью электронная машина "ABC" (Atanasoff-Berry Computer), 600 электронных ламп накаливания. Только операции сложения и вычитания.

f. 1943-1945 г.г. Пенсильванский университет, США, Д. Мочли и П. Эккерт, ENIAC - Electronic Numerical Integrator And Computer, вес 30 тонн, высота 6 метров, площадь120 м2 , 18 тысяч электронных ламп накаливания, 5 тысяч операций в секунду

g. 1944-1945 г.г. Джон фон Нейман, принципы разработки и функционирования ЭВМ

h. 1949 г. М. Уилкс, Великобритания, первая электронная машина с хранимой программой "EDSAC" (Electronic Delay Storage Automatic Calculator). С этой машины принято вести отсчет первого поколения компьютеров.

i. 1947-1951 г.г., С.А. Лебедев, СССР, машина МЭСМ

j. Середина .60 годов - появление науки информатика.

8. Переход человеческой цивилизации в информационный этап развития (конец XX - начало XXI века)

k. 1974 г., первый персональный компьютер Altair 8800.

l. 1969 г., первые элементы будущей глобальной сети Internet.

m. 1981 г., первый персональный компьютер модели IBM PC

n. 2003 г., суперЭВМ Cray X1 - 52 триллиона операций в секунду

o. 2006 г., суперЭВМ Blue Gen/L - 280 триллионов операций в секунду

Характеристики способов построения двоичных кодов. Примеры кодов.

Определяющие характеристики способов кодирования:

1. длительность (одинаковая или разная) элементарных сигналов, которые соответствуют знакам 0 и 1;

2. длина кода (одинаковая или разная) для разных знаков первичного алфавита (равномерный и неравномерный коды).

3. выделение отдельного кода для каждого знака первичного алфавита (алфавитное кодирование) или возможны коды для сочетаний знаков (блочное кодирование).

Коды Хемминга.

Принцип построения кодов Р. Хемминга (1948 г.).

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

2. Контрольные биты располагаются в позициях с номерами n=2 , k=0,1,2,3 ,…;

3. Для каждого контрольного разряда с номером n весь код делится на группы, состоящие из 2хn битов.

4. Контрольный бит с номером n контролирует в группе первые n подряд расположенных битов кода (для первой группы включая контрольный) с пропуском следующих n битов.

В общем случае информационный бит с номером b проверяется контрольными битами с номерами , такими, что

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

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

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

Для обнаружения k ошибок, необходим код с полным интервалом d=k+1, а для исправления k ошибок, необходим код с полным интервалом d=2k+1.

Разрядность кодов Хемминга для исправления одиночных ошибок

Для заданного допустимого кода разрядности m существует ровно n=m+r кодов с единственной ошибкой и n+1 кодов с не более чем одной ошибкой. Всего допустимых кодов . Всего кодов с не более чем одной ошибкой 2m(n+1). Должно выполняться неравенство

Классификация моделей.

Классификацией называется распределение рассматриваемых объектов по группам в соответствии с выбранными признаками, свойствами.

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

Классификация может быть представлена в виде графа (чертежа), в виде таблицы, списка или группы списков.

Натурные модели

Натурные модели представляют собой материальные объекты, которые адекватно отображают выбранные свойства объекта, предметной области.

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

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

Математические модели

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

Математическая модель (в узком смысле, с точки зрения математики) - это одно или несколько множеств элементов произвольной природы, на которых определено конечное множество отношений.

Структурные модели

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

Функциональные модели

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

Имитационные модели

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

Классификация систем.

Система называется статической если множество компонентов, из которых она состоит, множество их свойств и взаимосвязей, а также множество системных свойств не изменяется с течением времени.

Любое изменение указанных множеств считается процессом, происходящим в системе, а сама система становится динамической.

Статическую систему можно рассматривать как мгновенное состояние динамической системы.

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

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

Различают естественные, искусственные и информационные системы. Естественные и искусственные системы материальны, информационные системы нематериальны.

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

Машина Поста.

Машина Поста представляет собой идеальное, воображаемое устройство, состоящее из неограниченной в обе стороны ленты и каретки, способной перемещаться вдоль ленты. Лента разбита на клетки. Любая клетка может быть отмеченной или нет. За один шаг каретка может переместиться на одну клетку вправо или на одну клетку влево. Каретка может определить отмечена текущая клетка или нет, а также поставить в текущую клетку отметку или же стереть её.

Машина Поста задается:

1.начальным распределением отмеченных клеток;

2.начальным положение каретки;

3.программой, определяющей последовательность действий каретки.

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

Структура команды машины Поста:

<порядковый номер команды>. <операция> <номер следующей команды>

Невыполнимые команды:

Ø стереть отметку, если текущая клетка не отмечена;

Ø поставить отметку, если текущая клетка уже отмечена.

Выполнение программы может:

Ø не завершится никогда (безостановочная работа);

Ø завершится безрезультатно на невыполнимой команде;

Ø завершится результативно на команде Стоп.

Требование к программе машины Поста

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

2. Используемые в командах номера должны обозначать присутствующие в программе команды.

Основные типы алгоритмов.

Линейные алгоритмы. Отличительным свойством линейных алгоритмов является выполнение этапов алгоритма в той последовательности в которой они заданы в алгоритме, без каких-либо условий и повторов.

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

Циклы. Отличительным свойством является наличие этапа или группы этапов алгоритма, которые выполняются неоднократно.

51. Способы задания алгоритмов. Алгоритмические языки.

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

Словесный способ задания алгоритма состоит в его формулировке средствами естественного языка - русского, английского, китайского и т.д. Основное достоинство способа: наиболее приемлемая для человека, естественная форма. Важнейший недостаток - неоднозначность конструкций, предложений, слов естественного языка.

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

Блок-схемой называется графическое изображение структуры алгоритма. Блок –схема представляет собой группу геометрических фигур строго определенного начертания, соединенных стрелками. Каждая фигура изображает некоторое действие, а стрелки, соединяющие фигуры, определяют последовательность действий. Основными достоинствами этого способа является его простота, гибкость, высокая степень наглядности. Однако, задание достаточно сложных алгоритмов на этом уровне затруднено из-за существенно возрастающей громоздкости. Кроме того, алгоритмы, заданные в таком виде непосредственно не воспринимаются компьютером.

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

Присваивание.

Действие присваивания состоит в закреплении за переменной нового текущего значения. Присваивание выполняется независимо от наличия или отсутствия старого текущего значения.

<Имя переменной> : = <Правило определения нового значения>

Порядок выполнения присваивания

1. Вычисляется значение выражения в правой части.

2. При необходимости определяется компонент значения в левой части.

3. Вычисленное значение закрепляется за переменной или компонентом.

В действии присваивания необходимо различать два состояния:

1. до начала действия переменная имеет старое значение или не имеет никакого;

2. после завершения действия переменная имеет новое текущее значение.

Правила задания присваивания

1. Тип переменной в левой части и тип значения в правой должны соответствовать друг другу, например, совпадать. Имеются и другие случаи соответствия, зависящие от используемого языка программирования.

2. Все переменные в правой части должны иметь типы, обеспечивающие возможность вычисления значения выражения.

3. Все переменные, используемые в правой части, а также в индексных выражениях должны быть определены к моменту выполнения присваивания.

Присваивание это действие, в котором переменная изменяет значение, сравнение это операция, которая не изменяя значений устанавливает факт равенства или не равенства правой и левой частей.

В операции сравнения левая и правая части равноправны, а в действии присваивания - не равноправны. В присваивании выражение слева писать нельзя, а в сравнении - можно.

Бинарный поиск.

Если данные упорядочены, то поиск можно сделать значительно более эффективным. Если x[i]<=x[i+1], i=1,2,…,N-1, то массив называется упорядоченным (отсортированным) по возрастанию.

Искомый элемент сравнивается со средним элементом массива.

Если они совпадают, то задача уже решена. Так как массив упорядочен, то при не совпадении элементов, в дальнейшем поиске можно не рассматривать одну из половин массива.

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

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

Итак, во время поиска приходится повторять следующие действия: 1) выбирать средний элемент массива; 2) сравнивать его с искомым; 3) при необходимости уменьшать рассматриваемую часть массива в два раза выбором его правой или левой половины.

Так как начальный и конечный элементы рассматриваемой части массива при отбрасывании одной из половин массива будут изменяться, то для записи алгоритма следует использовать переменные, имеющие смысл номеров начального (левого) L и конечного (правого) R элементов массива. Поскольку в начале рассматривается весь массив, то L=1, а R=N. Номер среднего элемента M можно найти стандартным способом: M=(R+L) div 2.

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

На первом шаге количество K рассматриваемых элементов массива равно N

После первого шага количество K рассматриваемых элементов массива уменьшается в два раза K=N/2.

После второго шага - в четыре раза

Вообще, после шага с номером m:

В худшем случае процесс поиска закончится после того, как останется один элемент: . Отсюда:

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

Построение кратных циклов.

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

Понятие подпрограммы.

Описанием подпрограммы называется поименованная часть алгоритма (программы), которая может быть использована для выполнения описанных в ней действий неоднократно, как в рамках одного и того же алгоритма (программы), так и в разных алгоритмах (программах).

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

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

Итерация и рекурсия.

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

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

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