http://video.yandex.ru/users/ya-events/vie...ents&cid=10

Хоть я и недолюбливаю STL, но лекции мегарулез! Очень интересно и познавательно. Обчмырил Александреску, за что ему отдельный респект :).

djamshud, спасибо за ссылку. 

Писать письмо Степанову, что он дурак не буду.  Не дурак. Но... Обратите внимание на парадоксальность скзанного.

Человек искренне рад, что в России всё ещё учать тому, что принято называть "алгоритмическое программирование". И в то же самое время отмечает, что арифметика указателей -  преимущество C над PASCAL, т.к. нужно быть ближе к машине. Чтобы почуствовать парадоксальность этих суждений не надо быть Дейкстрой.

"Computer Science is no more about computers than astronomy is about telescopes." Edsger Wybe Dijkstra
"Информатика имеет не большее отношение к компьютерам, чем астрономия — к телескопам." Эдсгер Вибе Дейкстра

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

Поэтому с точки зрения алгоритмического программирования, PASCAL как раз смотрится выгоднее.

Про goto... Странно как-то. Помните, у Булгакова в "Мастере и Маргарите", Га-Ноцри на допросе у Понтия Пилата:


Вот с Дейкстрой таже история. Почему Дейкстра был против использования goto можно понять, прочитав его труд "Заметки по структурному программированию" (в составе сборника Дал У., Дейкстра Э., Хоар Т. - Структурное программирование (1975)). Особенно внимательно читать раздел "7. О понимании программ". Думаю... Нет, я уверен, что большая часть согласится с Дейкстрой.

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

Но. Дейкстра, убрав безусловно опасную конструкцию goto, вообще говоря, предложил ввести новую конструкцию, с помощью которой всяческие конечные автоматы и программировать. Называется "Цикл Дейкстры". Не в курсе, знает ли о нём Степанов (но, судя по-всему, нет), но его описание есть даже в Wikipedia. При такой записи мы видим сразу все ветви в одном месте, видим условия, охранающие переходы (опять же в одном месте). Мы видим конечный автомат, мы, несмотря на наши ограниченные интеллектуальные способности, видим картинку целиком. А с goto - мало того, что не видим, так ещё и появляется соблазна использовать его вся и всюду. Естественно, использовать не по назначению.

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

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

Помните тот момент, когда Степанов сокрушается, что римляне выкинули все доказатедьства из математических трактатов греков? Ай-ай-ай, как нехорошо! Вот он, господа-товарищи, "чистый математик". Во всей красе. И он отчасти прав. Математические доказательства - вещь важная, многие из них великолепны, эдакие интеллектуальные бриллианты. Но интересны они могут быть только "чистым математикам". А нам, римлянам химикам/физикам/биологам/статистикам/социологам/экономистам/..., нужны только сами выводы. Нам нужны теоремы и их следствия. которыми мы можем пользоваться при решении загадок природы. Мы формализуем задачи, пользуемся абстрактным языком математики и используем доказанные теоремы, чтобы найти ответы. На этом математика для нас заканчивается. Математика для нас - средство, инструмент. Но не самоцель. И ценнности самого по себе, в чистом виде не имеет. "Чистая математика" нужна только "чистым математикам".

Поэтому на вопрос "Должен ли каждый программист знать математические основы информатики?" можно смело отвечать "Да, должен". Но должен знать только теоремы и следствия. Он лишь должен уметь: алгоритмически мыслить и реализовывать алгоритм для конкретного вычислителя (но имея ввиду абстракный!). Для этого достаточно знать теорем и следствий теории алгоритмов, а также теорем и следствий, сформулированных Дейкстрой и иже с ним для императивного программирования.

Должен ли каждый физик знать математические основы физики? Да. Но опять же, теорем и следствий более чем достаточно. Должен ли каждый, скажем, каждый квантовый физик, знать доказательство того, что волновая (лучше назвать операторная) механика Шрёдингера эквивалентна матричной механике Гайзенберга? Нет. Это когда-то показал Шрёдингер, а доказал... фон Нейман, вроде. Не нужно физику знание некоммутативной математики. Пространствами и проблемами их изоморфизма пущай математики и занимаются.

Что-то я хотель написать про функциональное программирование... Что-то плохое...  Но голод не тётка... Может потом вспомню.

P.S. Кнута тоже не читайте. Аргументация выше.

Это сообщение отредактировал(а) kemiisto - 20.9.2010, 09:13

kemiisto, все так, но чтобы появился алгоритм кто-то должен его разработать и написать для него библиотеку.
Тогда уже можно будет его использовать не думая о том как его делали и как он сделан.

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


Таки всомнил. Вот что. Существует несколько т.н. моделей исчислений. Каждая из этих моделей - формализация понятия алгоритма.

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

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

Функциональное программирование базируется на совершенно иной модели исчислений: λ-исчислении (не только на λ-исчислении, но для упрощения картины).

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

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

do_task
  do_subtask_1
  do_subtask_2
  ...
  do_subtask_n
end do_task

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

output = f[n](f[n-1](...(f[1](input))))

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

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

Всё.  

Это очень неправильно так думать.
Это говорит о том что вы мало что понимаете в математике и в информатике как науке.


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

И всё!? 3 строчки!? А как думать правильно? Потрудитесь изложить.


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


Я писал про структурный подход. Там свои правила игры. Императивный подход намного шире.

Или, что точнее, умеет рассуждать как математик. Это сильно меняет дело - всевозможным "прикладникам" не надо быть математиками, но вот понимать, как эта кухня работает, необходимо. В противном случае... "сон разума рождает чудовищ".   

P.S. Если что, не обвиняйте в математическом шовинизме - я как раз "прикладник".

kemiisto, Для начала, статисты это кто в фильмах снимаются.  А статистики занимаются статистикой. И она знают математику, лучшие статистики это математики.

А ваша статья показывает насколько вы далеки от математики, и от теории. Увы, незнание, не дает вам права, к таким громким высказваниям. 
Вы подобны медбрату кричащему, что он ставит уколы лучше врача. И сантехнику, утверждаещему что он в трубах разбирается лучше инженера

Исправил. Статистики знают определённую, нужную только им часть математики. Математику, лежащую в основе теоретической информатики им знать необязательно.


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


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

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

Конечно, нужны и специалисты в теории алгоритмов и т.п. Но речь шла не о них, а о рядовых сантехниках программистах.

Вот.

Это сообщение отредактировал(а) kemiisto - 20.9.2010, 09:26

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

kemiisto, за ссылку пожалуйста.

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

Алгоритм vs Машина или Указатель маст дай! В теории алгоритм конечно ни к чему не привязан. Это в общем смысле какая-то математическая абстракция. На практике алгоритмы реализуются для ЭВМ, то есть мысли из абстрактной формы нужно перевести в практическую, реализовать их для ЭВМ. Как физики адаптируют математику под физику, так и программисты - под машину, они используют математику в проекции на ЭВМ - не сферическую и в вакууме, а вполне себе осязаемую - и используют в этом термины ЭВМ. Таким образом Степано не противоречит себе, а просто говорит о программировании в двух плоскостях: создание алгоритма и его реализация. При создании никакие термины ЭВМ конечно же не используются.

Long live goto. Он не плох сам по себе. Вполне годная и удобная конструкция. Другое дело, что ее можно использовать таким образом, что код с ним стал непонятным - поэтому вполне правильно огораживать от нее новичков. Лично я использую goto как правило в двух случаях: агрегация ошибок с последующим освобождением ресурсов внутри одной функции и выход из вложенных циклов. Ха! "Use exceptions, Luke!" - скажите вы. В первом случае идея хороша, если весь код изначально проектируется таким образом; лично мне это не нравится - я предпочитаю максимально локализовать ошибки внутри процедур, т.к. моя практика показывает, что одинаковой обработки одних и тех же ошибок в разных частях программы не бывает. Или почти не бывает. Во втором случае исключение - это огромный синтаксический оверхед, который к тому же усложняет понимание кода.