Ответ на »сообщение 67« (Павел Трубаев)
___________________________
Ну зачем при одном? «Говорят, что алгоритм корректен (correct), если для каждого ввода результатом его работы является корректный вывод» - Кормен и др.  «Алгоритмы: построение и анализ». То есть о математическом доказательстве здесь ничего нет.
Если имеется хотя бы десяток входных величин (пусть целочисленных), проверить тестированием что ДЛЯ КАЖДОГО ввода результатом его работы является корректный вывод не представляется возможным.
Подобное ПОЛНОЕ тестирование я встречал только для автопилотов: тестируются ВСЕ возможные сочитания входных параметров. Но там всего пара входных и одно выходное значение.
Сколько было случаев, когда серьезный сбой происходил при редком сочетании параметров, не попавшемся при тестировании.

А математически доказать правильность не чисто математического алгоритма, а программы решающей реальную задачу,  я думаю, будет довольно сложно (да и нужно ли?).
Что сложно - кто бы спорил. Нужно ли, зависит от ответственности задачи.

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

Ответ на »сообщение 65« (panda)
___________________________


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

Безусловно, хотя это скорее относится к математике, а не к программированию.

А вот если программа при одном запуске на одном варианте входных данных выдала правильные выходные данные - это абсолютно ни о чем не говорит и ни в малейшей степени не доказывает правильность программы.

Ну зачем при одном? «Говорят, что алгоритм корректен (correct), если для каждого ввода результатом его работы является корректный вывод» - Кормен и др.  «Алгоритмы: построение и анализ». То есть о математическом доказательстве здесь ничего нет. А математически доказать правильность не чисто математического алгоритма, а программы решающей реальную задачу,  я думаю, будет довольно сложно (да и нужно ли?).

Кстати, в ISO/IEC 12207:1995 «Information Technologies - Software Life Cycle Processes» в качестве доказательства правильности работы программ упоминается только тестирование.

Если меня доказательно опровергнут, буду рад изменить свое мнение.

Ответ на »сообщение 66« (Сергей Перовский)
___________________________

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

Вы меня немного не так поняли. Можно сказать так: программы – не основной мой источник дохода. Но я единоличный автор двух относительно крупных проектов (каждый за 50 тыс. строчек), участвовал еще в одном проекте. Моими программами легально пользуются на 16 крупных отечественных заводах (причем «поезда ходят» довольно долго, первый рес был уже более 10 лет назад), и на стольких же, если не больше, нелегально. В настоящий момент я участвую в разработке системы автоматизации на одном из заводов, пишу свой отдельный блок теплотехнического анализа. И в планах еще очень крупный проект – есть много заказов, но нет времени… Единственно, что ТЗ я сам себе определяю, так как предлагаю то, в чем я разбираюсь по своей основной специальности, и что программисты не смогли сделать, несмотря на востребованность задач и неоднократную попытку их решить).

Ну а на корзину работать – жалко своего времени и труда (сейчас я приболел, сижу дома, вот и решил поучаствовать в дискуссии, очень тема интересная. А так обычно бегаешь и крутишься и ничего не успеваешь…). Конечно, есть маленькие программки "для себя и знакомых", точнее для облегчения свой работы. Например, лет семь назад написал маленький калькулятор, очень удобный. Он, и правда, рядом с корзиной (в панели быстрого запуска), но пока не в ней.

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

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

"Я вижу в своем воображении образцовый учебник в качестве подходящего исходного пункта. Он должен удовлетворять следующим критериям:
1. Начинаться сжатым введением в основные понятия программного проектирования.
2. Использовать лаконичную формальную нотацию, строго определенную не более чем на примерно 20 страницах.
3. Основываясь на этой нотации, вводятся основные понятия итерации, рекурсии, логического утверждения <assertion> и инварианта.
4. Центральная тема — структурирование утверждений и типизация данных.
5. За этим следуют концепции упрятывания информации, модульности и проектирование интерфейсов, продемонстрированные образцовыми примерами.
6. Книга устанавливает терминологию, которая столь же интуитивна, сколь и точна.
7. Книга имеет умеренный размер."

---

---

Ответ на »сообщение 63« (Павел Трубаев)
___________________________
Вообще, решение инженерных задач численными методами, наверное, как раз в основном и заключается в экспериментальном поиске нужного алгоритма и опять же экспериментальной доводке его до кондиции.
Ваше "скромное ИМХО" основано на том, что Вы сами являетесь потребителем собственных алгоритмов и програм. Получили удовлетворительный результат и в корзину.
А программист делает то, что нужно множеству других пользователей. Он должен быть уверен, что ВО ВСЕХ предусмотренных ТЗ случаях программа выдаст адекватный результат. И тут в ход идут формальные доказательства алгоритмов, оценка вычислительной сложности и прочие теоретические хитрости.

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

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

Ответ на »сообщение 63« (Павел Трубаев)
___________________________

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

Добавление к предыдущему сообщению:
Прошу прошения у уважаемого Ins за неправильное цитирование ника.

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

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

«Хотелось, чтобы программы можно было и выполнять» - Вирт.

«В программировании в конечном счете многое определяет человеческий фактор: это не просто возможность творить эфемерные абстракции, а реальное создание того, что можно «потрогать» своими руками и применить в качестве инструмента. Другими словами, программирование ближе всего к инженерной деятельности, конструированию, а потому ему сродни понятие изобретательства» - Руслан Богатырев, редактор раздела ПО «Мира ПК».

От себя добавлю, «что поступают в корне неверно» – это очень категоричная мысль. Обучение во многом определяется уровнем и  мастерством учителя или преподавателя. Поэтому если кто-то может хорошо научить программированию и информатике на бумаге – так и надо делать. Но проверка решения задач на компьютере, по моему, предпочтительней, так как: 1) там выявляются все ошибки, которые преподаватель может просмотреть; 2) проверка преподавателем определяет перерыв между написанием работы и ее исправлением (если занятия раз  в неделю, то к тому времени уже все забудется), а на компьютере процесс решения задачи происходит on-line до получения нужного результата; 3) при проверке преподаватель обычно говорит, в чем ошибка, а при самостоятельном запуске программы обучающийся должен додуматься до этого сам, что с точки зрения обучения получше.

Да и пожалейте преподавателя – какая это работа – проверить задачи у класса (группы).

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

Сообщение 62 от ИМГ
Как сказал Вирт - программирование, это алгоритмы + структуры данных. Он ничего не говорил о языках.

На примере Вирта очень удобно проследить изменение понятий. Первая его книга называлась «Алгоритмы + Структуры данных = Программы».  Второе переработанное издание этой книги – «Алгоритмы и структуры данных». Цитата из предисловия к переводу от 1989 г.: «Конечно, сразу же возникает проблема представления: хотелось, чтобы программы можно было и выполнять, и чтобы они были достаточно машинно-независимы, ведь их нужно включать в текст. Для этого не подходит ни общераспростаненные языки, ни абстрактная нотация. Нужный компромисс  обеспечивается языком паскаль … поэтому в книге мы и будем им пользоваться». Ну а в последних статьях Вирта (они есть на сайте «Информатика-21») он именно очень много говорит о языках в свете преподавания программирования. Кстати, на этом же сайте говорится, что курс программирования должен базироваться на каком-то языке и системе программирования.

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

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

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

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

А еще по мнению многих классиков и современников, хороший алгоритмы – это не всегда хорошая программа. Например «Многие программисты настолько слепо верят в алгоритмы, что даже не пытаются задуматься о том, как они работают» - Кнут. «По мнению Вирта, программы - это органичное соединение алгоритмов со структурами данных. С этим спорить трудно, однако алгоритмы и структуры данных - все же еще не программы. Это лишь строительные блоки, из которых можно соорудить нечто, хаотически их нагромождая, а можно возвести красивый, уютный и долговечный дом» - Р. Богатырев.

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

Программирование – это наука (Грайс), искусство (Кнут), процесс (Хамфри), академическая дисциплина (Вирт), промышленные методы работы (Ершов). Так что, сколько классиков, столько и мнений.
«Кодинг» - такого понятия в учебниках нет. Поэтому им можно назвать все что угодно. У меня сложилось мнение, что «кодеры» - это те, кто переводит в текст заданный алгоритм («негры» информационного труда). Если человек сам составляет алгоритм и реализует его, без записи на бумаге, сразу на языке программирования, это уже наверное, программист, а не кодер.

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

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

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

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

И не забывайте, что все вышеприведенное мое скромное ИМХО, которое вполне может быть неверным.

Ответ на »сообщение 60« (Павел Трубаев)
___________________________
Программирование - это не наука сама по себе, а реализация с помощью компьютера прикладных задач. Поэтому научиться программированию абстрактно, без привязки к конкретным задачам и системам, невозможно.

Как сказал Вирт - программирование, это алгоритмы + структуры данных. Он ничего не говорил о языках. Ну, а Макконнелл сказал, что программировать нужно не на языке, а с помощью языка. Из этого делаем вывод, что программирование - это именно абстрактная наука, а реализация с помощью компьютера - это не программирование, а кодинг.

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

Не факт! ;-)
Очень полезное занятие, надо сказать, программировать без компьютера. Когда программа ну никак не хочет работать и ты сидишь и всяческим образом пытаешься ее заставить заработать, лучшим решением ИМХО будет отойти от компьютера, взять листик и ручку, и набросать алгоритм на бумажке. Даже если и удасться методом проб и ошибок заставить программу заработать, не факт что она будет работать при других входных данных.
Считаю, что этап разработки и написания кода нужно разделять, чтобы когда структура программы и алгоритмы были готовы, осталось только переписать их на соответствующем ЯП. Намного эффективнее, чем придумывать архитектуру программы по ходу написания кода.

Ответ на »сообщение 60« (Павел Трубаев)
___________________________

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

С интересом прочитал обсуждение, оно очень перекликается с опросом "Глас народа - Опрос на тему "Лучшая и худшая книга по Delphi"» (что-то ссылку не могу поставить), инициатором которого я когда-то был. И, конечно, пальцы сразу потянулись к клавиатуре (к сожалению,  не слепым методом а двумя пальцами по очереди, тут я, безусловно, не истинный программист).

Научитесь сначала программированию на подходящем для этого языке. (oberon, ML, scheme, python, ruby).

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

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

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

Теперь о том, что лучше Дельфи, Турбо-Паскаль или др. системы. При разработке алгоритма необходимо, по крайней мере, вывести на экран результаты работы, или проследить логику действия программы. С выводом результатов, я думаю, никакая система преимущества не получит (строки "writeln(txt,n:0)" или Label1.Caption:=IntToStr(n) с точки зрения новичка одинаково трудны, а для немного разбирающегося одинаково просты). Поэтому с любым языком программирования  необходимо изучать способы ввода/вывода, отладки, и опять же, преимущество здесь имеют не искуственные, а практически применимые среды программирования.

Поэтому, с моей точки зрения, наиболее применимо для обучения программированию - это курс с конкретной средой (Turbo Pascal или Delphi) и решением прикладных задач, например, по численным методам, где можно изучить  циклы, условия, массивы и т.д. Прекрасная книга в этом отношении - Путянин Е. П., Смагин Д. М., Степанов В. П. Турбо Паскаль в курсе высшей математики. - Харьков: Каравелла, 1997. - 352 с.

Кстати идея насчет выпуска книги по материалам Королевства (сообщение №10) у кого-нибудь вызвала в душе отклик? 

А зачем? Прекрасный, но очень разнородный материал сайта в печатном виде очень сильно проиграет, т.к. в книжке кнопку "поиск" нажать нельзя. Вообще, мое мнение, что программирование, компьютер, мс офис и т.п. в теории и по книгам изучать нельзя, так как это чисто прикладные знания, требующиеся человеку в том объеме, который необходим для решения имеющейся у него задачи. Я всегда советую - не читайте книжки по компьютерам на ночь, как художественную литературу, и не думайте, что прочитав книгу, Вы чему-то научитесь. Толку от этого не будет, так как в информатике и программировании из огромного количества имеющейся информации человеку нужна только та, которая поможет ему в решении его задачи. Любая невостребованная в практической деятельности информация будет или не понята, или довольно быстро забыта. Поэтому лучший способ изучать компьютер - взять и решать на нем необходимую вам задачу, консультируясь при этом с коллегами, книгами, круглым столом и т.п. 

Я книги обычно использую в качестве источника информации по непонятной проблеме. Считаю, что, в принципе, любая книга в чем-то полезна. У меня сейчас около двух десятков электронных версий книг по Дельфи, столько же по базам данных, Экселю, статистике, численным методам, и другим нужным  мне направлениям. Если мне нужна информация, просматриваю все книги подряд, обычно что-то где-то нахожу. Хорошо, что сейчас можно найти в интернете любую современную книгу по информационным технологиям (конечно, это пиратские версии, но убыток издательствам я не наношу, так как при отсутствии электронных версий бумажные книги я покупать вряд ли стал, жалко денег на эту современную литературу). Кстати, очень смешно видеть, как Микрософт подсчитывает свои миллиардные убытки в России. Ведь если человек установил пиратскую Windows/Office, это не значит, что что он бы ее купил в альтернативном случае. Не было бы пиратских версий Windows/Office, народ бы пользовался Lunix+Open Office.

Из бумажных версий у меня на полке стоит Кэнту (это просто гений) и Архангельский (использую как переведенный на русский help, но книги этого автора очень поверхностные, с неудобной системой ссылок и предметных указателей). Еще, лучшая книга - это конечно, help, но не в delphi  2005/2006/2007. Я использую help для D7 (работаю в D2007Win32Up1).

Я думаю, что хороших книг отечественных авторов не будет в обозримом будущем.

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

Ответ на »сообщение 58« (Антон Григорьев)
___________________________
Это переведенная статья Питера Норвига, автора знаменитой книги PAIP http://norvig.com/paip.html, несколько раз рекомендовавшейся к прочтению на ветке ФП.