Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Лекции - Высокоуровневые методы информатики и программирования (ВМИП) - файл 1.doc


Загрузка...
Лекции - Высокоуровневые методы информатики и программирования (ВМИП)
скачать (2205.5 kb.)

Доступные файлы (1):

1.doc2206kb.04.12.2011 09:12скачать

1.doc

  1   2   3   4   5   6   7   8   9   10   11
Реклама MarketGid:
Загрузка...
Лекции по дисциплине «Высокоуровневые методы информатики и программирования»
Курс лекций – 20 часов

Темы занятий

Количество часов

Раздел 1. Системы разработки и языки программирования.

1. Системы программирования. Иерархия языков программирования

2

2. Технологии программирования.

2

3. Язык программирования Delphi. Пакеты прикладных программ.

2

Раздел 2. Объектно-ориентированное программирование

4. Введение в объектно-ориентированное программирование.

2

5. Инкапсуляция. Наследование. Полиморфизм.

2

Раздел 3. Методы программирования и структуры данных

6. ^ Введение в методы программирования и структуры данных.

2

7 Структуры данных.

2

8 Создание сложных программных приложений.

2

9 Методы сортировки и поиска информации.

2

10 Программирование мультимедиа-приложений.

2


Лекция 1
^

СИСТЕМЫ ПРОГРАММИРОВАНИЯ. ИЕРАРХИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ. Парадигмы программирования


СИСТЕМЫ ПРОГРАММИРОВАНИЯ. ИЕРАРХИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ. Парадигмы программирования

1. Определение языка программирования

2. История языков программирования

3. Понятие парадигмы программирования

4. Императивное программирование

5. Параллельное и событийно-управляемое программирование

6. Объектно-ориентированное программирование

7. Функциональное программирование

8. Логическое программирование

1. Структурное программирование

  2. Модульное программирование

BEGIN

 3. Объектно-ориентированное программирование (ООП)

Type

1.1. Сортировка методом простого выбора

1.2. Сортировка методом простого обмена

1.3. Сортировка методом прямого включения

1.4. Сортировка методом слияний

1.5. Обменная сортировака с разделением (сортировка Хоара)

Сортировка

Сортировка методом простого выбора

Сортировка методом простого обмена

Сортировка методом прямого включения

Сортировка методом слияний

Обменная сортировка с разделением ( сортировка Хоара )

Алгоритмы поиска информации

Линейный поиск

Линейный поиск с использованием барьера

Бинарный поиск

Поиск подстроки в строке

Прямой поиск

Алгоритм Р. Бойера и Дж. Мура

Примеры

Список литературы

Основная:

  1. Петров А. и др. Вычислительная техника и программирование. Высшая школа, 1990.

  2. Епанешников А.. М. Епанешников В. А. Программирование в среде TURBO PASCAL 7.0. Диалог МИФИ, 1995г.

  3. В.В. Фаронов Delphi. Программирование на языке высокого уровня: Учебник для ВУЗОВ – СПб.: Питер, 2004.

  4. В. Гофман, А. Хоменко. Delphi 5. Наиболее полное руководство. СПБ: БХВ, 2000

  5. Попов В. Б. Паскаль и Дельфи. Самоучитель. – СПб.: Питер, 2004.

Дополнительная:

  1. Информатика, Учебник /Под ред. Макаровой Н.В. Москва, Финансы и статистика, 1997.

  2. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ. Мир, 1985.
^

1. Определение языка программирования


Прогресс компьютерных технологий определил процесс появления новых разнообразных знаковых систем для записи алгоритмов – языков программирования.

Дадим определение языку программирования. Согласно классическому учебнику «Курс программирования» Е. Жоголева и Н. Трифонова (М., «Наука», 1974): «Алгоритмический язык – это набор символов (алфавит языка), система правил образования из этих символов конструкций, с помощью которых представляются определенные компоненты алгоритма (синтаксис языка), и система правил истолкования этих конструкций, позволяющих однозначно воспроизводить процесс переработки данных (семантика языка)». Более кратко можно сказать, что «Назначение языка программирования состоит в хранении и передаче упорядоченных последовательностей инструкций, или алгоритмов».

Таким образом, язык программирования служит двум связанным между собой целям: он дает программисту аппарат для задания действий, которые должны быть выполнены, и формирует концепции, которыми пользуется программист, размышляя о том, что делать.

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

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

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

2. История языков программирования


Одной из самых революционных идей приведших к созданию автоматических цифровых вычислительных машин, была высказанная в 20-х годах 19 века Чарльзом Бебиджем мысль о предварительной записи порядка действия машины для последующей автоматической реализации вычислений – программе. И, хотя использованная Бебиджем запись программы на перфокартах, придуманная для управления такими станками французским изобретателем Жозефом Мари Жаккаром, технически не имеет ничего общего с современными приемами хранения программ в ПК, принцип здесь по существу один. С этого момента начинается история программирования.

^ Аду Левлейс, современницу Бебиджа, называют первым в мире программистом. Она теоретически разработала некоторые приемы управления последовательностью вычислений, которые используются в программировании и сейчас. Ею же была описана и одна из важнейших конструкций практически любого современного языка программирования – цикл.

Революционным моментом в истории языков программирования стало появление системы кодирования машинных команд с помощью специальных символов, предложенной Джоном Моучли. Система кодирования, предложенная им, вдохновила одну из его сотрудниц Грейс Мюррей Хоппер. При работе на компьютере «Марк-1» ей и ее группе пришлось столкнуться со многими проблемами и все, что ими придумано, было впервые. В частности они придумали подпрограммы. И еще одно фундаментальное понятие техники программирования впервые ввели Хоппер и ее группа – «отладка».

В конце 40-х годов Дж. Моучли создал систему под названием «Short Code», которая являлась примитивным языком программирования высокого уровня. В ней программист записывал решаемую задачу в виде математических формул, а затем, используя специальную таблицу, переводил символ за символом, преобразовывал эти формулы в двухлитерные коды. В дальнейшем специальная программа компьютера превращала эти коды в двоичный машинный код. Система, разработанная Дж. Моучли, считается одним из первых примитивных интерпретаторов.

Уже в 1951 г. Хоппер создала первый в мире компилятор и ею же был введен сам этот термин. Компилятор Хоппер осуществлял функцию объединения команд и в ходе трансляции производил организацию подпрограмм, выделение памяти компьютера, преобразование команд высокого уровня (в то время псевдокодов) в машинные команды. «Подпрограммы находятся в библиотеке (компьютера), а когда вы подбираете материал из библиотеки – это называется компиляцией» – так она объясняла происхождение введенного ею термина.

В 1954 году группа под руководством Г. Хоппер разработала систему, включающую язык программирования и компилятор, которая в дальнейшем получила название Math-Matic. После удачного завершения работ по созданию Math-Matic Хоппер и ее группа принялись за разработку нового языка и компилятора, который позволил бы пользователями программировать на языке, близком к обычному английскому. В 1958 г. появился компилятор Flow-Matic. Компилятор Flow-Matic был первым языком для задач обработки коммерческих данных.

Разработки в этом направлении привели к созданию языка Кобол (COBOL – Common Business Oriented Language). Он был создан в 1960 году. В этом языке по сравнению с Фортраном и Алголом, слабее развиты математические средства, но зато хорошо развиты средства обработки текстов, организация вывода данных в форме требуемого документа. Он задумывался как основной язык для массовой обработки данных в сферах управления и бизнеса.

Середина 50-х годов характеризуется стремительным прогрессом в области программирования. Роль программирования в машинных командах стала уменьшаться. Стали появляться языки программирования нового типа, выступающие в роли посредника между машинами и программистами. Первым и одним из наиболее распространенных был Фортран (FORTRAN, от FORmula TRANslator – переводчик формул), разработанный группой программистов фирмы IBM в 1954 году (первая версия). Этот язык был ориентирован на научно-технические расчеты математического характера и является классическим языком программирования при решении на ПК математических и инженерных задач.

Для первых языков программирования высокого уровня предметная ориентация языков была характерной чертой.

Особое место среди языков программирования занимает Алгол, первая версия которого появилась в 1958 году. Одним из разработчиков Алгола был «отец» Фортрана Джон Бэкус. Название языка ALGOrithmic Language подчеркивает то обстоятельство, что он предназначен для записи алгоритмов. Благодаря четкой логической структуре Алгол стал стандартным средством записи алгоритмов в научной и технической литературе.

В середине 60-х годов^ Томас Курц и Джон Камен (сотрудники математического факультета Дартмунтского колледжа) создали специализированный язык программирования, который состоял из простых слов английского языка. Новый язык назвали «универсальным символическим кодом для начинающих» (Beginner All-Purpose Symbolic Instruction Code, или, сокращенно, BASIC). Годом рождения нового языка можно считать 1964. Сегодня универсальный язык Бейсик (имеющий множество версий) приобрел большую популярность и получил широкое распространение среди пользователей ПК различных категорий во всем мире. В значительно мере этому способствовало то, что Бейсик начали использовать как встроенный язык персональных компьютеров, широкое распространение которых началось в конце 70-х годов. Однако Бейсик неструктурный язык, и поэтому он плохо подходит для обучения качественному программированию. Справедливости ради следует заметить, что последние версии Бейсика для ПК (например, QBasic) стали более структурными и по своим изобразительным возможностям приближаются к таким языкам, как Паскаль.

Разработчики ориентировали языки на разные классы задач, в той или иной мере привязывали их к конкретной архитектуре ПК, реализовывали личные вкусы и идеи. В 60-е годы были предприняты попытки преодолеть эту «разноголосицу» путем создания универсального языка программирования. Первым детищем этого направления стал PL/1 (Programm Language One), разработанный фирмой IBM в 1967 году. Этот язык претендовал на возможность решать любые задачи: вычислительные, обработки текстов, накопления и поиска информации. Однако он оказался слишком сложным, транслятор с него – недостаточно оптимальным и содержал ряд невыявленных ошибок.

Однако линия на универсализацию языков была поддержана. Старые языки были модернизированы в универсальные варианты: Алгол-68 (1968 г.), Фортран-77. Предполагалось, что подобные языки будут развиваться и усовершенствоваться, станут вытеснять все остальные. Однако ни одна из этих попыток не увенчалась успехом.

Язык ЛИСП появился в 1965 году. Основным в нем служит понятие рекурсивно определенных функций. Поскольку доказано, что любой алгоритм может быть описан с помощью некоторого набора рекурсивных функций, то ЛИСП по сути является универсальным языком. С его помощью ПК может моделировать достаточно сложные процессы, в частности – интеллектуальную деятельность людей.

Пролог разработан во Франции в 1972 году для решения проблем «искусственного интеллекта». Пролог позволяет в формальном виде описывать различные утверждения, логику рассуждений и заставляет ПК давать ответы на заданные вопросы.

Значительным событием в истории языков программирования стало создание в 1971 году языка Паскаль. Его автор – швейцарский ученый Никлаус Вирт. Вирт назвал его в честь великого французского математика и религиозного философа XVII века Блеза Паскаля, который изобрел первое суммирующее устройство, именно поэтому новому языку было присвоено его имя. Этот язык первоначально разрабатывался как учебный язык структурного программирования, и, действительно, сейчас он является одним из основных языков обучения программированию в школах и вузах.

В 1975 году два события стали вехами в истории программирования – ^ Билл Гейтс и Пол Аллен заявили о себе, разработав свою версию Бейсика, а Вирт и Йенсен выпустили классическое описание языка «Pascal User Manual and Report».

Не менее впечатляющей, в том числе и финансовой, удачи добился ^ Филип Кан, француз, разработавший в 1983 году систему Турбо-Паскаль. Суть его идеи состояла в объединении последовательных этапов обработки программы – компиляции, редактирования связей, отладки и диагностики ошибок – в едином интерфейсе. Турбо-Паскаль – это не только язык и транслятор с него, но еще и операционная оболочка, позволяющая пользователю удобно работать на Паскале. Этот язык вышел за рамки учебного предназначения и стал языком профессионального программирования с универсальными возможностями. В силу названных достоинств Паскаль стал источником многих современных языков программирования. С тех пор появилось несколько версий Турбо-Паскаля, последняя – седьмая.

Фирма Borland/Inprise завершила линию продуктов Турбо-Паскаль и перешла к выпуску системы визуальной разработки для Windows – Delphi.

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

Период с конца 60-х до начала 80-х годов характеризуется бурным ростом числа различных языков программирования, сопровождавшим кризис программного обеспечения. В январе 1975 года Пентагон решил навести порядок в хаосе трансляторов и учредил комитет, которому было предписано разработать один универсальный язык. В мае 1979 года был объявлен победитель – группа ученых во главе с Жаном Ихбиа. Победивший язык окрестили Ада, в честь Огасты Ады Левлейс. Этот язык предназначен для создания и длительного (многолетнего) сопровождения больших программных систем, допускает возможность параллельной обработки, управления процессами в реальном времени.


1950




1960


1970


1980


1990…

Рис. 1. История создания языков программирования


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

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

 языки программирования высокого (Паскаль, Бейсик) и низкого уровня (Ассемблер);

 строго типизированные (Паскаль) и нестрого типизированные (Бейсик);

 с поддержкой объектно-ориентированного программирования (Си++) и без и т. д.

Рассмотрим другую классификацию. Языки программирования делятся на:

1) Машинно-ориентированные языки:

 машинные языки;

 языки символического кодирования;

 автокоды;

 макрос.

2) Машинно-независимые языки:

 проблемно-ориентированные языки;

 универсальные языки;

 диалоговые языки;

 непроцедурные языки.

Машинно-ориентированные языки

Машинно-ориентированные языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ПК (внутреннего языка, структуры памяти и т. д.). Машинно-ориентированные языки имеют следующие особенности:

 высокое качество создаваемых программ (компактность и скорость выполнения);

 возможность использования конкретных аппаратных ресурсов;

 предсказуемость объектного кода и заказов памяти;

 для составления эффективных программ необходимо знать систему команд и особенности функционирования данного ПК;

 трудоемкость процесса составления программ (особенно на машинных языках и ЯСК), плохо защищенного от появления ошибок;

 низкая скорость программирования;

 невозможность непосредственного использования программ, составленных на этих языках, на ЭВМ других типов.

Машинно-ориентированные языки по степени автоматического программирования подразделяются на классы.

^ Машинный язык

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

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

^ Языки Символического Кодирования

Языки Символического Кодирования (далее ЯСК), так же, как и МЯ, являются командными. Однако коды операций и адреса в машинных командах, представляющие собой последовательность двоичных (во внутреннем коде) или восьмеричных (часто используемых при написании программ) цифр, в ЯСК заменены на символы (идентификаторы), форма написания которых помогает программисту легче запоминать смысловое содержание операции. Это обеспечивает существенное уменьшение числа ошибок при составлении программ.

Использование символических адресов – первый шаг к созданию ЯСК. Команды ПК вместо истинных (физических) адресов содержат символические адреса. По результатам составленной программы определяется требуемое количество ячеек для хранения исходных промежуточных и результирующих значений. Назначение адресов, выполняемое отдельно от составления программы в символических адресах, может проводиться менее квалифицированным программистом или специальной программой, что в значительной степени облегчает труд программиста.

Автокоды

Существуют языки, включающие в себя все возможности ^ ЯСК, посредством расширенного введения макрокоманд  они называются автокоды.

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

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

Обе указанных системы используют трансляторы с ЯСК и набор макрокоманд, которые также являются операторами автокода.

Развитые автокоды получили название ассемблеры. Сервисные программы и пр., как правило, составлены на языках типа ассемблер.
Макрос

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

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

Макрос одинаково может работать, как с программами, так и с данными.

Машинно-независимые языки

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

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

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

^ Проблемно-ориентированные языки

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

Проблемных языков очень много, например:

 Фортран, Алгол – языки, созданные для решения математических задач;

 Simula, Слэнг  для моделирования;

 Лисп, Снобол – для работы со списочными структурами.

Универсальные языки

Универсальные языки были созданы для широкого круга задач: коммерческих, научных, моделирования и т. д. Первый универсальный язык был разработан фирмой IBM, ставший в последовательности языков PL/1. Второй по мощности универсальный язык называется Алгол-68.

Диалоговые языки

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

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

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

Одним из примеров диалоговых языков является Бейсик.

^ Непроцедурные языки

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

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

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

Языки программирования служат разным целям, и их выбор определяется удобностью для пользователя, пригодностью для данного компьютера и данной задачи. А задачи для компьютера бывают самые разнообразные: вычислительные, экономические, графические, экспертные и т. д. Такая разнотипность решаемых компьютером задач и определяет многообразие языков программирования. В программировании наилучший результат достигается при индивидуальном подходе, исходящем из класса задачи, уровня и интересов программиста.
  1   2   3   4   5   6   7   8   9   10   11



Скачать файл (2205.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru