Пятница, 25.09.2020, 13:38
Ш  К  О  Л  А     П  И  Ф  А  Г  О  Р  А
      Предмет математики настолько серьезен, что нужно
не упускать случая, сделать его немного занимательным".
                                                                           Блез Паскаль
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
ПАМЯТКИ ПО МАТЕМАТИКЕ   ВЕЛИКИЕ МАТЕМАТИКИ   ТЕОРИЯ ЧИСЕЛ   МАТЕМАТИЧЕСКАЯ ЛОГИКА
УРОКИ МАТЕМАТИКИ В ШКОЛЕ


МАТЕМАТИЧЕСКАЯ КЛАДОВАЯ


В МИРЕ ЗАДАЧ
ЕГЭ ПО МАТЕМАТИКЕ
МАТЕМАТИКА В НАЧАЛЬНОЙ ШКОЛЕ
ВАРИ, КОТЕЛОК!
УДИВИТЕЛЬНАЯ МАТЕМАТИКА
ВЫСШАЯ МАТЕМАТИКА
В МИРЕ ИНТЕРЕСНОГО
Категории раздела
ПРОСТЫЕ ЧИСЛА. ДОЛГАЯ ДОРОГА К БЕСКОНЕЧНОСТИ [37]
КОГДА ПРЯМЫЕ ИСКРИВЛЯЮТСЯ. НЕЕВКЛИДОВЫ ГЕОМЕТРИИ [23]
МУЗЫКА СФЕР. АСТРОНОМИЯ И МАТЕМАТИКА [57]
МАГИЯ ЧИСЕЛ. МАТЕМАТИЧЕСКАЯ МЫСЛЬ ОТ ПИФАГОРА ДО НАШИХ ДНЕЙ [27]
ИНВЕРСИЯ [20]
ИСТИНА В ПРЕДЕЛЕ. АНАЛИЗ БЕСКОНЕЧНО МАЛЫХ [47]
БЕСКОНЕЧНОСТЬ В МАТЕМАТИКЕ [43]
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЕЕ ПАРАДОКСЫ [6]
ИЗМЕРЕНИЕ МИРА. КАЛЕНДАРИ, МЕРЫ ДЛИНЫ И МАТЕМАТИКА [33]
АБСОЛЮТНАЯ ТОЧНОСТЬ И ДРУГИЕ ИЛЛЮЗИИ. СЕКРЕТЫ СТАТИСТИКИ [31]
КОДИРОВАНИЕ И КРИПТОГРАФИЯ [47]
МАТЕМАТИКА В ЭКОНОМИКЕ [39]
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И МАТЕМАТИКА [35]
ЧЕТВЕРТОЕ ИЗМЕРЕНИЕ. ЯВЛЯЕТСЯ ЛИ НАШ МИР ТЕНЬЮ ДРУГОЙ ВСЕЛЕННОЙ? [9]
ТВОРЧЕСТВО В МАТЕМАТИКЕ [44]
ЗАГАДКА ФЕРМА. ТРЕХВЕКОВОЙ ВЫЗОВ МАТЕМАТИКЕ [30]
ТАЙНАЯ ЖИЗНЬ ЧИСЕЛ. ЛЮБОПЫТНЫЕ РАЗДЕЛЫ МАТЕМАТИКИ [95]
АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ [17]
КАРТОГРАФИЯ И МАТЕМАТИКА [38]
ПОЭЗИЯ ЧИСЕЛ. ПРЕКРАСНОЕ И МАТЕМАТИКА [23]
ТЕОРИЯ ГРАФОВ [33]
НАУКА О ПЕРСПЕКТИВЕ [29]
ЧИСЛА - ОСНОВА ГАРМОНИИ. МУЗЫКА И МАТЕМАТИКА [15]
Статистика

Онлайн всего: 6
Гостей: 6
Пользователей: 0
Форма входа

Главная » Файлы » МИР МАТЕМАТИКИ » АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ

Программирование и программы
19.01.2016, 12:28

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

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

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

В прошлых главах этой книги вы могли убедиться, что понятие «алгоритм» появилось намного раньше, чем компьютеры. Изначально этот термин относился к чистой математике и означал исключительно описание последовательности инструкций, необходимых для выполнения арифметических расчетов. Лишь позднее это понятие стали использовать в более широком смысле и связывать с информатикой, столь популярной в наши дни. Языки программирования — это всего лишь следующий этап эволюции форм записи алгоритмов, более формальный и точный (в противном случае они не могли бы быть использованы в компьютерах).

* * *

ТЕРМИН «РЕАЛИЗАЦИЯ»

Реализация — это осуществление или воплощение чего-либо. В информатике этот термин означает запись определенного алгоритма на заданном языке программирования.


ТЕРМИН «ПРОГРАММИРОВАНИЕ»

Слово «программировать» (англ, to program), означающее задание инструкций, которые должен выполнить компьютер, было придумано группой исследователей, работавших над созданием компьютера ENIAC в Институте Мура Пенсильванского университета. В то время использовалось слово «настраивать» (to set up), так как программирование ENIAC (изображен на иллюстрации ниже) осуществлялось с помощью соединений и переключателей, то есть путем изменения электрической схемы самого компьютера. Постепенно, по мере того как разделение между аппаратным и программным обеспечением становилось все более явным, стало применяться слово «программирование».



* * *

Древнейшие алгоритмы, которые позволили вавилонянам провозгласить себя первыми математиками, способными решать достаточно сложные задачи, использовались для решения алгебраических уравнений, записывались в общем виде и демонстрировались на конкретных примерах. В них не использовались итерации или условные конструкции вида «если x < 0, то», так как вавилонянам не был известен нуль. Чтобы выразить несколько возможных вариантов, математики Вавилонии повторяли алгоритм необходимое число раз. Прошло много веков, прежде чем Евклид примерно в 300 году до н. э. описал алгоритм вычисления наибольшего общего делителя двух чисел. Этот алгоритм, который сегодня известен как алгоритм Евклида, как правило, реализуется с помощью рекурсии.

* * *

РЕАЛИЗАЦИЯ АЛГОРИТМА ЕВКЛИДА

Приведем в качестве примера реализацию алгоритма для нахождения наибольшего общего делителя чисел А и В сначала на языке Пролог, затем на языке Java. Сокращение gcd означает great common divisor — наибольший общий делитель.

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

gcd (А, 0, А).

gcd (А, В, D)(А > В), (В > 0), R is A mod В, gcd(B, R, D).

gcd (А, В, D)(А < В), (А > 0), R is В mod A, gcd(A, R, D).

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

public static int gcd (int A, int B) {

if (B == 0) {return A;}

else if (A > B) {return gcd(B, A % B);}

else if (A < B) {return gcd(A, В % A);}

return 1;

}

public static int gcdlterative (int A, int B) {

int r = 0;

while (B > 0) {

r = A % B;

A = B;

В = r;

}

return A;

}

* * *

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

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

Несмотря на все усилия, предпринятые в 1930-е и 1940-е годы, а также написанные в этот период теоретические работы, в особенности те, что были посвящены лямбда-исчислению и машине Тьюринга, развитие алгоритмов началось лишь с появлением первых компьютеров: «Колосса», Mark I, ENIAC, EDSAC и UNIVAC. Языки программирования, с помощью которых стало возможным написание программ, хранящихся в оперативной памяти, позволили сэкономить время и уйти от взаимодействия с аппаратным обеспечением напрямую — именно так осуществлялось программирование первых компьютеров.

Программы для первых компьютеров писались в восьмеричном коде. Среди первых языков программирования, допускавших представление символов, были Short Order Code (1949) Джона Мокли и Sort-Merge Generator Бетти Холбертон. Short Order Code исполнялся на компьютере BINAC и был интерпретируемым языком.

Процедуры, соответствовавшие символам, хранились в памяти компьютера и вызывались системой. Эту же систему унаследовал UNIVAC. Программа, записанная на этом языке, исполнялась в 50 раз медленнее той же программы, записанной на машинном языке.

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




Бетти Холбертон (на этой фотографии она изображена за работой на ENIAC), создавшая один из первых языков программирования.


Эти первые системы, автоматического программирования (англ, automatic programming systems) всего лишь предоставляли понятные человеку коды операций и инструкции, записанные в символьном виде либо позволяли извлекать подпрограммы из библиотек и вставлять их в требуемый участок программного кода. Некоторые системы допускали интерпретацию операций для чисел с плавающей запятой и операций индексирования (indexing). Как бы то ни было, за исключением компилятора А-2 и алгебраической системы Лейнинга и Цирлера, до 1954 года даже наиболее мощные системы представляли собой всего лишь синтетические машины с кодом, отличающимся от машинного кода.

Эта модель обладала недостатками не только с технической, но и с экономической точки зрения. Оплата труда программистов вычислительного центра превышала стоимость самого компьютера, и этот разрыв неуклонно возрастал по мере того, как стоимость технологий и соответственно стоимость компьютеров снижалась. Кроме того, на программирование и отладку (debugging) тратилось от 25 до 50 % машинного времени. Системы автоматического программирования снижали быстродействие компьютера в 5—10 раз. Продавцы этих систем в худших традициях рынка стали завышать стоимость. Это привело к тому, что использование этих систем оказывалось невыгодным, и отношение к ним было скептическим.

В середине 1954 года в компании IBM под руководством Джона Бэкуса были начаты работы над языком Фортран (FORTRAN — FORmula TRANslation). Целью работ было решение всех вышеперечисленных проблем. При создании компилятора основное внимание уделялось генерации эффективного объектного кода, и эта задача была успешно решена. Качество объектного кода и преобразования, выполняемых для получения эффективных программ, удивили даже самих создателей языка FORTRAN.



Перфокарта с разметкой колонок для языка программирования Фортран.


С появлением языка Фортран появилась возможность записывать математические процедуры на четко определенном языке. Этот язык обеспечивал новый, более высокий уровень абстракции, поэтому программный код мог исполняться на разных компьютерах. Информация сохранялась в памяти и рассматривалась не как последовательность бит, а как целые или вещественные числа. В языке появились первые базовые конструкции императивных языков: условный оператор (IF <условие> <выражение_1_если_условие__истинно> <выражение_2_если_условие_ложно>) и оператор цикла (DO <инструкция> переменная = начальное значение, конечное значение, шаг).

За Фортраном последовали другие языки: Алгол-60 (одним из его создателей был голландский ученый Эдсгер Дейкстра), Кобол и LISP (предшественник функциональных языков программирования). Эти языки предназначались для решения определенных задач. В отличие от этих языков, язык PL/I был создан как язык общего назначения и содержал все нововведения, представленные в более ранних языках, что сделало его громоздким и сложным.



Компьютер Electrologica XI, работавший в период с 1958 по 1965 год, в котором использовался язык Алгол-60.


Авторы языков программирования ставили перед собой менее амбициозные задачи, но созданные ими языки оказались более эффективными. Среди них выделялись Simula 67 и Pascal. Вместо предопределенного полного множества абстракций эти языки обладали гибкими и удобными средствами определения новых произвольных абстракций. Pascal и Алгол-68 позволяли определять новые типы данных на основе предопределенных простых типов и служебных слов (array, record и других). Эти новые типы можно было рассматривать как абстракции, созданные на основе внутренних представлений, и им сопоставлялось множество операций. Эта модель была гибкой, но обладала существенным недостатком. Доступ к представлению предопределенных типов был закрыт, то есть с предопределенными объектами нельзя было работать напрямую (только с помощью операций), однако доступ к структуре пользовательских типов был открыт, и их значения можно было изменять. Причина заключалась в том, что в языке не было различий между двумя уровнями абстракции: уровнем, на котором программист использует тип данных, и уровнем реализации этого типа. Это осложняло чтение программ и исправление ошибок. Когда программы достигали определенных размеров, эта задача становилась невыполнимой.

Решением проблемы стало использование абстрактных типов данных и языков, в которых они поддерживались (Ada, Modula-2 и CLU). В них проводилось различие между этими уровнями абстракции и применялась так называемая инкапсуляция (ограничение доступа к определенным компонентам объектов). На уровне, на котором программист использовал тип, доступ к его внутренней структуре был закрыт. На уровне реализации определялся интерфейс объекта, его внутренняя структура и доступные операции.

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

Благодаря этим механизмам абстракции программы, написанные на этих языках, стало возможным представлять в терминах объектов. В некоторых языках, например в языке Ада и Modula-2, использование объектов было необязательным, в других — обязательным. В языке CLU программист должен был группировать данные приложения в классы, которые назывались кластерами. Аналогичный принцип использовался в объектно-ориентированных языках, в которых вводилось понятие наследования, позволявшее определять объекты на основе предопределенных объектов.

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

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

Первым языком, в котором данные и операции группировались в рамках единой сущности, был Simula I, предназначенный для решения задач симуляции. Он был разработан в Норвежском вычислительном центре под руководством математика и политика Кристена Нюгорда. Работы над первой версией языка были завершены в январе 1965 года. Следующая версия получила название Simula 67. Это был язык общего назначения, в котором были формализованы понятия объекта и класса и вводилось понятие наследования. Позднее в языке Smalltalk 80, который был создан на основе языка Simula и двух предыдущих версий (Smalltalk 72 и Smalltalk 76), понятие объекта было обобщено и объекты стали единственными сущностями, используемыми в языке. В начале 1970-х в научно-исследовательском центре Xerox Palo Alto Research Center, известном как Xerox PARC, была создана система Dynabook — персональное средство обработки информации с оконным интерфейсом, текстовыми меню, значками, то есть с полноценным графическим интерфейсом (англ. GUI — Graphical User Interface), очень похожим на современные. Dynabook был разработан американцем Аланом Кеем для обучения детей работе с компьютером. Работы были завершены в 1972 году. Программы в этой системе были написаны на языке BASIC, в них использовался механизм передачи сообщений, а также понятия класса и объекта, введенные в языке Simula.



Алан Кей получает степень почетного доктора испанского Университета Мурсии за вклад в развитие информатики. Торжественная церемония состоялась 28 января 2010 года.


Сейчас существует множество объектно-ориентированных языков программирования (Eiffel, C++ и другие), некоторые из которых являются расширенными и дополненными вариантами других языков. Так, C++ является расширенным вариантом языка С. Он был создан датским программистом Бьёрном Страуструпом и содержит классы, подобно языку Simula. Система CLOS была разработана с целью стандартизировать объектную систему языка Common LISP. Понятия объекта и наследования использовались в работах по созданию искусственного интеллекта при разработке языков для представления знаний, например KRL и KL-ONE, и языков с акторами, в частности Actl, Act2, Act3, ABCL/1 и других.

Абстракция и объекты применяются во всех языках программирования, появившихся в последние годы, как в объектно-ориентированных языках, например Java или Python, так и в процедурных, где используются объектно-ориентированные конструкции, например в языке РНР. Также появились языки, ориентированные на быструю разработку приложений, и сценарные языки. К ним относятся РНР и JavaScript, разработанные в последнее десятилетие XX века. Целью авторов этих языков было упростить и ускорить разработку программ. Разумеется, для небольших программ этого действительно удалось достичь, однако по сравнению с языками прошлого проектирование крупномасштабных программ усложнилось. Как бы то ни было, влияние объектно-ориентированных языков на разработку программ привело к появлению новых вспомогательных средств, например языков моделирования, подобных UML.

Категория: АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ | Добавил: admin | Теги: ИТК и мате, Мир Математики, искусственный интеллект, машинное обучение, популярная математик, математика и информатик, дидактический материал по матем
Просмотров: 506 | Загрузок: 0 | Рейтинг: 0.0/0
УЧИТЕЛЮ ИНФОРМАТИКИ
КОНСПЕКТЫ УРОКОВ
ВНЕКЛАССНЫЕ МЕРОПРИЯТИЯ ПО ИНФОРМАТИКЕ
ПОСОБИЯ И МЕТОДИЧКИ ДЛЯ УЧИТЕЛЯ ИНФОРМАТИКИ
ИЗ ОПЫТА РАБОТЫ УЧИТЕЛЯ ИНФОРМАТИКИ
ЗАДАНИЯ ШКОЛЬНОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ


ИНФОРМАТИКА В ШКОЛЕ


ИНФОРМАТИКА В НАЧАЛЬНЫХ КЛАССАХ
ИНФОРМАТИКА В 3 КЛАССЕ
ИНФОРМАТИКА В 4 КЛАССЕ
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 3 КЛАСС
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 4 КЛАСС
ПРОГРАММИРОВАНИЕ ДЛЯ ДЕТЕЙ
СКАЗКА "ПРИКЛЮЧЕНИЯ ЭЛЕКТРОШИ"
ИГРОВЫЕ ТЕХНОЛОГИИ НА УРОКАХ ИНФОРМАТИКИ
ВИКТОРИНЫ ПО ИНФОРМАТИКЕ
КОМПЬЮТЕРНЫЕ ЧАСТУШКИ
ОБРАТНАЯ СВЯЗЬ
Поиск


Друзья сайта
  • Создать сайт
  • Все для веб-мастера
  • Программы для всех
  • Мир развлечений
  • Лучшие сайты Рунета
  • Кулинарные рецепты

  • Copyright MyCorp © 2020
    Яндекс.Метрика Рейтинг@Mail.ru