Понятие алгоритма
ВВЕДЕНИЕ
Алгоритм – это последовательность команд, выполнение которых приводит к решению поставленной задачи. Простым языком: это определенные действия, с указанной последовательностью, которые приводят нас к результату. Понятие алгоритма относится к первоначальным, основным, базисным понятиям математики.
Вычислительные процессы алгоритмического характера (арифметические действия над целыми числами, нахождение наибольшего общего делителя двух чисел и т. д.) известны человечеству с глубокой древности.
Цель данной работы: рассмотреть основные понятия алгоритмизации и программирования.
1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ
1.1. Понятия алгоритма и алгоритмизации
Само слово «алгоритм» происходит от имени хорезмского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, первые использовал цифр 0 для обозначения пропущенной позиции в записи числа.
В первой половине XII века книга аль-Хрезми в латинском переводе попала в Европу. Ей было дано название «Алгоритмы о счёте индийском». По-арабски книга называлась «Китаб аль-джебрваль-мукабала» («Книга о сложении и вычитании»). Из этого название в русский язык попало слово алгебра (алгебра - аль-джебр - восполнение).
В течение нескольких следующих столетий появилось множество других трудов, посвященных обучению искусству счёта с помощью цифр. И все они в названии имели слово algoritmi или algorismi.
Со временем algorism (или algorismus) обрело значение способа выполнения арифметических действий. Именно в таком значении оно вошло во многие европейские языки.
Постепенно значение слова расширялось. Учёные начинали применять его не только к сугубо вычислительным, но и к другим математическим процедурам (степени, дробные показатели, логарифмы).
Алгоритмизация – это преобразование исходной информации к алгоритмическому виду. Алгоритмизация, как раздел информатики, который изучает процессы создания алгоритмов, традиционно относится к теоретической информатике вследствие своего фундаментального характера.
Язык программирования — искусственный (формальный) язык, предназначенный для записи программ для исполнителя (например, компьютера или станка с числовым управлением). Язык программирования задается своим описанием. Описание языка программирования — это документ, специфицирующий возможности алгоритмического языка. Обычно описание содержит:
· алфавит допустимых символов и служебных (ключевых) слов;
· синтаксические правила построения из алфавита допустимых конструкций языка;
· семантику, объясняющую смысл и назначение конструкций языка.
Языки программирования служат для представления решения задач в такой форме, чтобы они могли быть выполнены на ЭВМ.
Классификацию языков программирования можно вести по нескольким критериям: машинно-ориентированные (ассемблеры) и машинно-независимые, специализированные и универсальные.
К специализированным языкам можно отнести язык АРТ (Automatically Programmed Tools) — первый специализированный язык программирования для станков с числовым управлением. Язык был разработан группой американских специалистов в 1956–1959 гг. под руководством математика Дугласа Т. Росса. Язык СOBOL (Common Business–Oriented Language), созданный в США под руководством Грейс Мюррей Хоппер в 1959 г., ориентирован на обработку экономической информации. Математик Грейс Мюррей Хоппер возглавила проект по разработке СOBOL в чине капитана второго ранга, впоследствии она стана контр-адмиралом. Г.М. Хоппер называют “мамой и бабушкой” СOBOLа.
К специализированным языкам можно отнести и современные языки web-программирования Perl и PHP. Языки Рапира, Е-язык (Россия), SMR (Великобритания), LOGO (США) можно отнести к языкам, предназначенным для обучения программированию.
Самыми распространенными универсальными языками программирования сегодня являются C++, Delphi, Java, Pascal, Visual Basic, Python.
Но, рассматривая языки программирования как самостоятельный объект исследования, можно провести их классификацию по концепции построения языка.
Языки программирования можно разделить на два класса: процедурные и непроцедурные. Процедурные (императивные) языки — это языки операторного типа. Описание алгоритма на этом языке имеет вид последовательности операторов. Характерным для процедурного языка является наличие оператора присваивания (Basic, Pascal, С). Программа, написанная на императивном языке, очень похожа на приказы, выражаемые повелительным наклонением в естественных языках, то есть это последовательность команд, которые должен выполнить компьютер. Программируя в императивном стиле, программист должен объяснить компьютеру, как нужно решать задачу.
Непроцедурные (декларативные) языки — это языки, при использовании которых в программе в явном виде указывается, какими свойствами должен обладать результат, но не говорится, каким способом он должен быть получен. Непроцедурные языки делятся на две группы: функциональные и логические[1].
Декларативные языки программирования — это языки программирования высокого уровня, в которых операторы представляют собой объявления или высказывания в символьной логике. Типичным примером таких языков являются языки логического программирования (языки, основанные на системе правил и фактов). Характерной особенностью декларативных языков является их декларативная семантика. Основная концепция декларативной семантики заключается в том, что смысл каждого оператора не зависит от того, как этот оператор используется в программе. Декларативная семантика намного проще семантики императивных языков, что может рассматриваться как преимущество декларативных языков над императивными.
Логические языки
В программах на языках логического программирования соответствующие действия выполняются только при наличии необходимого разрешающего условия на вывод новых фактов из данных фактов согласно заданным логическим правилам. Логическое программирование основано на математической логике.
Функциональные языки
Первым языком функционального типа является язык ЛИСП, созданный в Массачусетсском технологическом институте в 1956–1959 гг. Джоном Маккарти, который в 1956 г. на Дармутской конференции (США) впервые предложил термин “искусственный интеллект”.
Объектно-ориентированные языки
Объектно-ориентированные языки — это языки, в которых понятия процедуры и данных, используемых в обычных системах программирования, заменены понятием “объект”. Языком объектно-ориентированного программирования в чистом виде считается SmallTalk, возможности объектно-ориентированного программирования заложены также в Java, C++, Delphi.
1.3. Методы разработки структуры программы
Между существующими языками программирования есть принципиальные расхождения в концепции построения языков, особенно это справедливо для более ранних языков, но все эти языки потому и называются языками программирования, что они с точки зрения внутренней системы построения имеют одинаковое формальное строение.
Любой язык программирования состоит из предложений (операторов). Предложения (как и слова) определены над неким алфавитом С. Синтаксис языка описывает множество предложений над алфавитом С, которые внешне представляют правильно сформированные программы.
Синтаксис языка — это правила получения слов и предложений этого языка. Синтаксис схематически описывается с помощью определенных грамматических правил[2].
Знание формального языка (алфавита + синтаксиса) хотя и достаточно для установления синтаксической корректности программы, однако недостаточно для понимания ее назначения и способа действий. Значение и способ действия программы на языке программирования уточняются путем задания семантики.
Семантика языка — это правила интерпретации слов формального языка, т.е. установления значения отдельных языковых элементов.
Для определения формальных языков, в том числе для языков программирования, используют БНФ (формы Бэкуса — Наура) и синтаксические диаграммы. Это два взаимозаменяемых способа описания.
При описании языка программирования через БНФ используются следующие обозначения:
1) <..>— определяемое слово;
2) R — правило из синтаксиса для формирования слова;
3) <e>::= — БНФ-правило.
Каждое R состоит из терминальных слов или лексем языка и, возможно, следующих символов:
· | — или;
· [..] — данный элемент присутствует в БНФ;
· {..} — данное вхождение может быть использовано в БНФ;
· {..}* — данное вхождение может быть использовано в БНФ конечное число раз.
Заключение
Algorism – это способ выполнения арифметических действий. Алгоритмизация – это преобразование исходной информации к алгоритмическому виду. Язык программирования — искусственный язык, предназначенный для записи программ для исполнителя. Языки программирования делятся на:
- специализированные (АРТ, СOBOL, Perl и PHP)
- языки, предназначенные для обучения программированию (Рапира, Е-язык, SMR, LOGO)
- универсальные языки (C++, Delphi, Java, Pascal, Visual Basic, Python)
- процедурные и непроцедурные.
- Декларативные языки программирования
- Функциональные языки
- Объектно-ориентированные языки.
2. ПЕРЕВОД ЧИСЕЛ В ПОЗИЦИОННЫХ СИСТЕМАХ СЧИСЛЕНИЯ
2.1. Перевод целых чисел
Пример 1:
31510 1001110112
|
|
|||||||||
|
315 |
2 |
||||||||
|
-314 |
157 |
2 |
|||||||
|
1 |
-156 |
78 |
2 |
||||||
|
1 |
-78 |
39 |
2 |
||||||
|
0 |
-38 |
19 |
2 |
||||||
|
1 |
-18 |
9 |
2 |
||||||
|
1 |
-8 |
4 |
2 |
||||||
|
1 |
-4 |
2 |
2 |
||||||
|
0 |
-2 |
1 |
|||||||
|
0 |
|||||||||
315104738
Целая часть числа находится делением на основание новой
|
315 |
8 |
||
|
-312 |
39 |
8 |
|
|
3 |
-32 |
4 |
|
|
7 |
3151013B16
Целая часть числа находится делением на основание новой
|
315 |
16 |
||
|
-304 |
19 |
16 |
|
|
11=B |
-16 |
1 |
|
|
3 |
|
Пример 2.
315820510
3158 = 3∙82+1∙81+5∙80 = 192+8+5 = 20510
Получилось: 20510
Переведем 20510 в двоичную систему вот так:
Целая часть числа находится делением на основание новой
|
205 |
2 |
|||||||
|
-204 |
102 |
2 |
||||||
|
1 |
-102 |
51 |
2 |
|||||
|
0 |
-50 |
25 |
2 |
|||||
|
1 |
-24 |
12 |
2 |
|||||
|
1 |
-12 |
6 |
2 |
|||||
|
0 |
-6 |
3 |
2 |
|||||
|
0 |
-2 |
1 |
||||||
|
1 |
Получилось:20510 = 110011012
Результат перевода:
3158110011012
315820510
Переведем 20510 в шестнадцатиричную систему вот так:
Целая часть числа находится делением на основание новой
|
205 |
16 |
|
|
-192 |
12 |
|
|
13=D |
20510 CD16
Пример 3.
31510
1001110112 = 1∙28+0∙27+0∙26+1∙25+1∙24+1∙23+0∙22+1∙21+1∙20 = 256+0+0+32+16+8+0+2+1 = 31510
4738
1001110112 = 1∙28+0∙27+0∙26+1∙25+1∙24+1∙23+0∙22+1∙21+1∙20 = 256+0+0+32+16+8+0+2+1 = 31510
Переведем 31510 в восьмеричную систему вот так:
Целая часть числа находится делением на основание новой
|
315 |
8 |
||
|
-312 |
39 |
8 |
|
|
3 |
-32 |
4 |
|
|
7 |
|
13В
1001110112 = 1∙28+0∙27+0∙26+1∙25+1∙24+1∙23+0∙22+1∙21+1∙20 =256+0+0+32+16+8+0+2+1 = 31510
Целая часть числа находится делением на основание новой
|
315 |
16 |
||
|
-304 |
19 |
16 |
|
|
11=B |
-16 |
1 |
|
|
3 |
Пример 4.
A0A16 1010000010102
A0A16 = 10∙162+0∙161+10∙160 = 2560+0+10 = 257010
Целая часть числа находится делением на основание новой
|
2570 |
2 |
|||||||||||
|
-2570 |
1285 |
2 |
||||||||||
|
0 |
-1284 |
642 |
2 |
|||||||||
|
1 |
-642 |
321 |
2 |
|||||||||
|
0 |
-320 |
160 |
2 |
|||||||||
|
1 |
-160 |
80 |
2 |
|||||||||
|
0 |
-80 |
40 |
2 |
|||||||||
|
0 |
-40 |
20 |
2 |
|||||||||
|
0 |
-20 |
10 |
2 |
|||||||||
|
0 |
-10 |
5 |
2 |
|||||||||
|
0 |
-4 |
2 |
2 |
|||||||||
|
1 |
-2 |
1 |
||||||||||
|
0 |
Получилось:257010 = 1010000010102
A0A16 50128
A0A16 = 10∙162+0∙161+10∙160 = 2560+0+10 = 257010
Получилось: 257010
Переведем 257010 в восьмеричную систему вот так:
Целая часть числа находится делением на основание новой
|
2570 |
8 |
|||
|
-2568 |
321 |
8 |
||
|
2 |
-320 |
40 |
8 |
|
|
1 |
-40 |
5 |
||
|
0 |
|
A0A16 257010
A0A16 = 10∙162+0∙161+10∙160 = 2560+0+10 = 257010
2.2. Перевод действительных чисел
Пример 1.
31,51011111.12
|
31 |
2 |
||||
|
-30 |
15 |
2 |
|||
|
1 |
-14 |
7 |
2 |
||
|
1 |
-6 |
3 |
2 |
||
|
1 |
-2 |
1 |
|||
|
1 |
Получилось:3110 = 111112
Дробная часть числа находится умножением на основание новой
|
|
|||
|
0 |
.5 |
|
|
|
. |
2 |
|
|
|
1 |
0 |
|
|
|
|
|||
Получилось:0.510 = 0.12
Сложим вместе целую и дробную часть вот так:
111112 + 0.12 = 11111.12
Результат перевода:
31.510 = 11111.12
31,51037.48
Целая часть числа находится делением на основание новой
|
31 |
8 |
|
|
-24 |
3 |
|
|
7 |
Получилось:3110 = 378
Дробная часть числа находится умножением на основание новой
|
|
|||
|
0 |
.5 |
|
|
|
. |
8 |
|
|
|
4 |
0 |
|
|
|
|
|||
Получилось:0.510 = 0.48
Сложим вместе целую и дробную часть вот так:
378 + 0.48 = 37.48
Результат перевода:
31.510 = 37.48
31,5101F.816
Целая часть числа находится делением на основание новой
|
31 |
16 |
|
|
-16 |
1 |
|
|
15=F |
Получилось:3110 = 1F16
Дробная часть числа находится умножением на основание новой
|
|
|||
|
0 |
.5 |
|
|
|
. |
16 |
|
|
|
8 |
0 |
|
|
|
|
|||
Получилось:0.510 = 0.816
Сложим вместе целую и дробную часть вот так:
1F16 + 0.816 = 1F.816
Результат перевода: 31.510 = 1F.816
Пример 2.
31,5825,62510
31.58 = 3∙81+1∙80+5∙8-1 = 24+1+0.625 = 25.62510
31,5811001.1012
Для этого переведем его сначала в десятичную вот так :
31.58 = 3∙81+1∙80+5∙8-1 = 24+1+0.625 = 25.62510
Получилось: 25.62510
Переведем 25.62510 в двоичную систему вот так:
Целая часть числа находится делением на основание новой
|
25 |
2 |
||||
|
-24 |
12 |
2 |
|||
|
1 |
-12 |
6 |
2 |
||
|
0 |
-6 |
3 |
2 |
||
|
0 |
-2 |
1 |
|||
|
1 |
Получилось:2510 = 110012
Дробная часть числа находится умножением на основание новой
|
|
|||
|
0 |
.625 |
|
|
|
. |
2 |
|
|
|
1 |
25 |
|
|
|
2 |
|
||
|
0 |
5 |
|
|
|
2 |
|
||
|
1 |
0 |
|
|
|
|
|||
Получилось:0.62510 = 0.1012
Сложим вместе целую и дробную часть вот так:
110012 + 0.1012 = 11001.1012
Результат перевода:
31.58 = 11001.1012
31,5819.А16
Переведем 25.62510 в шестнадцатиричную систему вот так:
Целая часть числа находится делением на основание новой
|
25 |
16 |
|
|
-16 |
1 |
|
|
9 |
Получилось:2510 = 1916
Дробная часть числа находится умножением на основание новой
|
|
|||
|
0 |
.625 |
|
|
|
. |
16 |
|
|
|
10=A |
0 |
|
|
|
|
|||
Получилось:0.62510 = 0.A16
Сложим вместе целую и дробную часть вот так:
1916 + 0.A16 = 19.A16
Результат перевода: 31.58 = 19.A16
Пример 3.
5.312510
101.01012 = 1∙22+0∙21+1∙20+0∙2-1+1∙2-2+0∙2-3+1∙2-4 = 4+0+1+0+0.25+0+0.0625 = 5.312510
5.248
101.01012 = 1∙22+0∙21+1∙20+0∙2-1+1∙2-2+0∙2-3+1∙2-4 = 4+0+1+0+0.25+0+0.0625 = 5.312510
Получилось: 5.312510
Дробная часть числа находится умножением на основание новой
|
|
|||
|
0 |
.3125 |
|
|
|
. |
8 |
|
|
|
2 |
5 |
|
|
|
8 |
|
||
|
4 |
0 |
|
|
|
|
|||
Получилось:0.312510 = 0.248
Сложим вместе целую и дробную часть вот так:
58 + 0.248 = 5.248
Результат перевода:
101.01012 = 5.248
5.516
101.01012 = 1∙22+0∙21+1∙20+0∙2-1+1∙2-2+0∙2-3+1∙2-4 = 4+0+1+0+0.25+0+0.0625 = 5.312510
Получилось: 5.312510
Дробная часть числа находится умножением на основание новой
|
|
|||
|
0 |
.3125 |
|
|
|
. |
16 |
|
|
|
5 |
0 |
|
|
|
|
|||
Получилось:0.312510 = 0.516
Сложим вместе целую и дробную часть вот так:
516 + 0.516 = 5.516
Результат перевода: 101.01012 = 5.516
Пример 4.
71.2510
47.416 = 4∙161+7∙160+4∙16-1 = 64+7+0.25 = 71.2510
1000111.012
47.416 = 4∙161+7∙160+4∙16-1 = 64+7+0.25 = 71.2510
Переведем 71.2510 в двоичную систему вот так:
Целая часть числа находится делением на основание новой
|
71 |
2 |
||||||
|
-70 |
35 |
2 |
|||||
|
1 |
-34 |
17 |
2 |
||||
|
1 |
-16 |
8 |
2 |
||||
|
1 |
-8 |
4 |
2 |
||||
|
0 |
-4 |
2 |
2 |
||||
|
0 |
-2 |
1 |
|||||
|
0 |
Получилось:7110 = 10001112
107.28
47.416 = 4∙161+7∙160+4∙16-1 = 64+7+0.25 = 71.2510
Целая часть числа находится делением на основание новой
|
71 |
8 |
||
|
-64 |
8 |
8 |
|
|
7 |
-8 |
1 |
|
|
0 |
Получилось:7110 = 1078
Дробная часть числа находится умножением на основание новой
|
|
|||
|
0 |
.25 |
|
|
|
. |
8 |
|
|
|
2 |
0 |
|
|
|
|
|||
Получилось:0.2510 = 0.28
Сложим вместе целую и дробную часть вот так:
1078 + 0.28 = 107.28
Результат перевода: 47.416 = 107.28
СПИСОК ЛИТЕРАТУРЫ
- Информатика. Базовый курс./С.В. Симонович и др. - СПб.: Питер, 2015.
- Информатика: базовый курс: учебник для студентов вузов, бакалавров, магистров, обучающихся по направлению «Информатика»/О.А. Акулов, Н.В. Медведев. 6-е изд., испр. и доп.-М.: Издательство «Омега-Л», 2014.-574 с. – (Высшее техническое образование).
- Каймин В.А. Информатика: Учебник для вузов. - М.: Высшее образование, 2015.
- Каймин В.А., Касаев Б.С. Информатика.: Практикум на ЭВМ. Учебное пособие. - СПб.: Питер, 2015.
