Экономическая информатика. 2
- Понятие и свойства алгоритма
- История возникновения алгоритма
Современное формальное определение алгоритма было дано в 30—50-х годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера А.А. Маркова. Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, арабский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском»). По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алгебра.
Таким образом, мы видим, что латинизированное имя среднеазиатского ученого было вынесено в заглавие книги, и сегодня ни у кого нет сомнений, что слово «алгоритм» попало в европейские языки именно благодаря этому сочинению. Однако вопрос о его смысле длительное время вызывал ожесточённые споры. На протяжении многих веков происхождению слова давались самые разные объяснения. Упомянутый выше перевод сочинения аль-Хорезми стал первой ласточкой, и в течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр. И все они в названии имели слово algoritmi. [1]
- Понятие алгоритма
Алгоритм – это понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящих от искомых данных к искомому результату. В этом определении содержатся основные понятия, связанные с алгоритмом и его главные свойства. Взаимосвязь понятий отражена на рис 1.[9]
Исполнитель алгоритма – это тот объект (или субъект), для управления которым составлен алгоритм (человек, машина, компьютер и т.д.). Центральным объектом в этой системе является ИСПОЛНИТЕЛЬ алгоритмов.[7]
Рис. 1. Схема функционирования исполнителя алгоритмов
- Свойства алгоритма
При составлении и записи алгоритма необходимо обеспечить, чтобы он обладал рядом свойств:
однозначностью (детерминированностью)
- любое действие алгоритма
дискретностью – разбиение алгоритма на ряд отдельных законченных действий (шагов);
конечностью - каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения;
массовостью - возможность применения данного алгоритма для решения целого класса задач с разными исходными данными;
результативностью - алгоритм должен приводить к правильному результату для всех допустимых входных значениях.
Основной характеристикой
Для выполнения всякой работы, решения поставленной задачи исполнитель на входе получает алгоритм и исходные данные, а на выходе получаются требуемые результаты. Алгоритм может включать в себя только команды, входящие в СКИ. Это требование к алгоритму называется свойством понятности.
Другое свойство алгоритма — точность. Всякая команда должна быть сформулирована так, чтобы определить однозначное действие исполнителя.
Работа исполнителя состоит в последовательном выполнении команд алгоритма. Отсюда следует вывод о возможности создания автоматических исполнителей. В частности таким автоматическим исполнителем алгоритмов по обработке информации является компьютер.
Еще одно свойство, которое отражено в определении алгоритма — конечность. Оно формулируется так: исполнение алгоритма и, следовательно, получение искомого результата должно завершиться за конечное число шагов. Здесь под шагом подразумевается выполнение отдельной команды. Это свойство является предупреждением ситуации, которую программисты называют зацикливанием. Бесконечно исполняемый алгоритм безрезультатен. Поэтому свойство конечности называют еще результативностью алгоритма.
Дискретность
состоит в том, что команды
алгоритма выполняются
Свойство массовости выражается в том, что алгоритм единым образом применяется к любой конкретной формулировке задачи, для решения которой он разработан.
Другими словами, это можно назвать универсальностью алгоритма по отношению к исходным данным решаемой задачи. Заметим, что данное свойство не является необходимым свойством алгоритма, а скорее определяет качество алгоритма: универсальный алгоритм лучше неуниверсального (алгоритм решения частной задачи — тоже алгоритм!)[6]
- Языки и системы программирования
- Понятие о языке программирования
Программирование в машинном коде
— трудоемкий процесс, в ходе которого
трудно избежать ошибок. Упростить
этот процесс можно, если автоматизировать
работу, поручив часть ее самому компьютеру.
Прогресс компьютерных технологий определил
процесс появления новых разнообразных
знаковых систем для записи алгоритмов
– языков программирования.
Сегодня для записи программ используют
языки программирования. Язык программирования — это формальный
язык для записи алгоритмов в виде, допускающем
их автоматическую подготовку к выполнению
на компьютере. Для преобразования программы
в машинный код служит специальное программное
средство — транслятор.
Язык программирования содержит три основных компонента: алфавит, синтаксис и семантику. Эти компоненты определяют правила записи программ. Алфавит языка — это набор символов, которые можно применять в инструкциях языка программирования. Другие символы допустимы только в особых случаях, например в строковых константах.
Синтаксис языка определяет правила построения операторов. Любой корректный оператор соответствует этим правилам. Правила синтаксиса — формальные. Проверка правильности исходного текста и поиск синтаксических ошибок могут быть выполнены автоматически.
Семантика — это смысловое содержание операторов языка программирования. Семантические правила определяют действия, описываемые различными операторами, и, в итоге, сущность всего алгоритма.
Язык программирования — формальная знаковая система, предназначенная для записи компьютерных программ. Язык программирования определяет набор лексических, синтаксических и семантических правил, задающих внешний вид программы и действия, которые выполнит исполнитель (компьютер) под ее управлением.
Со времени создания первых программируемых машин человечество придумало более двух с половиной тысяч языков программирования. Каждый год их число пополняется новыми. Некоторыми языками умеет пользоваться только небольшое число их собственных разработчиков, другие становятся известны миллионам людей. Профессиональные программисты иногда применяют в своей работе более десятка разнообразных языков программирования.
Смысл появления такого языка – оснащенный набор вычислительных формул дополнительной информации, превращает данный набор в алгоритм.
Язык программирования служит двум связанным между собой целям: он дает программисту аппарат для задания действий, которые должны быть выполнены, и формирует концепции, которыми пользуется программист.
Может показаться удивительным, но конкретный компьютер способен работать с программами, написанными на его родном машинном языке. Существует почти столько же разных машинных языков, сколько и компьютеров, но все они суть разновидности одной идей простые операции производятся со скоростью молнии на двоичных числах. Персональные компьютеры IBM используют машинный язык микропроцессоров семейства 8086, т.к. их аппаратная часть основывается именно на данных микропроцессорах. Можно писать программы непосредственно на машинном языке, хотя это и сложно.[9]
- История возникновения языков программирования
На заре компьютеризации (в начале 1950-х г.г.), машинный язык был единственным языком, большего человек к тому времени не придумал. Для спасения программистов от сурового машинного языка программирования, были созданы языки высокого уровня (т.е. немашинные языки), которые стали своеобразным связующим мостом между человеком и машинным языком компьютера. Языки высокого уровня работают через трансляционные программы, которые вводят "исходный код" (гибрид английских слов и математических выражений, который считывает машина), и в конечном итоге заставляет компьютер выполнять соответствующие команды на машинном языке. Каждый процессор имеет свою систему команд. Компьютер способен выполнять только последовательности команд, понятных процессору, — машинный код. Первоначально программы для компьютеров и писались с использованием машинного кода.
Один из самых старых языков программирования Фортран был создан в 50-х гг. нашего века. Фортран и подобные ему языки программирования (Алгол, ПЛ/1) предназначались для решения вычислительных задач, возникающих в математике, физике, инженерных расчетах, экономике и т.п. Эти языки в основном работают с числами. Фортран был задуман для использования в сфере научных и инженерно-технических вычислений. Однако на этом языке легко описываются задачи с разветвленной логикой (моделирование производственных процессов, решение игровых ситуаций и т.д.), некоторые экономические задачи и особенно задачи редактирования (составление таблиц, сводок, ведомостей и т.д.). Одним из первых и наиболее удачных компиляторов стал язык Фортран, разработанный фирмой IBM. Профессор Дж. Букс и группа американских специалистов в области программирования в 1954 году опубликовало первое сообщение о языке. Дословно, название языка Formulae Translation –преобразование формул.
Язык Бейсик (BASIC — Beginners All-purpose Symbolic Instruction Code — универсальный символьный код для начинающих) был создан в 1965 г. Дж. Кемени и Т. Курцем как язык, облегчающий написание простых программ.
Язык Паскаль был разработан в 1970 г. Никласом Виртом как язык обучения студентов программированию. Паскаль вырабатывает навыки соблюдения хорошего строгого стиля программирования, упрощающего разработку сложных программ. Основные привлекательные черты Паскаля — логичность, поддержка концепций структурного и процедурного программирования, работа с динамической памятью, возможность создания своих типов данных.
В своем первоначальном виде Паскаль имел довольно ограниченные возможности, но расширенный вариант этого языка — Turbo Pascal, является очень мощным языком программирования.
Язык Си разработан Деннисом Ритчи в 1972 г. как язык, пригодный для программирования новой операционной системы UNIX. Си не очень прост в изучении и требует тщательности в программировании, но позволяет создавать сложные и весьма эффективные программы.
Язык Ассемблера Система обозначений для представления в удобочитаемом виде программ, записанных в машинном коде, — это уже язык программирования (язык ассемблера, или автокод). Ассемблер, программа, преобразующая текст на языке ассемблера в машинные команды, — это простейший транслятор.[3]
- Классификация языков программирования
Машинный язык - система команд, непосредственно понимаемых аппаратурой данной электронно-вычислительной системы. Как следствие этого, машинный язык однозначно определяется системой команд процессора и архитектурой компьютера.
Набор команд процессора содержит:
арифметико-логические
команды - команды арифметических действий
над двоичными числами и
команды управления - команды перехода, ветвлений, повторений, и некоторые другие команды;
команды пересылки данных - команды, с помощью которых обмениваются данными ОЗУ и ЦП;
команды ввода-вывода данных - команды, с помощью которых обмениваются данными ЦП и внешние устройства.
Каждая команда содержит код операции, ею выполняемой и информацию об адресах данных, над которыми эта операция выполняется. Кроме этого, команда (непосредственно - команды управления и косвенно - другие команды) содержит информацию об адресе команды, которая будет выполняться следующей. Таким образом, любая последовательность команд, размещенная в ОЗУ, фактически представляет из себя алгоритм, записанный в системе команд процессора - машинную программу. Каждый процессор имеет свою систему команд. Компьютер способен выполнять только последовательности команд, понятных процессору, — машинный код. Первоначально программы для компьютеров и писались с использованием машинного кода.
Таким образом,
машинный язык (язык процессора) - это
набор команд, каждая из которых
описывает некоторое
Иными словами,
программист (проектировщик алгоритмов)
должен иметь возможность
Существует два основных вида трансляторов: интерпретаторы, которые сканируют и проверяют исходный код в один шаг, и компиляторы, которые сканируют исходный код для производства текста программы на машинном языке, которая затем выполняется отдельно.
Машинно-ориентированные языки
Языки для машинно-ориентированной записи программ называют языками низкого уровня.
Предшественниками языков высокого уровня стали так называемые машинно-ориентированные языки или языки автокодов. Одним из самых ярких представителей машинно-ориентированных языков является Ассемблер. Ассемблер очень близок к машинному языку, большинство его инструкций является точным символическим представлением машинных команд. Преимущество состоит в том, что уже нет необходимости помнить числовые коды команд процессора, достаточно знать их символическое представление. Кроме этого, впервые в машинно-ориентированных языках появляется понятие переменной, как именованной области памяти для хранения данных, а вместе с ним и понятие типа данных. В программах на машинно-ориентированном языке появляется возможность использовать как числовую так и текстовую информацию в привычной для человека форме. Инструкция языка ассемблера описывает ровно одну машинную команду. И наоборот: каждой команде в системе команд процессора соответствует инструкция языка (мнемоника). По сравнению с машинным кодом язык ассемблера имеет ряд преимуществ, облегчающих труд программиста.
Несмотря на явные преимущества машинно-ориентированных языков перед сугубо машинным языком, написание программ на этих языках по прежнему сопряжено со значительными трудностями. Программы получаются очень громоздки и трудно читаемы. Языки низкого уровня сегодня применяют в тех случаях, когда имеются особые требования к скорости работы и компактности программы. Они также удобны, если нужен прямой доступ к аппаратным ресурсам.
Языки программирования высокого уровня
Программировать на языке ассемблера намного проще, чем в машинном коде, но все равно сложно. Поэтому были созданы другие языки программирования, в которых каждая инструкция (оператор) языка преобразуется в группу машинных. Эти языки ориентируются не на систему команд процессора, а на способ мышления, присущий человеку. Языки, удобные для людей, называют языками высокого уровня.
Сегодня абсолютное большинство программ создается именно на основе языков высокого уровня. Эти языки имеют следующие достоинства.
Машинная независимость. Программа с одинаковым исходным текстом может быть подготовлена для выполнения на процессорах с разной системой команд. Транслятор языка программирования высокого уровня — это машинно-зависимая система, предназначенная для подготовки программы к выполнению в рамках конкретной платформы.
Использование естественных обозначений (например, привычных математических знаков).
Эффективное представление этапов обработки данных средствами языка. Набор допустимых операций определен соображениями удобства, а не системой команд конкретного процессора.
Расширенный набор поддерживаемых типов данных.
Готовые библиотеки стандартных подпрограмм для выполнения часто встречающихся действий.
Применение языков программирования высокого уровня для создания программ началось в 60-е годы XX века. С тех пор по настоящее время создано и используется множество языков программирования, как универсальных, так и ориентированных на определенные группы задач. Языки программирования высокого уровня играют роль средства связи между программистом и машиной.
- Системы программирования
В пятидесятые годы двадцатого века с появлением компьютеров на электронных лампах началось бурное развитие систем программирования. К сегодняшнему дню насчитывают несколько поколений систем программирования. Каждое из последующих поколений по своей функциональной мощности качественно отличается от предыдущего. С появлением персональных компьютеров системы стали составными частями интегрированных сред разработки. Появились системы, применяемые в различных офисных программах. В настоящее время системы программирования применяются в самых различных областях человеческой деятельности, таких как научные вычисления, системное программирование, обработка информации, искусственный интеллект, издательская деятельность, удаленная обработка информации, описание документов.
Система программирования — это система для разработки новых программ на конкретном языке программирования. Современные системы программирования обычно предоставляют пользователям мощные и удобные средства разработки программ.
К ним относятся:
• компилятор или интерпретатор;
• интегрированная среда
• средства создания и редактирования текстов программ;
• обширные библиотеки стандартных программ и функций;
• отладочные программы, т.е. программы, помогающие находить и устранять ошибки в программе;
• "дружественная" к пользователю диалоговая среда;
• многооконный режим работы;
• мощные графические библиотеки; утилиты для работы с библиотеками
• встроенный ассемблер;
• встроенная справочная служба;
• другие специфические особенности.
Популярные системы
В последнее время получили распространение системы программирования, ориентированные на создание Windows-приложений:
пакет Borland Delphi (Дельфи) — блестящий наследник семейства компиляторов Borland Pascal, предоставляющий качественные и очень удобные средства визуальной разработки. Его исключительно быстрый компилятор позволяет эффективно и быстро решать практически любые задачи прикладного программирования.
пакет Microsoft Visual Basic — удобный и популярный инструмент для создания Windows-программ с использованием визуальных средств. Содержит инструментарий для создания диаграмм и презентаций.
пакет Borland C++ — одно из самых распространённых средств для разработки DOS и Windows приложений. [5]
- Процессор ЭВМ: назначение, типы и основные характеристики
- Понятие процессор ЭВМ
Процессор – это центральное обрабатывающее устройство компьютера. Он выполняет все арифметические и логические операции и управляет работой всего компьютера.
Процессор – это блок ЭВМ, предназначенный для автоматического считывания команд программы, их расшифровки и выполнения. Будучи центральным устройством ЭВМ, процессор во многом определяет её возможности и производительность.
В компьютерах третьего поколения процессор изготавливался из отдельных деталей и микросхем невысокого уровня интеграции. Прогресс в области микроэлектроники привел к тому, процессор удалось разместить внутри одного кристалла. Таким образом, он стал отдельной самостоятельной микросхемой и получил название – микропроцессор.[10]
Центральный процессор (ЦП, или центральное процессовое устройство — ЦПУ; англ. central processing unit, сокращенно - CPU, дословно — центральное обрабатывающее устройство) — микросхема, исполнитель машинных инструкций (кода программ), главная часть аппаратного обеспечения компьютера или программируемого логического контроллера. Иногда называют микропроцессором или просто процессором. На компьютерном сленге его называют либо "проц", либо "камень».
- Структура процессора
Современные процессоры строятся на одной или нескольких интегральных схем. ЦП – это одна микросхема, в которой используется все возможности современной полупроводниковой технологии. Такую микросхему называют – микропроцессором. В компьютерах используются процессоры нескольких типов. Наиболее распространены: центральные, специализированные, процессоры ввода вывода, передачи информации. ЦП служит для обработки данных и управления всей компьютерной системы в целом, позволяет обрабатывать данные с фиксированной и плавающей точкой, поля переменной длины, а иногда и десятичные данные, назначать приоритеты доступа и управлять различными видами памяти.
В состав ЦП входят:
- Арифметическое устройство.
- Счетчик команд.
- Регистр команд.
- Регистр данных.
- Блок микропрограммного или аппаратного управления.
- Регистры общего назначения и ряд узлов, предназначенных для связи оперативной памяти и другими устройствами компьютера.
При выполнении каждой команды вычислительная машина проделывает определенные стандартные действия:
1. Согласно содержимому счетчика
адреса команды считывается
2. Считанная в регистр команд операция расшифровывается.
3. Извлекаются необходимые данные.
4. Над ними в АЛУ выполняются требуемые действия.
5. Результат записывается в ОЗУ.
Схема основного алгоритма работы процессора:
считывание очередной команды в регистр команд
формирование адреса следующей команды
дешифрация команды
выборка операндов
выполнение операции
запись результата
начало
остановка
конец
нет
да
Как следует из приведенной схемы, обработка команды в процессоре может быть разделена на несколько основных этапов, которые можно назвать микрокомандами. Известно пять основных типов микрокоманд. Каждая операция требует своего выполнения времени, равному такту генератора процессора.
- Типы процессоров
По типу семейства: Intel, AMD, ARM, Pentium, Celeron.
По назначению: Универсальные и специализированные.
Все процессоры можно разделить на группы:
Процессоры типа CISC (Complex Instruction Set Computing) с полным набором команд, т.е. универсальные; Это микропроцессоры семейства х86.
Процессоры типа RISC (Reduced) с сокращенным набором команд, т.е. специализированные.Это процессоры такие как: MIPS, SPARС, ARM.
Процессоры типа MISC (Minimum instruction set computer) - вычисления с минимальным набором команд (20-30) и весьма высоким быстродействием. Эти модели процессоров находятся в стадии разработки.
Процессоры типа VLIW ( Very long instruction word) - сверхдлинное командное слово. Примером такого процессора является – Intel Itanium.
К основным относят группы CISC и RISC.
Эти процессоры нацелены на быстрое выполнение небольшого набора простых команд. При выполнении сложных команд RISC – процессоры работают медленнее, чем CISC – процессоры.[11]
- Назначение, классификация и основные характеристики
Назначение процессора:
Управлять работой ЭВМ по заданной программе;
Выполнять операции обработки информации.
Классификация по исполнению:
- однокристальный
- многокристальный
- многокристальный секционный
Классификация по архитектуре:
- фон Неймана (принстонская)
- гарвардская (программный код и данные хранятся в разной памяти, не возможно во время выполнения программы изменить её код, оптимально для ограниченных ресурсов)
- параллельная (суперкомпьютеры)
Основные характеристики:
быстродействие – количество операций, производимых в 1 секунду
тактовая частота, - количество тактов, производимых процессором.
за 1 секунду. Операции, производимые процессором, не являются непрерывными, они разделены на такты.
частота системной шины (чем она больше, тем больше данных передается за отрезок времени)
количество ядер (одно-, двух- и четырехядерные процессоры)
объем кэш-памяти - памяти с большой скоростью доступа.
разрядность – количество двоичных разрядов, которые процессор обрабатывает за один такт.
вид оперативной памяти (DDR, DDR2, DDR3)
сокет ( разъем в который
вставляется центральный
Под разрядностью процессора понимают число одновременно обрабатываемых им битов. Формально эта величина есть количество двоичных разрядов в регистрах процессора.
Любая операция процессора (машинная команда) состоит из отдельных операций – тактов. В зависимости от сложности, команда может быть реализована за разное количество тактов. Предельная тактовая частота определяется технологией производства микросхем, в частности наименьшими достижимыми размерами элементов, которые определяют минимальное время передачи сигналов. Чем выше тактовая частота, тем выше производительность.
Кэш-память – это высокоскоростная память произвольного доступа, используемая процессором компьютера для временного хранения информации. Кэш-память напрямую влияет на скорость работы с более равномерной нагрузкой.
Заключение
Таким образом, любая последовательность команд, размещенная в ОЗУ, фактически представляет из себя алгоритм, записанный в системе команд процессора - машинную программу.
Применение языков
