1.Алгоритмы их виды и свойства.

 

 

1.1.Понятие алгоритма и его свойства

 

Алгоритм - описанная на некотором языке точная конечная система правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение поставленной задачи.Понятие алгоритма, являющееся фундаментальным в математике и информатике, возникло задолго до появления средств вычислительной техники. Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами  выполнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Муххамедом бен Аль-Хорезми .Слово алгоритм - есть результат европейского произношения слов Аль-Хорезми.Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя (человека, робота, компьютера, языка программирования и т.д.).Значение слова «алгоритм» очень схоже со значениями слов  «рецепт», «метод», «процесс». Однако, в отличие от рецепта или процесса, алгоритм характеризуется следующими свойствами: 

дискретностью, массовостью, определенностью, результативностью, формальностью.

Дискретность ( разрывность) - это свойство алгоритма, характеризующее его структуру: каждый  алгоритм состоит из отдельных законченных действий, говорят «Делится на шаги».

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

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

Результативность - свойство, состоящее в том, что любой алгоритм должен завершаться за конечное (может быть очень большое) число шагов.  Формальность - это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему?» должен разработчик алгоритма, а исполнитель формально (не думая) поочередно исполняет предложенные команды и получает необходимый результат.

 1.2.Способы описания (виды) алгоритмов.

Рассмотрим следующие способы описания алгоритма:  словесное описание, псевдокод, блок-схема, программа.

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

 

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

 

Блок-схема - описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость»алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.

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

 

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

 

 Основные алгоритмические конструкции.

Элементарные  шаги  алгоритма  можно  объединить  в  следующие алгоритмические конструкции:

линейные(последовательные), разветвляющиеся, циклические и рекурсивные.

- линейная алгоритмическая конструкция.

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

- разветвляющаяся алгоритмическая конструкция.

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

- алгоритмическая конструкция «Цикл».

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

- рекурсивный алгоритм.

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

2.Основы программирования.

Как мы уже знаем, компьютерная программа представляет собой логически упорядоченную последовательность команд,предназначенных для управления компьютером. Процессор компьютера - это большая интегральная схема. Все данные и команды он получает в виде электрических сигналов. В двоичном коде наличие сигнала описывается понятием «1», а его отсутствие - понятием «О». Команды, обрабатываемые процессором, можно интерпретировать как ряд  чередующихся определенным образом единиц и нулей. То есть любая команда преобразуется в двоичное число. Таким образом, процессор исполняет программы, представляющие собой последовательность чисел и называемые машинным кодом.

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

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

 

2.1. Понятие «язык программирования».

 

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

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

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

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

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

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

Языки программирования, ориентированные на команды процессора и учитывающие его особенности, называют языками низкого уровня. «Низкий уровень» не означает неразвитый, имеется в виду, что операторы этого языка близки к машинному коду и ориентированы на конкретные команды процессора. Языком самого низкого уровня является ассемблер. Программа, написанная на нем, представляет последовательность команд машинных кодов, но записанных с помощью символьных мнемоник.Языки программирования, имитирующие естественные,  обладающие укрупненными командами, ориентированные «на человека»,

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

Таким образом, языки программирования высокого уровня,  ориентированные на решение больших содержательных прикладных  

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

обрабатывается процессором.

С помощью языка программирования создается текст программы, описывающий разработанный алгоритм. Чтобы программа была

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

 

 

2.2 Классификация и обзор языков программирования.

 

Современное состояние языков программирования можно представить в виде следующей классификации:

 

-Процедурные (императивные);

-Операционные;

-Структурные;

-Объектно - ориентированные;

-Объектные;

-Визуальные;

-Декларативные;

-Функциональные;

-Логические.

 

 Фундаментальная идея процедурного программирования - использование памяти компьютера для хранения данных.

Функционирование  программы  сводится к последовательному выполнению команд с целью преобразования исходного состояния памяти, т.е. программа производит пошаговое преобразование содержимого памяти, изменяя его от исходного состояния к результирующему.Одним из первых процедурных языков программирования высокого уровня стал Фортран, созданный в начале 50-х гг. в США фирмой IBM. Многие средства Фортрана использованы в языках PL-1 и Бейсик.

Кобол (COmmon Business Oriented Language - общепринятый  деловой язык) - язык программирования, ориентированный на решение задач обработки данных. Широко используется для решения учетно-экономических и управленческих задач. Разработан в США в 1958-1960 гг. Программа на Коболе имеет вид ряда предложений на английском языке и напоминает обычный текст.

Алгол (ALGOrithmic Language) разработан группой зарубежных специалистов в 1960 г., явился результатом международного 

сотрудничества конца 50-х гг. (Алгол-60). В 1968 г. в результате дальнейшего развития и  усовершенствования Алгола-60 была создана версия Алгол-68. Это  многоцелевой универсальный расширенный язык программирования. По своим возможностям Алгол-68 и сегодня опережает многие языки программирования.

В середине 60-х гг. был создан специализированный язык программирования, который состоял из простых английских слов. Новый язык назвали универсальным символическим кодом для начинающих (Beginners All-purpose Symbolic /instruction Code) или сокращенно BASIC (Бейсик). 1964 г. считают годом рождения этого языка. Он получил самое широкое распространение при работе на персональных компьютерах в режиме интерактивного диалога. Популярность Бейсика объясняется как простотой его освоения, так и наличием достаточно мощных универсальных средств, пригодных для решения научных, технических и

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

В начале 60-х гг. каждый из существующих языков программирования был ориентирован на разные классы задач, но в той или иной мере привязан к конкретной архитектуре ЭВМ. Были  предприняты попытки преодолеть этот недостаток путем создания  универсального языка программирования. ПЛ/1 (PL/1 - Programming language One) - первый многоцелевой универсальный язык,  разработан в США фирмой IBM в 1963-1966 гг. Это один из наиболее  распространенных универсальных языков, он хорошо приспособлен для решения задач в области вычислительной техники.

Паскаль (Pascal) является одним из наиболее популярных  процедурных языков программирования, особенно для персональных компьютеров. Созданный как учебный язык программирования в 1968-1971 гг.  Н.Виртом, он был назван в честь французского математика и философа Блеза Паскаля. Задачей Н. Вирта было создание языка, базирующегося на простом синтаксисе и  небольшом количестве базовых конструкций, переводимого в машинный код простым компилятором.

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

В основу разработки языка Паскаль был положен Алгол-60, но в нем ужесточен ряд требований к структуре программы и имеются

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

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

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

Язык программирования С (Си) был разработан в лаборатории Bell для реализации операционной системы UNIX в начале 70-х гг.и не рассматривался как массовый. Он планировался для замены Ассемблера, чтобы иметь возможность создавать столь же эффективные и компактные программы, и в то же время не зависеть от конкретного типа процессора. По набору управляющих конструкций и структур данных С имеет возможности, присущие высокоуровневым языкам, и вместе с тем он располагает средствами прямого  обращения к функциональным узлам компьютера. Синтаксис языка С позволяет создавать лаконичный программный код.Язык С популярен и широко используется профессиональными программистами. 

 

К функциональному программированию можно отнести язык Лисп (LISP, LISt Processing - обработка списков), созданный в 1959 г. Джоном Маккарти. Этот язык ориентирован на структуру данных в форме списка и позволяет  организовать эффективную обработку больших объемов текстовой  информации. Существенная черта языка - единообразие программных структур и структур данных: все выражения записываются в виде списков.

Создание языка искусственного интеллекта Пролог (PROLOG, PROgramming in LOGic - программирование в терминах логики) в

1973 г. открыло новую  область - логическое или реляционное программирование. 

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

 

Объектно-ориентированное программирование представлено языком Смолток (Smalltalk). Данный язык оригинален тем, что его синтаксис очень компактен и базируется  исключительно на понятии объекта. В нем отсутствуют операторы или данные.

 

К наиболее распространенным современным языкам  программирования относятся C++ и  Java.

Язык C++ был разработан в начале 80-х гг.в лаборатории Bell. Была создана компактная компилирующая система, в основе которой лежал язык С, дополненный элементами языков BCPL, Simula-67 и Алгол-68. В 1990 г. корпорация Sun на  основе расширения C++ разработала объектно-ориентированный язык Oak, основным достоинством которого было обеспечение сетевого взаимодействия различных по типу устройств. Новая интегрируемая в Internet версия языка получила название Java. Сегодня Java по популярности занимает второе место в мире после Бейсика.

С середины 90-х гг. многие объектно-ориентированные языки реализуются как системы визуального программирования. Такие 

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

К объектно-ориентированным системам визуального проектирования относятся: Visual Basic, Delphi, C++ Builder, Visual C++.

Это системы программирования самого высокого уровня.

 

Языки программирования баз данных отличаются от алгоритмических прежде всего своим функциональным назначением. При работе с базами данных (БД) наиболее часто выполняются следующие операции: создание,  преобразование, удаление таблиц в БД; поиск, отбор, сортировка по  запросам пользователя; добавление новых записей или модификация существующих; удаление записей и др. Для обработки больших массивов информации и выборки записей по определенным признакам был создан структурированный язык запросов SQL (Structured Query Language).

Появление и активное развитие компьютерных сетей стало  причиной создания многочисленных версий популярных языков программирования, адаптированных для использования в сети. Отличительные особенности, присущие сетевым языкам: они являются интерпретируемыми. Интерпретаторы для них распространяются бесплатно, а сами программы - в исходных текстах. Такие языки получили название скрипт-языков.

HTML (Hyper Text Markup Language) - универсальный язык разметки гипертекста, используемый для подготовки Web-документов для сети Internet. Язык представляет собой набор элементарных команд форматирования текста, добавления графических объектов (рисунков), задания шрифтов и цвета, организации ссылок и таблиц. В соответствии с командами HTML браузер отображает содержимое документа, команды языка не отображаются. В основе языка HTML лежит механизм гипертекстовых ссылок, обеспечивающий связь  одного документа с другим. В HTML текст кодируется в ASCII и поэтому может быть создан и

отредактирован в любом текстовом редакторе. Все Web-страницы написаны на HTML или используют его расширение.

Практические аспекты программирования, например, на Visual Basic можно найти по адресу: http://www.vbzero.ru/

Бесплатные видео уроки по программированию для начинающих на turbo pascal и некоторых других языках (автор:Артем Кашеваров) можно получить, зарегистрировавшись на сайте: http://www.programmerinfo.ru