Алгоритм
Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
В старой трактовке алгори́тм — это точный набор инструкций, описывающих последовательность действий некоторого исполнителя для достижения результата, решения некоторой задачи. По мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что какие-то действия алгоритма должны быть выполнены только друг за другом, но какие-то могут быть и независимыми.

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

Содержание [убрать]
1 Определения алгоритма
2 Формальные признаки алгоритмов
3 История термина
4 Литература
5 См. также
6 Ссылки



[править] Определения алгоритма
Единого «истинного» определения понятия «алгоритм» нет.

«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.» (А. Колмогоров)

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

«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд.» (Угринович Николай Дмитриевич)

«Алгоритм — это последовательность действий, направленных на получение определённого результата.» ([поставьте сюда правильный copyright])

«Алгоритм есть формализованная последовательность действий (событий). Алгоритм может быть записан словами и изображен схематически. Практически любое неслучайное повторяемое действие поддается описанию через алгоритм.» ([grey_olli])

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

«Алгоритм — это система операторов, взятых из множества операторов некоторого исполнителя, которая полностью определяет некоторый класс алгоритмических процессов, то есть процессов, которые:

дискретны;
детерминированы;
потенциально конечны;
преобразовывают некоторые конструктивные объекты.
Между операторами алгоритма и операциями (элементарными действиями) алгоритмического процесса существует гомоморфное соответствие. Поэтому алгоритм следует также считать моделью алгоритмического процесса». (А. Копаев)


[править] Формальные признаки алгоритмов
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

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


[править] История термина
Современное формальное определение алгоритма было дано в 30-50-х гг. XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.

Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 г. он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, арабский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском»). По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алгебра.

Таким образом, мы видим, что латинизированное имя среднеазиатского ученого было вынесено в заглавие книги, и сегодня ни у кого нет сомнений, что слово «алгоритм» попало в европейские языки именно благодаря этому сочинению. Однако вопрос о его смысле длительное время вызывал ожесточённые споры. На протяжении многих веков происхождению слова давались самые разные объяснения.

Одни выводили algorism из греческих algiros (больной) и arithmos (число). Из такого объяснения не очень ясно, почему числа именно «больные». Или же лингвистам больными казались люди, имеющие несчастье заниматься вычислениями? Своё объяснение предлагал и энциклопедический словарь Брокгауза и Ефрона. В нём алгорифм (кстати, до революции использовалось написание алгориθм, через фиту) производится «от арабского слова Аль-Горетм, то есть корень». Разумеется, эти объяснения вряд ли можно счесть убедительными.

Такого рода языковые упражнения могут приводить к самым произвольным и нелепым выводам. Можно вспомнить, как в начале XIX века санкт-петербургский профессор Я. В. Толмачёв, стараясь доказать исконно русское происхождение некоторых слов, производил слово «кабинет» не от французского cabinet, а от фразы «как бы нет». В самом деле, писал он, человек заходит в кабинет и исчезает с наших глаз. Его «как бы нет». Ещё более курьезным было его объяснение слова «республика». Согласно Толмачёву, кровожадные низвергатели тронов кричали: «Режь публику!», откуда и произошло наименование республиканской формы правления…

Упомянутый выше перевод сочинения аль-Хорезми стал первой ласточкой, и в течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр. И все они в названии имели слово algoritmi или algorismi.

Про аль-Хорезми позднейшие авторы ничего не знали, но поскольку первый перевод книги начинается словами: «Dixit algorizmi: …» («Аль-Хорезми говорил: …»), всё ещё связывали это слово с именем конкретного человека. Очень распространённой была версия о греческом происхождении книги. В англо-норманской рукописи XIII века, написанной в стихах, читаем:

"Алгоризм был придуман в Греции. Это часть арифметики. Придуман он был мастером по имени Алгоризм, который дал ему своё имя. И поскольку его звали Алгоризм, Он назвал свою книгу «Алгоризм».

Около 1250 года английский астроном и математик Иоанн Сакробоско написал труд по арифметике «Algorismus vulgaris», на столетия ставший основным учебником по вычислениям в десятичной позиционной системе счисления во многих европейских университетах. Во введении Сакробоско назвал автором науки о счёте мудреца по имени Алгус (Algus). А в популярной средневековой поэме «Роман о розе» (1275—1280) Жана де Мена «греческий философ Алгус» ставится в один ряд с Платоном, Аристотелем, Евклидом и Птолемеем! Встречался также вариант написания имени Аргус (Argus). И хотя, согласно древнегреческой мифологии, корабль «Арго» был построен Ясоном, именно этому Арго приписывалось строительство корабля.

«Мастер Алгус» (или Аргус) стал в средневековой литературе олицетворением счетного искусства. И в уже упоминавшейся «Поэме о розе», и в известной итальянской поэме «Цветок», написанной Дуранте, имеются фрагменты, в которых говорится, что даже «mestre Argus» не сумеет подсчитать, сколько раз ссорятся и мирятся влюблённые. Великий английский поэт Джефри Чосер в поэме «Книга герцогини» (1369 г.) пишет, что даже «славный счётчик Аргус» (noble countour Argus) не сможет счесть чудовищ, явившихся в кошмарных видениях герою.

Впрочем, греческая версия была не единственной. Мифический Алгор (Algor) именовался то королем Кастилии (Rex quodam Castelliae), то индийским королем, то арабским мудрецом (philosophus Algus nomine Arabicus).

Однако со временем такие объяснения всё менее занимали математиков, и слово algorism (или algorismus), неизменно присутствовавшее в названиях математических сочинений, обрело значение способа выполнения арифметических действий посредством арабских цифр, то есть на бумаге, без использования абака. Именно в таком значении оно вошло во многие европейские языки. Например, с пометкой «устар.» оно присутствует в представительном словаре английского языка Webster’s New World Dictionary, изданном в 1957 г.

Алгоритм — это искусство счёта с помощью цифр, но поначалу слово «цифра» относилось только к нулю. Знаменитый французский трувер Готье де Куэнси (Gautier de Coincy, 1177—1236) в одном из стихотворений использовал слова algorismus-cipher (которые означали цифру 0) как метафору для характеристики абсолютно никчёмного человека. Очевидно, понимание такого образа требовало соответствующей подготовки слушателей, а это означает, что новая система счисления уже была им достаточно хорошо известна.

Многие века абак был фактически единственным средством для практичных вычислений, им пользовалисьи купцы, и менялы, и учёные. Достоинства вычислений на счётной доске разъяснял в своих сочинениях такой выдающийся мыслитель, как Герберт Аврилакский (938—1003), ставший в 999 г. папой римским под именем Сильвестра II. Новое с огромным трудом пробивало себе дорогу, и в историю математики вошло упорное противостояние лагерей абацистов и алгорисмиков (первых иногда еще называли гербекистами), которые пропагандировали использование для вычислений вместо абака арабских цифр. Интересно, что известный французский математик Никола Шюке (Nicolas Chuquet, 1445—1488) в реестр налогоплательщиков города Лиона был вписан как алгорисмик (algoriste). Но прошло не одно столетие, прежде чем новый способ счёта окончательно утвердился, столько времени потребовалось, чтобы выработать общепризнанные обозначения, усовершенствовать и приспособить к записи на бумаге методы вычислений. В Западной Европе учителей арифметики вплоть до XVII века продолжали называть «магистрами абака», как, например, математика Никколо Тарталью (1500—1557).

Итак, сочинения по искусству счёта назывались Алгоритмами. Из многих сотен можно выделить и такие необычные, как написанный в стихах трактат «Carmen de Algorismo» (латинское carmen и означает стихи) Александра де Вилла Деи (Alexander de Villa Dei, ум. 1240) или учебник венского астронома и математика Георга Пурбаха (Georg Peurbach, 1423—1461) «Opus algorismi jocundissimi» («Веселейшее сочинение по алгоритму»).

Постепенно значение слова расширялось. Ученые начинали применять его не только к сугубо вычислительным, но и к другим математическим процедурам. Например, около 1360 г. французский философ Николай Орем (Nicolaus Oresme, 1323/25-1382) написал математический трактат «Algorismus proportionum» («Вычисление пропорций»), в котором впервые использовал степени с дробными показателями и фактически вплотную подошёл к идее логарифмов. Когда же на смену абаку пришёл так называемый счёт на линиях, многочисленные руководства по нему стали называть «Algorithmus linealis», то есть правила счёта на линиях.

Можно обратить внимание на то, что первоначальная форма algorismi спустя какое-то время потеряла последнюю букву, и слово приобрело более удобное для европейского произношения вид algorism. Позднее и оно, в свою очередь, подверглось искажению, скорее всего, связанному со словом arithmetic.

В 1684 году Готфрид Лейбниц в сочинении «Nova Methodvs pro maximis et minimis, itemque tangentibus…» впервые использовал слово «алгоритм» (Algorithmo) в ещё более широком смысле: как систематический способ решения проблем дифференциального исчисления.

В XVIII веке в одном из германских математических словарей, Vollstandiges mathematisches Lexicon (изданном в Лейпциге в 1747 г.), термин algorithmus всё ещё объясняется как понятие о четырёх арифметических операциях. Но такое значение не было единственным, ведь терминология математической науки в те времена ещё только формировалась. В частности, выражение algorithmus infinitesimalis применялось к способам выполнения действий с бесконечно малыми величинами. Пользовался словом алгоритм и Леонард Эйлер, одна из работ которого так и называется — «Использование нового алгоритма для решения проблемы Пелля» («De usu novi algorithmi in problemate Pelliano solvendo»). Мы видим, что понимание Эйлером алгоритма как синонима способа решения задачи уже очень близко к современному.

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

Историки датируют 1691 годом один из списков древнерусского учебника арифметики, известного как «Счётная мудрость». Это сочинение известно во многих вариантах (самые ранние из них почти на сто старше) и восходит к еще более древним рукописям XVI в. По ним можно проследить, как знание арабских цифр и правил действий с ними постепенно распространялось на Руси. Полное название этого учебника — «Сия книга, глаголемая по еллински и по гречески арифметика, а по немецки алгоризма, а по русски цифирная счётная мудрость».

Таким образом, слово «алгоритм» понималось первыми русскими математиками так же, как и в Западной Европе. Однако его не было ни в знаменитом словаре В. И. Даля, ни спустя сто лет в «Толковом словаре русского языка» под редакцией Д. Н. Ушакова (1935 г.). Зато слово «алгорифм» можно найти и в популярном дореволюционном Энциклопедическом словаре братьев Гранат, и в первом издании Большой Советской Энциклопедии (БСЭ), изданном в 1926 г. И там, и там оно трактуется одинаково: как правило, по которому выполняется то или иное из четырёх арифметических действий в десятичной системе счисления. Однако к началу XX в. для математиков слово «алгоритм» уже означало любой арифметический или алгебраический процесс, выполняемый по строго определённым правилам, и это объяснение также даётся в БСЭ.

Совершенно неожиданное объяснение слова мы обнаруживаем в энциклопедии Брокгауза-Ефрона. В ней сказано, что «Русское слово „обозначение“ вполне соответствует точному значению слова А.» Очень трудно понять, откуда автор энциклопедической статьи взял это объяснение, как нам кажется, вряд ли верное. А это означает, что даже к сведениям, приводимым в самом авторитетном энциклопедическом издании, следует относиться внимательно, по возможности перепроверяя их!

Алгоритмы становились предметом все более пристального внимания ученых, и постепенно это понятие заняло одно из центральных мест в современной математике. Что же касается людей, от математики далеких, то к началу сороковых годов это слово они могли услышать разве что во время учебы в школе, в сочетании «алгоритм Евклида». Несмотря на это, алгоритм все еще воспринимался как термин сугубо специальный, что подтверждается отсутствием соответствующих статей в менее объёмных изданиях. В частности, его нет даже в десятитомной Малой Советской Энциклопедии (1957 г.), не говоря уже об однотомных энциклопедических словарях. Но зато спустя десять лет, в третьем издании Большой советской энциклопедии (1969 г.) алгоритм уже характеризуется как одна из основных категорий математики, «не обладающих формальным определением в терминах более простых понятий, и абстрагируемых непосредственно из опыта». Как мы видим, отличие даже от трактовки первым изданием БСЭ разительное! За сорок лет алгоритм превратился в одно из ключевых понятий математики, и признанием этого стало включение слова уже не в энциклопедии, а в словари. Например, оно присутствует в академическом «Словаре русского языка» (1981 г.) именно как термин из области математики.

Одновременно с развитием понятия алгоритма постепенно происходила и его экспансия из чистой математики в другие сферы. И начало ей положило появление компьютеров, благодаря которому слово «алгоритм» обрело новую жизнь. Вообще можно сказать, что его сегодняшняя известность напрямую связана со степенью распространения компьютеров. Например, в третьем томе «Детской энциклопедии» (1959 г.) о вычислительных машинах говорится немало, но они еще не стали чем-то привычным и воспринимаются скорее как некий атрибут светлого, но достаточно далекого будущего. Соответственно и алгоритмы ни разу не упоминаются на её страницах. Но уже в начале 70-х гг. прошлого столетия, когда компьютеры перестали быть экзотической диковинкой, слово «алгоритм» стремительно входит в обиход. Это чутко фиксируют энциклопедические издания. В «Энциклопедии кибернетики» (1974 г.) в статье «Алгоритм» он уже связывается с реализацией на вычислительных машинах, а в «Советской военной энциклопедии (1976 г.) даже появляется отдельная статья „Алгоритм решения задачи на ЭВМ“. За последние полтора-два десятилетия компьютер стал неотъемлемым атрибутом нашей жизни, компьютерная лексика становится все более привычной. Слово „алгоритм“ в наши дни известно, вероятно, каждому. Оно уверенно шагнуло даже в разговорную речь, и сегодня мы нередко встречаем в газетах и слышим в выступлениях политиков выражения вроде „алгоритм поведения“, „алгоритм успеха“ или даже „алгоритм предательства“. Академик Н. Н. Моисеев назвал свою книгу „Алгоритмы развития“, а известный врач Н. М. Амосов — „Алгоритм здоровья“ и „Алгоритмы разума“. А это означает, что слово живет, обогащаясь все новыми значениями и смысловыми оттенками.


[править] Литература
Томас Х. Кормен и др. Алгоритмы: построение и анализ, 2-е изд. — М.:»Вильямс", 2005. ISBN 5-8459-0857-4, ISBN 0-07-013151-1

Цикл (программирование)
[править]
Материал из Википедии — свободной энциклопедии
У этого термина существуют и другие значения, см. цикл.

Цикл — последовательность из нескольких (0 и больше) операторов, которая указывается в тексте программы один раз, но может выполняться несколько (0 и более) раз подряд, от первого до последнего, после последнего снова выполняется первый.Содержание [показать]


[править]
Тело цикла

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

[править]
Виды циклов

[править]
Условные циклы

Условные циклы выполняются или перестают выполняться в зависимости от заданного условия, проверяемого при каждом проходе цикла. Проверка может происходить перед выполнением тела цикла, после него или внутри тела цикла.

[править]
Цикл с предусловием

Цикл с предусловием — цикл, который выполняется, пока истинно некоторое условие, указанное перед его началом. Это условие проверяется до выполнения тела цикла, поэтому тело может быть не выполнено ни разу (если условие с самого начала ложно). В большинстве процедурных языков программирования реализуется оператором while, отсюда его второе название — while-цикл.

[править]
Цикл с постусловием

Цикл с постусловием — цикл, в котором условие проверяется после выполнения тела цикла. Отсюда следует, что тело всегда выполняется хотя бы один раз. В языке Паскаль этот цикл реализует оператор repeat..until; в Си — do…while.

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

[править]
Цикл с выходом из середины

Цикл с выходом из середины — наиболее общая форма условного цикла. Синтаксически такой цикл оформляется с помощью трёх конструкций: начала цикла, конца цикла и команды выхода из цикла. Конструкция начала маркирует точку программы, в которой начинается тело цикла, конструкция конца — точку, где тело заканчивается. Внутри тела должна присутствовать команда выхода из цикла, при выполнении которой цикл заканчивается и управление передаётся на оператор, следующий за конструкцией конца цикла. Естественно, чтобы цикл выполнился более одного раза, команда выхода должна вызываться не безусловно, а только при выполнении условия выхода из цикла.

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

Легко видеть, что с помощью цикла с выходом из середины можно легко смоделировать и цикл с предусловием (разместив команду выхода в начале тела цикла), и цикл с постусловием (разместив команду выхода в конце тела цикла).

Часть языков программирования содержат специальные конструкции для организации цикла с выходом из середины. Так, в языке Ада для этого используется конструкция LOOP…END LOOP и команда выхода EXIT или EXIT WHEN. В тех языках, где подобных конструкций не предусмотрено, цикл с выходом из середины может быть смоделирован с помощью любого условного цикла и оператора досрочного выхода из цикла (такого, как break в Си), либо оператора безусловного перехода goto.

[править]
Цикл c счётчиком

Цикл с счётчиком — цикл, в котором некоторая переменная изменяет своё значение от заданного начального значения до конечного значения с некоторым шагом, и для каждого значения этой переменной тело цикла выполняется один раз. В большинстве процедурных языков программирования реализуется оператором for, в котором указывается счётчик (так называемая «переменная цикла»), требуемое количество проходов (или граничное значение счётчика) и, возможно, шаг, с которым изменяется счётчик.

Неоднозначен вопрос о значении переменной по завершении цикла, в котором эта переменная использовалась как счётчик. Например, если в программе на языке Паскаль встретится конструкция вида:
i := 100;
for i := 0 to 9 do begin
   ... тело цикла
end;
k := i;

возникает вопрос: какое значение будет в итоге присвоено переменной k: 9, 10, 100, может быть, какое-то другое? А если цикл завершится досрочно? Ответы зависят от того, увеличивается ли значение счётчика после последней итерации и не изменяет ли транслятор это значение дополнительно. Ещё один вопрос: что будет, если внутри цикла счётчику будет явно присвоено новое значение? Различные языки программирования решают данные вопросы по-разному. В некоторых поведение счётчика чётко регламентировано. В других, например, в том же Паскале, стандарт языка не определяет ни конечного значения счётчика, ни последствий его явного изменения в цикле, но не рекомендует изменять счётчик явно и использовать его по завершении цикла без повторной инициализации. Радикально решён вопрос в языке Ада: счётчик считается описанным в заголовке цикла, и вне его просто не существует. Даже если имя счётчика в программе уже используется, внутри цикла в качестве счётчика используется отдельная переменная. Счётчику запрещено явно присваивать какие бы то ни было значения, он может меняться только внутренним механизмом оператора цикла. В результате конструкция
i := 100;
for i in (0..9) loop
   ... тело цикла
end loop;
k := i;

внешне аналогичная вышеприведённому циклу на Паскале, трактуется однозначно: переменной k будет присвоено значение 100, поскольку переменная i, используемая вне данного цикла, не имеет никакого отношения к счётчику i, который создаётся и изменяется внутри цикла. Считается, что подобное обособление счётчика наиболее удобно и безопасно: не требуется отдельное описание для него и минимальна вероятность случайных ошибок, связанных со случайным разрушением внешних по отношению к циклу переменных.

Цикл со счётчиком всегда можно записать как условный цикл, перед началом которого счётчику присваивается начальное значение, а условием выхода является достижение счётчиком конечного значения; к телу цикла при этом добавляется оператор изменения счётчика на заданный шаг. Однако специальные операторы цикла со счётчиком могут эффективнее транслироваться, так как формализованный вид такого цикла позволяет использовать специальные процессорные команды организации циклов.

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

[править]
Цикл по коллекции

Некоторые языки (C#, Java, JavaScript, Perl, Python, PHP, LISP, Tcl и др.) позволяют выполнять циклы по всем элементам заданной коллекции объектов. Для определения такого цикла не нужно ни указывать какой-либо счётчик, ни задавать условия выхода из цикла. Достаточно задать коллекцию и переменную, которой будут по очереди присваиваться значения всех объектов, находящихся в коллекции, или ссылки на них. Такие циклы реализуются операторами foreach, for…in и т. п.

не проще, было бы мыло, сам бы скачал... :P

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

Императивные языки программирования противопоставляются функциональным и логическим языкам программирования. Функциональные языки, например, Haskell, не представляют собой последовательность инструкций и не имеют глобального состояния. Логические языки программирования, такие как Prolog, обычно определяют что надо вычислить, а не как это надо делать.

Индексный массив (в некоторых ЯП также таблица, ряд) — простая статическая структура данных, предназначенная для хранения набора единиц данных, каждая из которых идентифицируется индексом или набором индексов.

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

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

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

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


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

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


[править] Достоинства
легкость вычисления адреса элемента по его индексу (поскольку элементы массива располагаются один за другим)
одинаковое время доступа ко всем элементам
малый размер элементов: они состоят только из информационного поля

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

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

Поддержка ассоциативных массивов есть во многих интерпретируемых языках программирования высокого уровня (Perl, PHP, Python, Ruby и др.). В языке C++ поддержка ассоциативных массивов включена в стандартную библиотеку (контейнер map).

[править] Достоинства
Наглядность, удобство для человека, возможность присвоить каждому элементу осмысленный идентификатор
Лёгкость добавления или удаления элементов, так как в общем случае не требуется изменения позиций других

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

[править] Примеры

[править] Python
Встроенный в Питон тип ассоциативного массива называется словарём (англ. dictionary), элементами (англ. items) которого являются пары ключей (англ. keys) и соотв. им значений (англ. values).

d1 = dict(a=10, b=20)
  d2 = {'a':10, 'b':20}
  d1[100] = 123
  d2['c'] = 321
  d1[100] = 1023
Здесь были показаны два способа написания литерала словаря и продемонстрировано, что ключом может быть объект любого типа. Добавление нового объекта в словарь не требует предварительных проверок: если ранее ключу уже соответствовало некоторое значение, оно будет перезаписано (Подробнее см. Python Tutorial, Dictionaries(англ.)). Другие операции со словарем:

if d1.has_key('a'):    # проверка наличия ключа
      del d1['a']        # удаление ключа (и значения)
  val = d1.get('a', 'default value')   # получение значения по ключу или значения
                                       # по умолчанию в случае отсутствия ключа
  val = d1.setdefault('a', 'default value')   # получение значения по ключу или значения
                                       # по умолчанию в случае отсутствия ключа (при этом
                                       # значение записывается в словарь)
  d1.keys()                            # список ключей
  d1.values()                          # список значений
  d1.items()                           # список пар ключ-значение
На Python весьма просто можно написать свой класс, который будет вести себя подобно словарю. Для этого необходимо лишь определить в своем классе соответствующие методы (см. Python Reference Manual, Emulating container types(англ.)). Для расширения базовых свойств типа словарь, необходимо наследовать свой класс от соответствующего типа словаря (dict).


[править] Perl
%arr = ( key1 => 'Значение (строка), доступное по ключу key1',
          text => 'Hello, world!'
        );

print $arr{text}; # будет напечатана строка 'Hello, world!'
Хэш может быть "связан" (tie) с внешним источником данных, например с файлом или же с таблицей базы данных.

Исправлено GingerNadya (26.06.07 14:21)

Метод ветвей и границ
Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Метод ветвей и границ — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является комбинаторным (алгоритм перебора) с отсевом подмножеств множества допустимых решений, не содержащих оптимальных решений. Метод был впервые предложен Ленд и Дойг в 1960 г. для решения задач линейного программирования.


[править] Общее описание
Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

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

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

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

Парадигма программирования
Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

Побочный эффект (программирование)
Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Побо́чный эффе́кт функции — возможность в процессе выполнения своих вычислений чтения и модификации значений глобальных переменных, осуществления операций ввода/вывода, реагирования на исключительные ситуации, вызова их обработчиков. Поэтому, если вызвать такую функцию дважды с одним и тем же набором значений входных аргументов, может случиться так, что в качестве результата вычисляются разные значения. Такие функции называются недетерминированными функциями с побочными эффектами.

Си (язык программирования)
Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Си 
Семантика: процедурный
Тип исполнения: компилируемый
Появился в: 1969 — 1973 г.
Автор(ы): Кен Томпсон, Денис Ритчи
Типизация данных: статическая
Основные реализации: GCC, Microsoft Visual C++, Borland C++ Builder, Watcom
Диалекты: «K&R» C (1978)
ANSI C (1989)
C99 (1999)
Создан под влиянием: не известно
Оказал влияние на: нет или не известно
Си (англ. C) — стандартизованный процедурный язык программирования, разработанный в начале 1970-х годов сотрудниками Bell Labs Кеном Томпсоном и Денисом Ритчи как развитие языка Би. Си был создан для использования в операционной системе UNIX. С тех пор он был портирован на многие другие операционные системы и стал одним из самых используемых языков программирования. Си ценят за его эффективность; он является самым популярным языком для создания системного программного обеспечения. Его также часто используют для создания прикладных программ. Несмотря на то, что Си не разрабатывался для новичков, он активно используется для обучения программированию. В дальнейшем синтаксис языка Си стал основой для многих других языков (см. C-подобный синтаксис).

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

Содержание [убрать]
1 Особенности
1.1 Обзор
1.2 Программа «Hello, World!»
1.3 Комментарии
1.4 Типы
1.5 Хранение данных
1.6 Набор используемых символов
2 Проблемы
3 История
3.1 Ранние разработки
3.2 K&R C
3.3 ANSI C и ISO C
3.4 C99
4 Связь с С++
5 Приоритет операций в Си
6 Внешние ссылки
7 См. также



[править] Особенности

[править] Обзор
Язык программирования Си отличается минимализмом. Авторы языка хотели, чтобы программы на нем легко компилировались с помощью однопроходного компилятора, после компиляции каждой элементарной составляющей программы соответствовало весьма небольшое число машинных команд, а использование базовых элементов языка не задействовало библиотеку времени выполнения. Однопроходный компилятор компилирует программу, не возвращаясь назад, к уже откомпилированному тексту. Поэтому использованию функции должно предшествовать её объявление. Код на Си можно легко писать на низком уровне абстракции, почти как на ассемблере. Иногда Си называют «универсальным ассемблером» или «ассемблером высокого уровня», что отражает различие языков ассемблера для разных платформ и единство стандарта Си, код которого может быть скомпилирован без изменений практически на любой модели компьютера. Си часто называют языком среднего уровня или даже низкого уровня, учитывая то, как близко он работает к реальным устройствам.

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

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

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

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

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

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


[править] Программа «Hello, World!»
Эта простая программа, появившаяся в первом издании книги «Язык программирования Си» Кернигана и Ритчи, обычно является первой программой большинства учебников Си. Она печатает сообщение «Hello World!» на стандартном устройстве вывода (которым, как правило, является монитор (дисплей), но может быть и файл, какое-либо устройство или область в памяти, в зависимости от того, как отражается стандартное устройство вывода на данной платформе).

main() {  printf("Hello, World!\n");  }
Несмотря на то, что на большинстве современных компиляторов эта программа может быть корректно скомпилирована, она порождает несколько предупреждений на компиляторах стандарта ANSI C. Кроме того, этот код не будет компилироваться, если компилятор жёстко следует стандарту C99, так как в этом случае по умолчанию больше не принимается тип int в качестве возвращаемого значения. Эти сообщения можно убрать, если внести в эту программу несколько небольших изменений:

#include <stdio.h>
int main(void)
{
    printf("Hello, World!\n");
    return 0;
}
В первой строке программы расположена директива препроцессора #include, встретив которую, компилятор заменяет её на полный текст файла, на который она ссылается. В данном случае эта строка будет заменена стандартным заголовочным файлом stdio.h. Угловые скобки указывают компилятору искать файл stdio.h в каталоге стандартных заголовочных файлов.

Следующая строка является объявлением функции с именем main. Эта функция в программе Си является особенной, так как выполняется первой при запуске программы, то есть служит так называемой точкой входа в программу. Фигурные скобки после функции main обозначают её определение. Слово int говорит, что функция main возвращает (вычисляет) целое число. Слово void показывает, что функция main не требует от вызывающего ни параметров, ни аргументов.

Следующая строка «вызывает» или исполняет функцию printf. Включаемый заголовочный файл stdio.h содержит информацию, описывающую то, как нужно вызывать эту функцию. В данном примере этой функции передаётся единственный аргумент, содержащий текстовую строку «Hello, World!\n». Последовательность \n транслируется в символ «новая строка», который при отображении соответственно обозначает разрыв строки. Функция printf вообще возвращает значение типа int, которое в этом примере полностью отбрасывается.

Выражение return заставляет программу прекратить выполнение данной функции (main в этом случае), возвращая вызвавшей функции значение, указанное после ключевого слова return (0 в этом случае). Так как текущая функция — это main, то вызывающим является то, что запустило программу. Последняя фигурная скобка обозначает конец определения функции main.


[править] Комментарии
Текст, заключённый в служебные символы /* и */ в этом порядке, полностью игнорируется компилятором. Компиляторы, совместимые со стандартом C99, также позволяют использовать комментарии, начинающиеся с символов // и заканчивающиеся переводом строки


[править] Типы
Си имеет ту же систему типов, что и другие потомки Алгола, такие как Паскаль. Существуют типы для целых чисел различных размеров, имеющих знак и не имеющих его, чисел с плавающей запятой, символов, перечисляемых типов (enum) и записей (struct). Кроме того, язык Си имеет тип объединения (union), позволяющий программисту создавать структуры, способные хранить данные разных типов, но только одного типа единовременно.


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

В Си есть три разных способа выделения памяти для объектов:

Статическое выделение памяти: пространство для объектов создаётся в области хранения данных кода программы в момент компиляции; время жизни таких объектов совпадает со временем жизни этого кода.
Автоматическое выделение памяти: объекты можно временно хранить в стеке; эта память затем автоматически освобождается и может быть использована снова, после того, как программа выходит из блока, использующего её.
Динамическое выделение памяти: блоки памяти нужного размера могут запрашиваться во время выполнения программы с помощью библиотечных функций malloc, realloc и free из области памяти, называемой кучей. Эти блоки освобождаются и могут быть использованы снова после вызова для них функции free.
Все три этих способа хранения данных пригодны в различных ситуациях и имеют свои преимущества и недостатки. Например, статическое выделение памяти не имеет накладных расходов по выделению, автоматическое выделение — лишь малые расходы при выделении, а вот динамическое выделение потенциально требует больших расходов и на выделение, и на освобождение памяти. С другой стороны, память стека гораздо больше ограничена, чем статическая, или память в куче. Только динамическая память может использоваться в случаях, когда размер используемых объектов заранее неизвестен. Большинство программ на Си интенсивно используют все три этих способа.

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


[править] Набор используемых символов
Язык Си был создан уже после внедрения стандарта ASCII, поэтому использует почти все его графические символы (нет только $ @ `). Более старые языки вынуждены были обходиться более скромным набором — так, Фортран, Лисп и Кобол использовали только круглые скобки ( ), а в Си есть и круглые ( ), и квадратные [ ], и фигурные { }. Кроме того, в Си различаются заглавные и строчные буквы, а более старые языки использовали только заглавные.


[править] Проблемы
Многие элементы Си потенциально опасны, а последствия неправильного использования этих элементов зачастую непредсказуемы. Керниган говорит: «Си — инструмент, острый, как бритва: с его помощью можно создать и элегантную программу, и кровавое месиво». В связи со сравнительно низким уровнем языка многие случаи неправильного использования опасных элементов не обнаруживаются и не могут быть обнаружены ни при компиляции, ни во время исполнения. Они часто приводит к непредсказуемому поведению программы. Иногда в результате неграмотного использования элементов языка появляются уязвимости в системе безопасности. Необходимо заметить, что использования многих таких элементов можно избежать.

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

Другим потенциальным источником опасных ситуаций служит механизм указателей. Указатель может указывать на абсолютно любой объект в памяти, включая даже и сам машинный код программы, что может приводить к непредсказуемым эффектам. Несмотря на то, что большинство указателей, как правило, указывают на безопасные места, они легко могут быть передвинуты в уже небезопасные области памяти с помощью арифметики указателей; память, на которую они указывают, может быть освобождена и использована по-другому («висячие указатели»); они могут быть не инициализированы («дикие указатели»); или же они просто могут получить любое значение путём приведения типов или присваивания значения другого повреждённого указателя. Другие языки пытаются решить эти проблемы путём использования более ограниченных типов — ссылок.

Одна из таких проблем — то, что автоматически и динамически создаваемые объекты не инициализируются, поэтому в начале они имеют такое значение, какое осталось в памяти, выделенной для них, от ранее удалённых объектов. Такое значение полностью непредсказуемо, оно меняется от одной машины к другой, от запуска к запуску, от вызова функции к вызову. Если программа попытается использовать такое неинициализированное значение, то придёт к непредсказуемому результату. Большинство современных компиляторов пытаются обнаружить эту проблему в некоторых случаях.

Ещё одной распространённой проблемой является то, что память кучи не может быть использована снова, пока она не будет освобождена программистом с помощью функции free(). В результате программист может случайно забыть освобождать эту память, но продолжать её выделять, занимая всё большее и большее пространство. Это обозначается термином утечка памяти. Наоборот, возможно освободить память слишком рано, но продолжать её использовать. Из-за того, что система выделения может использовать освобождённую память по-другому, это ведёт к непредсказуемым последствиям. Эти проблемы решаются в языках со сборкой мусора. С другой стороны, если память выделяется в функции и должна освобождаться после выхода из функции, данная проблема решается с помощью автоматического вызова деструкторов в языке C++, или с помощью локальных массивов, используя расширения С99.

Функции с переменным количеством аргументов также являются потенциальным источником проблем. В отличие от обычных функций, имеющих прототип, стандартом не регламентируется проверка функций с переменным числом аргументов. Если передаётся неправильный тип данных, то возникает непредсказуемый, если не фатальный результат. Например, семейство функций printf стандартной библиотеки языка Си, используемое для генерации форматированного текста для вывода, хорошо известно за его потенциально опасный интерфейс с переменным числом аргументов, которые описываются строкой формата. Проверка типов в функциях с переменным числом аргументов является задачей каждой конкретной реализации такой функции, однако многие современные компиляторы в частности проверяют типы в каждом вызове printf, генерируя предупреждения в случаях, когда список аргументов не соответствует строке формата. Следует заметить, что невозможно статически проконтролировать даже все вызовы функции printf, поскольку строка формата может создаваться в программе динамически, поэтому как правило никаких проверок других функций с переменным числом аргументов компилятором не производится.

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


[править] История

[править] Ранние разработки
Язык программирования Си был разработан в лабораториях Bell Labs в период с 1969 по 1973 год. Согласно Ритчи, самый активный период творчества пришёлся на 1972 год. Язык назвали «Си» (C — третья буква латинского алфавита), потому что многие его особенности берут начало от старого языка «Би» (B — вторая буква латинского алфавита). Существует несколько различных версий происхождения названия языка Би. Кен Томпсон указывает на язык программирования BCPL, однако существует ещё и язык Bon, также созданный им, и названный так в честь его жены Бонни.

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

Разработка Си стала результатом того, что его будущие авторы любили компьютерную игру, подобную популярной игре Asteroids (Астероиды). Они уже давно играли в неё на главном сервере компании, который был недостаточно мощным и должен был обслуживать около ста пользователей. Томпсон и Ритчи посчитали, что им не хватает контроля над космическим кораблём для того, чтобы избегать столкновений с некоторыми камнями. Поэтому они решили перенести игру на свободный PDP-7, стоящий в офисе. Однако этот компьютер не имел операционной системы, что заставило их её написать. В конце концов, они решили перенести эту операционную систему ещё и на офисный PDP-11, что было очень тяжело, потому что её код был целиком написан на ассемблере. Было вынесено предложение использовать какой-нибудь высокоуровневый портативный язык, чтобы можно было легко переносить ОС с одного компьютера на другой. Язык Би, который они хотели сначала задействовать для этого, оказался лишён функциональности, способной использовать новые возможности PDP-11. Поэтому они и остановились на разработке языка Си.
Самый первый компьютер, для которого была первоначально написана UNIX, предназначался для создания системы автоматического заполнения документов. Первая версия UNIX была написана на ассемблере. Позднее для того, чтобы переписать эту операционную систему, был разработан язык Си.
К 1973 язык Си стал достаточно силён, и большая часть ядра UNIX, первоначально написанная на ассемблере PDP-11/20, была переписана на Си. Это было одно из самых первых ядер операционных систем, написанное на языке, отличном от ассемблера; более ранними были лишь системы Multics (написана на ПЛ/1) и TRIPOS (написана на BCPL).


[править] K&R C

«Язык программирования Си» — книга Кернигана и Ритчи, долгое время служившая неформальным стандартом языка СиВ 1978 году Ритчи и Керниган опубликовали первую редакцию книги «Язык программирования Си». Эта книга, известная среди программистов как «K&R», служила многие годы неформальной спецификацией языка. Версию языка Си, описанную в ней, часто называют «K&R C». (Вторая редакция этой книги посвящена более позднему стандарту ANSI C, описанному ниже.)

K&R ввёл следующие особенности языка:

записи (тип данных struct);
длинное целое (тип данных long int);
целое без знака (тип данных unsigned int);
оператор += и подобные ему (старые операторы =+ вводили анализатор лексики компилятора Си в заблуждение, например, при сравнении выражений i =+ 10 и i = +10).
K&R C часто считают самой главной частью языка, которую должен поддерживать компилятор Си. Многие годы даже после выхода ANSI C, он считался минимальным уровнем, которого следовало придерживаться программистам, желающим добиться от своих программ максимальной портативности, потому что не все компиляторы тогда поддерживали ANSI C, а хороший код на K&R C был верен и для ANSI C.

После публикации K&R C в язык было добавлено несколько «неофициальных» возможностей, поддерживаемый компиляторами AT&T и некоторых других производителей:

функции, не возвращающие значение (с типом void) и указатели, не имеющие типа (с типом void *);
функции, возвращающие объединения и записи;
имена полей данных записей в разных пространствах имён для каждой записи;
присваивания записей;
спецификатор констант (const);
стандартная библиотека, реализующая большую часть функций, введённых различными производителями;
перечислимый тип;
дробное число единичной точности (float).

[править] ANSI C и ISO C
В конце 1970-х годов Си начал вытеснять Бейсик с позиции ведущего языка для программирования микрокомпьютеров. В 1980-х годах он был адаптирован для использования в IBM PC, что привело к резкому росту его популярности. В то же время Бьярне Строуструп и другие в лабораториях Bell Labs начали работу по добавлению в Си возможностей объектно-ориентированного программирования. Язык, который они в итоге сделали, C++, в настоящее время является самым распространённым языком программирования для платформы Microsoft Windows. Си остаётся более популярным в UNIX-подобных системах.

В 1983 году Американский Национальный Институт Стандартизации (ANSI) сформировал комитет для разработки стандартной спецификации Си. По окончании этого долгого и сложного процесса в 1989 году он был наконец утверждён как «Язык программирования Си» ANSI X3.159-1989. Эту версию языка принято называть ANSI C. В 1990 году стандарт ANSI C был принят с небольшими изменениями Международной Организацией по Стандартизации (ISO) как ISO/IEC 9899:1990.

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

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

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

[править] C99
После стандартизации в ANSI спецификация языка Си оставалась относительно неизменной в течение долгого времени, в то время как C++ продолжал развиваться (в 1995 году в стандарт Си была внесена Первая Нормативная Поправка, но её почти никто не признавал). Однако в конце 1990-х годов стандарт подвергся пересмотру, что привело к публикации ISO 9899:1999 в 1999 году. Этот стандарт обычно называют «С99». В марте 2000 года он был принят и адаптирован ANSI.

Вот некоторые новые особенности С99:

подставляемые функции (inline);
отсутствие ограничений на объявление локальных переменных (как и в С++);
новые типы данных, такие как long long int (для облегчения перехода от 32-х битных к 64-х битным числам), явный булевый тип данных и тип complex для представления комплексных чисел;
массивы переменной размерности;
поддержка ограниченных указателей (restrict);
именованная инициализация структур: struct { int x, y, z; } point = { .y=10, .z=20, .x=30 };
поддержка однострочных комментариев, начинающихся на //, заимствованных из С++ (многие компиляторы Си поддерживали их и ранее в качестве дополнения);
несколько новых библиотечных функций, таких как snprintf;
несколько новых заголовочных файлов, таких как stdint.h.
Интерес к поддержке новых особенностей С99 в настоящее время смешан. В то время как GCC и некоторые другие компиляторы в настоящее время поддерживают большую часть новых особенностей С99, компиляторы компаний Borland и Microsoft не делают этого, причём похоже, что две эти компании и не думают их добавлять.


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

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

Вот различия между этими языками, существующие на сегодня:

inline — подставляемые функции существуют в глобальном пространстве С++, а в Си — в пространстве файла (статическом пространстве). Другими словами, это значит, что в С++ любое определение подставляемой функции (независимо от переопределения функций) должно соответствовать правилу одного определения, требующего того, чтобы любая подставляемая функция была определена только один раз. В Си же одна и та же подставляемая функция может быть определена по-разному в разных компилируемых файлах одной программы.
В отличие от С++, ключевое слово bool в С99 требует включения соответствующего заголовочного файла stdbool.h. Предыдущие стандарты Си не определяли булевый тип вообще, поэтому для этого часто использовались различные (а значит, несовместимые) методы.
Символьные константы (заключённые в одинарные кавычки) имеют тип int в Си и тип char в С++. Поэтому в Си справедливо равенство sizeof('a') == sizeof(int), а в С++ — равенство sizeof('a') == sizeof(char).
Некоторые новые возможности C99, в первую очередь, restrict, не включены в стандарт C++.
Си перенял от С++ ряд особенностей:

прототипы объявления функций;
однострочные комментарии, начинающиеся на // и заканчивающиеся символом перевода строки;
ключевое слово inline;
более сильную проверку типов, включая добавление типа void, спецификатора const и удаление принятия по умолчанию типа int в качестве возвращаемого значения.

[править] Приоритет операций в Си
Ниже приведены операции в порядке убывания приоритета. Операции, приведённые на одной строчке, имеют одинаковый приоритет. Операции, помеченные как R->L, исполняются справа налево.

() [] -> .
Унарные (R->L): !  ~  - * & sizeof (type) ++ --
Бинарные арифметические: * / %
Бинарные арифметические + -
Сдвиг: << >>
Сравнение: < <= > >=
Сравнение: == !=
Битовая: &
Битовая: ^
Битовая: |
Логическая: &&
Логическая: ||
Тернарная (R->L): ?:
Операции с присваиванием (R->L): = += -= *= /= &= |= ^= <<= >>=

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

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

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

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

Содержание [убрать]
1 Основы
2 Контроль типов
3 Классификация типов данных
4 См. также



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

Преимущества от использования типов данных:

Надёжность. Типы данных защищают от трёх видов ошибок:
Некорректное присваивание. Пусть переменная объявлена как имеющая числовой тип. Тогда попытка присвоить ей символьное или какое-либо другое значение приведет к ошибке еще на этапе компиляции и позволит избежать многих трудностей, поскольку такого рода ошибки трудно отследить обычными средствами. Предварительное объявление используемых переменных сейчас обязательно практически во всех языках.
Некорректная операция. Позволяет избежать попыток применения выражений вида «Hello world» + 1. Поскольку как уже говорилось все переменные в памяти хранятся как наборы битов, то при отсутствии типов подобная операция была выполнима (и могла дать результат вроде «Hello worle»!). С использованием типов (см. далее «Контроль типов») такие ошибки отсекаются опять же на этапе компиляции.
Некорректная передача параметров. Если функция «синус» ожидает, что ей будет передан числовой аргумент, то передача ей в качестве параметра строки «Hello world» может иметь непредсказуемые последствия. При помощи контроля типов такие ошибки также отсекаются на этапе компиляции.

[править] Контроль типов
Процесс проверки и накладывания ограничений типов — контроля типов, может выполняться во время компилирования (статическая проверка) или во время выполнения (динамическая проверка). Статический контроль типов является основной задачей семантического анализа, выполняемого компилятором. Контроль типов может быть сильным и слабым.


[править] Классификация типов данных
Согласно стандартной классификации, типы данных бывают следующие:

Простые.
Числовые. Хранятся числа. Могут применяться обычные арифметические операции.
Целочисленные: со знаком, то есть могут принимать как положительные, так и отрицательные значения; и без знака, то есть могут принимать только неотрицательные значения.
Вещественные: с фиксированной точкой, то есть хранятся знак и цифры целой и дробной частей и с плавающей точкой, то есть число приводится к виду m*2e, где m — мантисса, e — экспонента причем 1/2<=m<=1, а e — целое число и хранятся знак, и числа m и e.
Символьный тип. Хранит один символ. Могут использоваться различные кодировки.
Строковый тип. Хранит строку символов. Может применяться операция конкатенация (сложение строк). Вообще говоря, может рассматриваться как массив символов, но как правило выделяется в качестве простого.
Логический тип. Имеет два значения: истина(true) и ложь(false). Могут применяться логические операции. Используется в операторах ветвления и циклах. В некоторых языках является подтипом числового типа, при этом ложь=0, истина=1.
Перечислимый тип. Может хранить только те значения, которые прямо указаны в его описании.
Множество (тип данных). В основном совпадает с обычным математическим понятием множества. Допустимы стандартные операции с множествами и проверка на принадлежность элемента множеству. В некоторых языках рассматривается как составной тип.
Составные. Формируются на основе комбинаций простых типов.
Массив. Является индексированным набором элементов одного типа. Одномерный массив — вектор, двумерный массив — таблица.
Запись. Набор различных элементов (полей записи), хранимый как единое целое. Возможен доступ к отдельным полям записи.
Другие типы данных. Если описанные выше типы данных представляли какие-либо объекты реального мира, то рассматриваемые здесь типы данных представляют объекты компьютерного мира, то есть являются исключительно компьютерными терминами.
Указатель (тип данных). Хранит адрес в памяти компьютера, указывающий на какую-либо информацию, как правило — указатель на переменную.
Ссылки (тип данных).

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

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

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

Функциональное программирование основано на теориях λ-исчисления (Алонзо Чёрч, 1936) и комбинаторной логики (Моисей Исаевич Шейнфинкель и Хаскелл Карри).

Наиболее известными языками функционального программирования являются:

LISP (Джон МакКарти, 1958, множество его потомков, наиболее современные из которых — Scheme и Common Lisp)
ML (Робин Милнер, 1979, из ныне используемых диалектов известны Standard ML и Objective CAML)
Miranda (Дэвид Тёрнер, 1985, который впоследствии дал развитие языку Haskell).
Nemerle — гибридный функционально/императивный язык.

Форма Бэкуса — Наура
Материал из Википедии — свободной энциклопедии
(Перенаправлено с Форма Бэкуса-Наура)

Форма Бэкуса — Наура (сокр. БНФ, Бэкуса — Наура форма) - формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ эквивалентно контекстно-свободным формальным грамматикам.

см. англ. Backus–Naur form

[править]
Применение

Используется для описания синтаксиса языков программирования, данных, протоколов (например, в документах RFC) и т.д. (причем как грамматики, так и регулярной лексики, поскольку регулярные грамматики являются подмножеством контекстно-свободных).

[править]
Описание

Терминология этой статьи может расходиться с традиционной.

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

БНФ-конструкция состоит из нескольких предложений вида
<определяемый символ> ::= посл.1 | посл.2 | . . . | посл.n

, описывающих правила. Такое правило, означает, что символ <определяемый символ> может заменятся на одну из последовательностей посл.i. Знак определения, обычно выглядит как ::=, но возможны и другие варианты.

Некоторые специальные символы, как например <пусто> означают какую-то последовательность (в данном случае — пустую).

[править]
Примеры конструкций
Вот пример БНФ-конструкции, описывающей правильные скобочные последовательности:
<правпосл>::=<пусто> | (<правпосл>) | <правпосл><правпосл>

Это простая конструкция, состоящая всего из одного правила, утверждающего, что символ <правпосл> может замениться либо на пустое место, либо на этот же символ <правпосл>, заключённый в скобки, либо на два символа <правпосл> идущих подряд.

Вот, как получить с помощью этой конструкции цепочку ((())())() (ниже перечисляются все этапы, символы <пусто> опускаются):
<правпосл>
<правпосл><правпосл>
(<правпосл>)<правпосл>
(<правпосл>)(<правпосл>)
(<правпосл>)(<пусто>)
(<правпосл><правпосл>)()
((<правпосл>)<правпосл>)()
((<правпосл>)(<правпосл>))()
((<правпосл>)(<пусто>))()
(((<правпосл>))())()
(((<пусто>))())()
((())())()


Вот пример, взятый из книги Дональда Кнута Всё про TEX (TEXbook):
<simple assignment> ::= <variable assignment> | <arithmetic>
|  | <let assignment> | <shorthand definition>
| <fontdef token> | <family assignment> | <shape assignment>
| \readhnumber> to <optional spaces><control sequence>
| \setboxh8-bit number><equals><filler><box>
| \fonthcontrol sequence><equals><file name><at clause>
| <global assignment>
<variable assignment> ::= <integer variable><equals><number>
| <dimen variable><equals><dimen>
| <glue variable><equals><glue>
| <muglue variable><equals><muglue>
| <token variable><equals><general text>
| <token variable><equals><filler><token variable>
<arithmetic> ::= \advancehinteger variable><optional by><number>
| \advancehdimen variable><optional by><dimen>
| \advancehglue variable><optional by><glue>
| \advancehmuglue variable><optional by><muglue>
| \multiplyhnumeric variable><optional by><number>
| \dividehnumeric variable><optional by><number>
<optional by> ::= by | <optional spaces>
<integer variable> ::= <integer parameter> | <countdef token>
| \counth8-bit number>
<dimen variable> ::= <dimen parameter> | <dimendef token>
| \dimenh8-bit number>
<glue variable> ::= <glue parameter> | <skipdef token>
| \skiph8-bit number>
<muglue variable> ::= <muglue parameter> | <muskipdef token>
| \muskiph8-bit number>
<token variable> ::= <token parameter> | <toksdef token>
| \toksh8-bit number>
<numeric variable> ::= <integer variable> | <dimen variable>
| <glue variable> | <muglue variable>
::= <8-bit number><equals><number>
<let assignment> ::= \futurelethcontrol sequence><token><token>
| \lethcontrol sequence><equals><one optional space><token>
<shorthand definition> ::= \chardefhcontrol sequence><equals><8-bit number>
| \mathchardefhcontrol sequence><equals><15-bit number>
| <registerdef><control sequence><equals><8-bit number>
<registerdef> ::= \countdef | \dimendef | \skipdef | \muskipdef | \toksdef
<family assignment> ::= <family member><equals>
<shape assignment> ::= \parshapehequals><number><shape dimensions>

Этот пример не будет разбираться подробно в данной статье.

Спасибо всем огромное... ;)