Эффективность алгоритма ПрВыб

В лучшем случае (если исходная последовательность уже упорядочена), алгоритм ПрВыб произведёт (N - 1) * (N + 2) / 2 сравнений и 0 пересылок данных. В остальных же случаях количество сравнений останется прежним, а вот количество пересылок элементов массива будет равным 3 * (N - 1).

Таким образом, алгоритм ПрВыб имеет квадратичную сложность (~N2) по сравнениям и линейную (~N) — по пересылкам.

Замечание. Если перед вами поставлена задача отсортировать строки двумерного массива (размерности NxN) по значениям его первого столбца, то сложность алгоритма ПрВыб, модифицированного для решения этой задачи, будет квадратичной (N2 сравнений и N2 пересылок), а алгоритма БинВст — кубической (N*log N сравнений и N3 пересылок). Комментарии, как говорится, излишни.

БИЛЕТ №19

№19 1. Итерационные циклы: бесконечное произведение см билет 6 пункт 1

Эволюция языков программирования

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

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

Ассемблер

Первым значительным шагом представляется переход к языку ассемблера (позволим себе маленькое лирическое отступление: английское название assembly language, или assembler, на русский переводят именно тем термином, который был использован выше. При этом у новичка создается впечатление, что язык назван в честь некоего человека по имени ассемблер. Достаточно забавная ситуация, не правда ли?). Не очень заметный, казалось бы, шаг — переход к символическому кодированию машинных команд — имел на самом деле огромное значение. Программисту не надо было больше вникать в хитроумные способы кодирования команд на аппаратном уровне. Более того, зачастую одинаковые по сути команды кодировались совершенно различным образом в зависимости от своих параметров (широко известный пример из мира современных компьютеров — это кодирование инструкции mov в процессорах Intel: существует несколько совершенно по-разному кодируемых вариантов команды; выбор того или иного варианта зависит от операндов, хотя суть выполняемой операции неизменна: поместить содержимое (или значение) второго операнда в первый). Появилась также возможность использования макросов и меток, что также упрощало создание, модификацию и отладку программ. Появилось даже некое подобие переносимости — существовала возможность разработки целого семейства машин со сходной системой команд и некоего общего ассемблера для них, при этом не было нужды обеспечивать двоичную совместимость.

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

Фортран

В 1954 году в недрах корпорации IBM группой разработчиков во главе с Джоном Бэкусом (John Backus) был создан язык программирования Fortran. Значение этого события трудно переоценить. Это первый язык программирования высокого уровня. Впервые программист мог по-настоящему абстрагироваться от особенностей машинной архитектуры. Ключевой идеей, отличающей новый язык от ассемблера, была концепция подпрограмм. Напомним, что это современные компьютеры поддерживают подпрограммы на аппаратном уровне, предоставляя соответствующие команды и структуры данных (стек) прямо на уровне ассемблера, в 1954 же году это было совершенно не так. Поэтому компиляция Fortran’а была процессом отнюдь не тривиальным. Кроме того, синтаксическая структура языка была достаточно сложна для машинной обработки в первую очередь из-за того, что пробелы как синтаксические единицы вообще не использовались. Это порождало массу возможностей для скрытых ошибок, таких, например:

В Фортране следующая конструкция описывает «цикл for до метки 10 при изменении индекса от 1 до 100»: DO 10 I=1,100

Если же здесь заменить запятую на точку, то получится оператор присваивания:

DO10I = 1.100

Говорят, что такая ошибка заставила ракету взорваться во время старта!

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

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

Cobol

В 1960 году был создан язык программирования Cobol. Он задумывался как язык для создания коммерческих приложений, и он стал таковым. На Коболе написаны тысячи прикладных коммерческих систем. Отличительной особенностью языка является возможность эффективной работы с большими массивами данных, что характерно именно коммерческих приложений. Популярность Кобола столь высока, что даже сейчас, при всех его недостатках (по структуре и замыслу Кобол во многом напоминает Фортран) появляются новые его диалекты и реализации. Так недавно появилась реализация Кобола, совместимая с Microsoft.NET, что потребовало, вероятно, внесения в язык некоторых черт объектно-ориентированного языка.

PL/1

В 1964 году все та же корпорация IBM создала язык PL/1, который был призван заменить Cobol и Fortran в большинстве приложений. Язык обладал исключительным богатством синтаксических конструкций. В нем впервые появилась обработка исключительных ситуаций и поддержка параллелизма. Надо заметить, что синтаксическая структура языка была крайне сложной. Пробелы уже использовались как синтаксические разделители, но ключевые слова не были зарезервированы. В частности, следующая строка — это вполне нормальный оператор на PL/1:IF ELSE=THEN THEN THEN; ELSE ELSE

В силу таких особенностей разработка компилятора для PL/1 была исключительно сложным делом. Язык так и не стал популярен вне мира IBM.

BASIC

В 1963 году в Дартмурском колледже (Dartmouth College) был создан язык программирования BASIC (Beginners’ All-Purpose Symbolic Instruction Code — многоцелевой язык символических инструкций для начинающих). Язык задумывался в первую очередь как средство обучения и как первый изучаемый язык программирования. Он предполагался легко интерпретируемым и компилируемым. Надо сказать, что BASIC действительно стал языком, на котором учатся программировать (по крайней мере, так было еще несколько лет назад; сейчас эта роль отходит к Pascal). Было создано несколько мощных реализаций BASIC, поддерживающих самые современные концепции программирования (ярчайший пример — Microsoft Visual Basic).

Algol

В 1960 году командой во главе с Петером Науром (Peter Naur) был создан язык программирования Algol. Этот язык дал начало целому семейству Алгол-подобных языков (важнейший представитель — Pascal). В 1968 году появилась новая версия языка. Она не нашла столь широкого практического применения, как первая версия, но была весьма популярна в кругах теоретиков. Язык был достаточно интересен, так как обладал многими уникальными на так момент характеристиками.

Дальнейшее развитие языков программирования

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

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

Pascal-подобные языки

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

Отрицательной чертой языка было отсутствие в нем средств для разбиения программы на модули. Вирт осознавал это и разработал язык Modula-2 (1978), в котором идея модуля стала одной из ключевых концепций языка. В 1988 году появилась Modula-3, в которую были добавлены объектно-ориентированные черты. Логическим продолжением Pascal и Modula являются язык Oberon и Oberon-2. Они характеризуются движением в сторону объектно- и компонентно-ориентированности.

C-подобные языки

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

В 1986 году Бьярн Страуструп создал первую версию языка C++, добавив в язык C объектно-ориентированные черты, взятые из Simula (см. ниже), и исправив некоторые ошибки и неудачные решения языка. C++ продолжает совершенствоваться и в настоящее время, так в 1998 году вышла новая (третья) версия стандарта, содержащая в себе некоторые довольно существенные изменения. Язык стал основой для разработки современных больших и сложных проектов. У него имеются, однако же, и слабые стороны, вытекающие из требований эффективности.

В 1995 году в корпорации Sun Microsystems Кеном Арнольдом и Джеймсом Гослингом был создан язык Java. Он наследовал синтаксис C и C++ и был избавлен от некоторых неприятных черт последнего. Отличительной особенностью языка является компиляция в код некоей абстрактной машины, для которой затем пишется эмулятор (Java Virtual Machine) для реальных систем. Кроме того, в Java нет указателей и множественного наследования, что сильно повышает надежность программирования.

В 1999–2000 годах в корпорации Microsoft был создан язык C#. Он в достаточной степени схож с Java (и задумывался как альтернатива последнему), но имеет и отличительные особенности. Ориентирован, в основном, на разработку многокомпонентных Интернет-приложений.

Языки Ada и Ada 95

В 1983 году под эгидой Министерства Обороны США был создан язык Ada. Язык замечателен тем, что очень много ошибок может быть выявлено на этапе компиляции. Кроме того, поддерживаются многие аспекты программирования, которые часто отдаются на откуп операционной системе (параллелизм, обработка исключений). В 1995 году был принят стандарт языка Ada 95, который развивает предыдущую версию, добавляя в нее объекно-ориентированность и исправляя некоторые неточности. Оба этих языка не получили широкого распространения вне военных и прочих крупномасштабных проектов (авиация, железнодорожные перевозки). Основной причиной является сложность освоения языка и достаточно громоздкий синтаксис (значительно более громоздкий, чем Pascal).

Языки обработки данных

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

APL

В 1957 году была предпринята попытка создания языка для описания математической обработки данных. Язык был назван APL (Application Programming Language). Его отличительной особенностью было использование математических символов (что затрудняло применение на текстовых терминалах; появление графических интерфейсов сняло эту проблему) и очень мощный синтаксис, который позволял производить множество нетривиальных операций прямо над сложными объектами, не прибегая к разбиению их на компоненты. Широкому применению помешало, как уже отмечалось, использование нестандартных символов как элементов синтаксиса.

Snobol и Icon

В 1962 году появился язык Snobol (а в 1974 — его преемник Icon), предназначенный для обработки строк. Синтаксис Icon напоминает С и Pascal одновременно. Отличие заключается в наличии мощных встроенных функций работы со строками и связанная с этими функциями особая семантика. Современным аналогом Icon и Snobol является Perl — язык обработки строк и текстов, в который добавлены некоторые объектно-ориентированные возможности. Считается очень практичным языком, однако ему недостает элегантности.

SETL

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

Lisp и ему подобные языки

В 1958 году появился язык Lisp — язык для обработки списков. Получил достаточно широкое распространение в системах искусственного интеллекта. Имеет несколько потомков: Planner (1967), Scheme (1975), Common Lisp (1984). Многие его черты были унаследованы современными языками функционального программирования.

Скриптовые языки

Javascript

Язык был создан в компании Netscape Communications в качестве языка для описания сложного поведения веб-страниц. Первоначально назывался LiveScript, причиной смены названия получили маркетинговые соображения. Интерпретируется браузером во время отображения веб-страницы. По синтаксису схож с Java и (отдаленно) с C/C++. Имеет возможность использовать встроенную в браузер объектную функциональность, однако подлинно объектно-ориентированным языком не является.

VBScript

Язык был создан в корпорации Microsoft во многом в качестве альтернативы javascript. Имеет схожую область применения. Синтаксически схож с языком Visual Basic (и является усеченной версией последнего). Так же, как и JacaScript, исполняется браузером при отображении веб-страниц и имеет ту же степень объектно-ориентированности.

Perl

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

Python

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

 

 

БИЛЕТ №20

1. Отладка программы в ИСП ТР

2. Защита от зацикливания в программе