Контрольная работа по "Информатике"

Институт  дистанционного образования

Направление 221700 «Стандартизация и метрология» 

Кафедра компьютерных измерительных систем и метрологии. Институт кибернетики

 

 

 

 

 

 

 

 

ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ  № 1

по дисциплине «информатика и програмирование»

 

Вариант № 6

 

 

 

 

 

Выполнил студент гр.З-8Г21 Ефимова М.А.    ___________     __________

                                         (Фамилия И.О.)      (подпись)            (дата)

 

       Шифр зачетной книжки З-8Г21/14

 

 

 

 

Проверил преподаватель    Заревич А.И.      ___________    ___________

                                    (Фамилия И.О.)       (подпись)             (дата)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Томск 2013

Вопросы.

 

1.Язык программирования Pascal. Предпосылки появления, область применения, достоинства и недостатки.

 

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

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

Предпосылка появления является Международная федерация по обработке информации когда IFIP  которая в 1965 г., предложила нескольким специалистам в области информатики принять участие в разработке нового языка программирования — преемника АЛГОЛа-60. Среди них был швейцарский ученый, работавший в то время доцентом на факультете информатики Стэнфордского университета Никалаус Вирт, который принял участие в разработке проекта языка под названием АЛГОЛ-W. И хотя IFIP отклонила этот проект (был принят проект АЛГОЛ-68 — автор Аад ван Вейнгаартен), Никалаус Вирт по возвращению в Швейцарию в 1967 г. не прекратил работу по созданию нового языка. В результате этой работы в конце 1968 г. профессор Вирт и его сотрудники из Швейцарского федерального института технологии ETH в Цюрихе разработали первую версию ПАСКАЛЯ, а спустя два года был создан и опубликован паскаль как небольшой и эффективный язык программирования. Создавая паскаль Н. Вирт преследовал две цели: во-первых, разработать язык, пригодный для обучения программированию как систематической дисциплине; во-вторых, реализация языка должна быть эффективной и надежной на существующих вычислительных машинах.

Как и всякий преемник, паскаль  имеет многие черты тех программ что были созданы ранее это такие как алголь-60 и некоторых других. Как и алголь-60, он имеет блочную структуру, т. е. программы составляются из блоков, которые начинаются и оканчиваются словами begin и end. Конкретно касаясь этого нельзя сказать на сколько удобен паскаль по скольку много отзывов касаясь его использования откликаються о нем как и с хорошей стороны так и с плохой.  Операторы языка паскаль, как и в алголе-60, разделяются между собой точкой с запятой. Аналогично алголу и фортратуну в языке имеется оператор перехода, а оператор варианта выполняет те же функции, что и переключатель в алголу или вычисляемый оператор перехода в фортране . Простые и гибкие операторы цикла while и repeat и оператор варианта case, отмечает Вирт, обладают переработанной версией оператора цикла for (также заимствованным из алгола ) они позволяют программисту выразить все, что ему нужно путем использования вложенных иерархических структур, представляющих композиции этих операторов.

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

Другие достоинства языка  были предопределены двумя основополагающими  статьями профессора Ч. Хоара, опубликованными  на рубеже 60-70-х годов: «О структурной  организации данных» и «Аксиоматическая основа программирования для вычислительных машин».

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

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

Язык паскаль , очевидно, явился на тот момент первым языком, для которого имеются программные средства, позволяющие доказывать правильность написанных программ.

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

При создании и совершенствовании  языка паскаль Н. Вирт ввел много новшеств, в частности: изобрел синтаксические диаграммы, с помощью которых удобно представлять конструкции языка; ввел, очевидно, первый в алфавит языка квадратные скобки; высказал идею решения проблемы переносимости программ в виде пи-систем (P-system), которая заключается в том, что написанные на паскале программы транслируются в пи-код (p-code) - в машинный язык некоторой идеальной машины а затем интерпретируется на реальных машинных языках.

Опыт использования языка  паскаль выявил ряд недостатков. В языке отсутствовали многие известные конструкции, такие, как: динамические массивы; возможность задания локальных переменных; понятие отдельно транслируемого модуля, затруднившие тем самым создание больших программ; операция возведения в степень; возможность включения в программу участков, написанных на машинном языке, и т. д. Одни программисты могли продолжить список недостатков ПАСКАЛЯ, другие возразить, что некоторые недостатки в их реализации отсутствуют. Такой разнобой мнений, как пишет О. Перминов, свидетельствует о том, что долгое время отсутствовал документ, который бы точно фиксировал состав и правила выполнения и правила выполнения языка. Такой документ появился только в 1982 г. — международный стандарт ISO на язык паскаль. Этот стандарт соответствует авторскому «стандартному определению» язык, изложенному в книге Йенсена и Вирта «паскаль. Руководство для пользователя и описание языка», но дает более полное и строгое описание некоторых деталей, опущенных в руководстве.

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

Уксд-паскаль (UCSD-PACKAL; UCSD-Universiti of California, San Diego) был разработан сотрудником Калифорнийского университета в Сан-Диего К. Бауэлсом уксд-паскаль является расширением стандартного определения языка и предназначен главным образом для мини- и микро-ЭВМ.

Эппл-ПАСКАЛЬ (Apple-pascal), разработанный для персональных компьютеров «Apple», по существу, является модификацией уксд-паскаля, однако в нем имеются дополнительные средства, в частности средства для графического отображения.

Компилятор паскаль-80 разработан фирмой Microsoft для операционной системы СР/М-80, используемой В 8-разрядных персональных компьютерах. Этот компилятор допускает раздельную компиляцию файлов и использование программных модулей, созданных и откомпилированных в других системах программирования.

Особую популярность на микро-ЭВМ  и персональных ЭВМ в настоящие  время получило семейство паскаль-систем, названное турбо-паскаль(Turbo-Pascal) и разработанное фирмой Borland. Данное семейство, работающее с операционными системами СР/М-80, MS DOS, MSX DOS, имеет высокую производительность (используется ускоренная однопроходная процедура компиляции) и широко променяется пользователями персональных ЭВМ IBM PC XT/AT и совместными с ними компьютерами. Фирма Borland создала несколько версий Turbo-pascal, среди последних версия НО, которая включает пакет стандартной графики, позволяющий работать с различными графическими адаптерами IBM PC, и Turbo-pascal версий 5.0 и 5.5, назначением которых является объектно-ориентированное программирование.

Одновременно с появлением пятой версии Turbo-pascal конкурирующая фирма Microsoft выпустила версию 1.0 языка quick -pascal (Quick-pascal-быстрый паскаль), полностью совместимою с Turbo-pascal , и как заявляют сотрудники фирмы, в полтора раза дешевле последнего.

Известны аппаратные реализации языка паскаля Так, в 1983 г. инженеры японской фирмы Mitsubishi разработали аппаратный компилятор, состоящий из четырех однокристальных блоков и устройства управления шиной. Как утверждают создатели компилятора, язык паскаль выбран потому, что его «регулярная структура делает возможной строго последовательную компиляцию, т. е. компиляцию, не требующую опережающего просмотра для обработки текущего предложения». Паскаль стал прародителем более поздних языков программирования. Через 10 лет после паскаля Никалаус Вирт создал язык Модула-2 который основал на многих концепциях, введенных в паскале, хотя особое внимание в нем уделяется построению программы как набора независимых модулей. На паскаль все четыре языка, принятые в конце 70-х годов министерством обороны США для разработки своего универсального высокоуровневого языка, который в дальнейшем получил название Ада. Хотя язык Ада в значительной степени отличается от

паскаля, в нем сохранено много удачных черт последнего.

В заключение хотелось бы привести некоторые высказывания о языке  ПАСКАЛЬ. Надо отметить, что среди  восторженных иногда встречаются и довольно резкие суждения (см., напр., Datamation. — 1984. — july).

Итак, вот что писали в 1977 г. ч. Хоар и другие: » В настоящие  время язык ПАСКАЛЬ является лучшим языком программирования общего назначения для целей системного программирования и реализации программного обеспечения. Открытие того, что преимущества языка  программирования высокого уровня могут  быть скомбинированы таким простым  и элегантным способом, как это  сделано в языке ПАСКАЛЬ, явилось  откровением, заслуживающим названия крупнейшего открытия. Следствием необычайного успеха языка программирования ПАСКАЛЬ, который на много превзошел все  ожидания его автора, явилось то, что оценка языков программирования высокого уровня теперь производится на совершенно ином, намного высоком уровне».

А несколько лет спустя Н. Дейтел написал следующие: «Некоторые научные школы по информатике стали постепенно освобождаться от чар «изворотливой смекалистости», заложенной в обученных ПАСКАЛЮ студентов. Для некоторых приложений язык настолько скуден, что пользователи вынуждены встраивать возможности, общедоступные на других языках».

 

 

2.Организация данных в форме списка, виды списков.

 

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

    Списком называется последовательность элементов x1, …, xn, где n ≥ 0. В случае n = 0 список называется пустым. Элементы списка могут иметь произвольную структуру. В частности, любой элемент может также представлять собой список, называемый в этом случае подсписком. Если список содержит подсписки, его называют списковой структурой. Список без подсписков называют последовательным списком. Определенные позиции списка имеют специальное назначение. Например, первая позиция называется заголовком списка. Метод программирования, в основе которого лежат операции со списками, называется обработкой списков. Существует два основных вида списков: распределенные и связные.

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

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

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

Односвязный список (Однонаправленный связный список).

 Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.

Двусвязный список (Двунаправленный  связный список)

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

 

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

 

Реализация такой структуры  происходит на базе линейного списка. В каждом кольцевом списке есть указатель  на первый элемент. В этом списке константы NULL не существует.