17. Какие существуют способы представления алгоритма?

 Существуют следующие формы представления алгоритма:    • словесная (текстуальная) (для достаточно сложных алгоритмов описание становится слишком громоздким и ненаглядным, вследствие этого такая форма представления обычно используется лишь на начальных стадиях разработки алгоритма);    • графическая (форма представления алгоритмов является более компактной и наглядной: алгоритм изображается в виде последовательности связанных между собой блоков (символов), каждый из которых соответствует выполнению одного или нескольких операторов, такое графическое представление называется блок-схемой алгоритма);    • на языках программирования (алгоритм, записанный на языке программирования, называется программой).

18. Какие вы знаете основные структуры алгоритмов?

Базовые(основные) структуры алгоритмов — это определенный набор блоков и стандартных способов их соединения для выполнения типичных последовательностей действий.

К основным структурам относятся следующие:

• линейные

• разветвляющиеся

• циклические

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

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

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

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

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

Вопросы для повторения 3:

1.

Домеханический этап  Ручной период автоматизации вычислений начался на заре человеческой цивилизации и базировался на использовании частей тела,  Суань-пань в первую очередь пальцев рук и ног.  Пальцевый счет уходит корнями в глубокую древность, встречаясь в том или ином виде у всех народов и в наши дни. Конечно, счёт был примитивным, а уровень абстракции очень низким. Понятие числа максимально конкретно, оно неразрывно связано с предметом (т.е. это, например, не число «два», а «две рыбы», «два коня» и т.д.). Диапазон счёта невелик. Можно выделить три типа таких счётных приспособлений. Искусственные приспособления: зарубки (насечки) на различных предметах, в Южной Америке получают широкое распространение узелки на верёвках. Предметный счёт, когда используются предметы типа камешков, палочек, зёрен и т.д. Часто этот тип счёта использовался вместе с пальцевым. Счёт с помощью предметов был предшественником счёта на абаке - наиболее развитом счётном приборе древности, сохранившем некоторое значение в настоящее время (в виде русских счётов, китайского суань-паня и др.). Под абаком понимается счётный прибор, на котором отмечены места (колонки или строчки) для отдельных разрядов чисел. Механический этап  Леонардо да Винчи (Leonardo da Vinci, 1452–1519) Под механическим вычислительным устройством понимается устройство, построенное на механических элементах и обеспечивающее автоматическую передачу из низшего разряда в высший. Один из первых арифмометров, точнее «суммирующая машина», был изобретен Леонардо да Винчи (Leonardo da Vinci, 1452–1519) около 1500 года. Правда, о его идеях никто не знал на протяжении почти четырех столетий. Рисунок этого устройства был обнаружен только в 1967 году, и по нему фирма IBM воссоздала вполне работоспособную 13-разрядную суммирующую машину, в которой использован принцип 10-зубых колес.  Десятью годами раньше в результате исторических изысканий в Германии были обнаружены чертежи и описание арифмометра, выполненные в 1623 году Вильгельмом Шиккардом (Wilhelm Schickard, 1592–1636), профессором математики университета в Тюбингене. Это была весьма «продвинутая» 6-разрядная машина, состоявшая из трех узлов: устройства сложения-вычитания, множительного устройства и блока записи промежуточных результатов. Если сумматор был выполнен на традиционных зубчатых ко-лесах, имевших кулачки для передачи в соседний разряд единицы переноса, то множитель был построен весьма изощренно. В нем немецкий профессор применил метод «решетки», когда при помощи «насаженной» на валы зубчатой «таблицы умножения» происходит перемножение каждой цифры первого сомножителя на каждую цифру второго, после чего со сдвигом складываются все эти частные произведения.  Блез Паскаль (Blaise Pascal, 1623–1662) Эта модель оказалась работоспособной, что было доказано в 1957 году, когда она была воссоздана в ФРГ. Однако неизвестно, смог ли сам Шиккард построить свой арифмометр. Есть свидетельство, содержащееся в его переписке с астрономом Иоганном Кеплером (Johannes Kepler, 1571–1630) относительно того, что недостроенная мо-дель погибла в огне во время пожара в мастерской. К тому же автор, вскоре скончавшийся от холеры, не успел внедрить в научный обиход сведения о своем изобретении, и о нем стало известно лишь в середине ХХ века.  Поэтому Блез Паскаль (Blaise Pascal, 1623–1662), который первым не только сконструировал, но и построил работоспособный арифмометр, начинал, как говорится, с ну-ля. Блистательный французский ученый, один из создателей теории вероятностей, автор нескольких важных математических теорем, естествоиспытатель, открывший атмосферное давление и определивший массу земной атмосферы, и выдающийся мыслитель, был в повседневной жизни любящим сыном президента королевской палаты сборов. Девятнадцатилетним юношей, в 1642 году, желая помочь отцу, тратившему много времени и сил, составляя финансовые отчеты, он сконструировал машину, которая могла складывать и вычитать числа. 

2.

Выделяют четыре этапа развития вычислительной техники:

• Домеханический — с 40—30-го тысячелетия до н. э.

• Механический — с середины XVII в.

• Электромеханический — с 90-х годов XIX в.

• Электронный — со второй половины 40-х годов XX в.

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

• устройства ввода-вывода: бумажная перфолента, перфокарты, магнитная лента, и печатающие устройства;

• внешняя память: магнитный барабан, перфоленты, перфокарты;

• пультовая работа программиста;

• программирование в машинных кодах.

ENIAC(Electronic Numerical Integrator and calculator)-Эта первая универсальная машина разработана в 1940г. в Пенсильванском университете, закончена к 1946г. Назначение: для военных баллистических расчетов, однако после завершения активно использовалась в научных целях.Руководители проекта: Джон Моучли, инженер Дж.ЭккертЗанимала комнату 10*15 кв.м, 18000 эл. ламп, 1500 реле, мощность 150Квт. За секунду выполняла 5000 сложений или 300 умножений.

МЭСМ (Малая Электронно - Счетная Машина ) .МЭСМ- 1947-51гг., Киев, руководитель проекта - академик Сергей Алексеевич Лебедев. Работала с 20-ти разрядными числами, со скоростью 50 операций в секунду. Объем памяти - 100 ячеек. Превосходила по своим характеристикам многие зарубежные образцы. Задачи решались в основном вычислительного характера, содержащие сложные расчеты, необходимые для прогноза погоды, решения задач атомной энергетики, управления летательной техникой и других стратегических задач.

2 поколение.1 июля 1948г. Bell Telefon Laboratory объявила о создании первого транзистора (первая демонстрация была еще раньше — в 1947г). Его разработали американские физики У. Браттейн, Бардин, У.Шокли.

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

Дополнительные черты:

• Внешняя память: магнитный барабан, перфоленты, перфокарты

• Пультовая или пакетная работа программиста

• Появление мониторов и первых операционных систем

• Программирование в машинных кодах и на первых языках программирования(FORTRAN, ALGOL).

3-е поколение .Особенностью ЭВМ 3 поколения считается применение в их конструкции интегральных схем, а в управлении работой компьютера — операционных систем. Появились возможности мультипрограммирования, управления памятью, устройствами ввода-вывода. Восстановление после сбоев взяла на себя операционная система.

Дополнительные черты:

• мощные операционные системы

• развитые системы программного обеспечения для числовых и текстовых приложений

• возможность ограниченного диалога с программистом

• возможность удаленного, коллективного доступа

IBM SYSTEM 360(IBM CORP) — знаменитое семейство машин, программно совместимых снизу вверх. Машины примерно одинаковой архитектуры, но самых разных рабочих и стоимостных характеристик. До конца 70-х годов этот этап связывается с распространением ЭВМ серии IBM/360. Проблема этого этапа — отставание программного обеспечения от уровня развития аппаратных средств. ЭВМ ЕС (Единой серии), выпускаемые бывшими странами СЭВ, семейство малых машин СМ ЭВМ. С середины 60-х до середины 70-х годов важным видом информационных услуг стали базы данных, содержащие разные виды информации по всевозможным отраслям знаний. Впервые возникает информационная технология поддержки принятия решений. Это совсем новый способ взаимодействия человека и компьютера. 4-е поколение основные черты этого поколения ЭВМ — наличие запоминающих устройств, запуск ЭВМ с помощью системы самозагрузки из ПЗУ, разнообразие архитектур, мощные ОС, объединение ЭВМ в сети. Начиная с середины 70-х годов с созданием национальных и глобальных сетей передачи данных ведущим видом информационных услуг стал диалоговый поиск информации в удаленных от пользователя базах данных. 5 поколение ЭВМ со многими десятками параллельно работающих процессоров, позволяющих строить эффективные системы обработки знаний; ЭВМ на сверхсложных микропроцессорах с параллельной векторной структурой, одновременно выполняющих десятки последовательных команд программы. 6 поколение Оптоэлектронные ЭВМ с массовым параллелизмом и нейронной структурой — с сетью из большого числа (десятки тысяч) несложных микропроцессоров, моделирующих структуру нейронных биологических систем. 

3.

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

4.

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

· Принцип однородности памяти. Как программы (команды), так и данные хранятся в одной и той же памяти (и кодируются в одной и той же системе счисления — чаще всего двоичной). Над командами можно выполнять такие же действия, как и над данными. ·Принцип адресуемости памяти. Структурно основная память состоит из пронумерованных ячеек; процессору в произвольный момент времени доступна любая ячейка. ·Принцип последовательного программного управления. Все команды располагаются в памяти и выполняются последовательно, одна после завершения другой. ·Принцип условного перехода. Команды из программы не всегда выполняются одна за другой. Возможно присутствие в программе команд условного перехода, которые изменяют последовательность выполнения команд в зависимости от значений данных. (Сам принцип был сформулирован задолго до Джона фон Неймана Адой Лавлейс и Чарльзом Бэббиджем, однако он логически включен в фон-неймановский набор как дополняющий предыдущий принцип.)

5. В целом следует признать, что при сохранении фон-неймановской концепции последовательного выполнения команд программы шинная архитектура в чистом ее виде оказывается недостаточно эффективной. Более распространена архитек­тура с иерархией шин, где помимо магистральной шины имеется еще несколько дополнительных шин. Они могут обеспечивать непосредственную связь между устройствами с наиболее интенсивным обменом, например процессором и кэш­-памятью. Другой вариант использования дополнительных шин — объединение однотипных устройств ввода/вывода с последующим выходом с дополнительной шины на магистральную. Все эти меры позволяют снизить нагрузку на общую шину и более эффективно расходовать ее пропускную способность.

6.

Контроллер – это созданная Вами PHP-функция, которая берёт информацию из HTTP-запроса и на её основании составляет и выдаёт HTTP-ответ (в виде Symfony2 объекта Response ). Ответом может быть HTML-страница, XML-документ, преобразованный в последовательную форму JSON-массив, изображение, переадресовывание на другой ресурс, ошибка 404 и т.п. Контроллер содержит любую произвольную логику, какая только может понадобиться в Вашем приложении для визуализации содержимого страницы.