Курс «Алгоритмизация вычислений» будет вам интересен и просто необходим, если вы хотели бы изучить программирование с нуля и выйти на хороший базовый уровень, научиться составлять, понимать и анализировать алгоритмы. В результате изучения курса вы сможете: • записывать математическую постановку задачи; • применять стандартные алгоритмы для решения задач; • оценивать оптимальность алгоритмов и выбирать алгоритм, дающий лучшее решение задачи; • проверять правильность алгоритма методом трассировки; • кодировать алгоритмы с использованием технологии структурного программирования; • отлаживать и тестировать программы. Изучение данной дисциплины базируется на знании студентами основ математики, информатики и основ алгоритмизации в пределах программы средней школы, умении применять математический аппарат при выборе метода решения задачи. Для освоения учебной дисциплины, студенты должны владеть школьными знаниями, получаемыми в процессе изучения указанных выше курсов. Этот курс лежит в основе всего программирования. Можно сказать, что это фундамент, на котором будет строиться все дальнейшее обучение программированию. Мы будем решать задачи, постепенно переходя от простых к более сложным. В конечном итоге вы научитесь решать задачи обработки динамических списков, т.е. работать на хорошем базовом уровне.
Преимущества и недостатки различных подходов к составлению алгоритмов и программ. Определение структурного программирования. Основные алгоритмические структуры (конструкции)
Loading...
En provenance du cours de National Research University Higher School of Economics
Алгоритмизация вычислений (Algorithmic computation)
69 notes
National Research University Higher School of Economics
69 notes
À partir de la leçon
Основы алгоритмизации
Здравствуйте, уважаемые слушатели! На первой неделе курса мы рассмотрим различные подходы к составлению алгоритмов программ. Затем осознанно выберем систематический метод для решения задач, рассматриваемых в курсе. Также мы сравним различные способы записи алгоритмов. Кроме того, мы изучим классификацию команд, которые используются в алгоритмическом языке. По итогам недели предусмотрен тест для оценки полученных знаний. Желаем вам успехов в освоении материала!
Rencontrer les enseignants
Ерохина Елена АльфредовнаСтарший преподаватель
Департамент компьютерной инженерии МИЭМ Высшая Школа Экономики
[МУЗЫКА] Мы
с вами начнём изучение нашего предмета со следующей темы.
Рассмотрим преимущества и недостатки различных подходов к
составлению алгоритмов и программ.
Подходов к составлению алгоритмов и программ есть много,
мы с вами рассмотрим три наиболее распространённых.
И первый из этих подходов, так называемый «традиционный» подход,
состоит в следующем.
Этот подход, кстати, возник вместе с появлением первых компьютеров.
И в те времена такой профессии, как программист, просто не существовало.
Программы писали инженеры, математики, ну словом, все те люди,
которым нужны были программы для компьютеров.
Так вот.
Первым делом ставилась задача, и затем в результате некоторого
творческого процесса на свет появлялась программа.
Эти программы, как правило, были небольшого объёма,
но зачастую возникала необходимость некоторым образом эту программу улучшить:
усовершенствовать, что‐то в ней дописать, от чего‐то избавиться, что‐то исправить.
И таких итераций, то есть шагов этого процесса,
как правило, требовалось несколько.
Ну и в результате, когда программа оказывалась готовой, то, как правило,
результат выглядел, если его изобразить схематически, следующим образом.
На этой картинке мы с вами видим некоторую последовательность операторов,
они обозначены чёрными такими линеечками.
И между ними красными стрелками показаны возможные переходы.
То есть мы с вами видим, что такая программа,
она обладает очень сложной структурой, которую очень трудно анализировать.
Ну и, кроме того, можно себе легко представить, что будет, если мы попытаемся
какой‐нибудь из операторов этой программы как‐нибудь изменить.
На что это повлияет?
Это повлияет на всю программу в целом.
И существует даже такой специальный термин, это называется «BS‐программа».
От слова «блюдо спагетти», то есть структура этой программы сильно напоминает
такую тарелку с перепутанными макаронами.
Понятно, что качество таких программ, оно, конечно, никакой критики не выдерживает.
И можно сказать, что у этого подхода есть следующие недостатки.
Это, во‐первых, то, что программы трудно читать: если очень много имеется различных
переходов, то, чтобы разобраться в логике программы, нужно очень большое время.
Затем, в таких программах трудно искать и исправлять ошибки, потому что,
как мы с вами уже говорили, задев, преобразовав один оператор,
мы с вами получаем изменения во всей программе.
То есть трудно проанализировать, к чему это приведёт.
Если мы с вами исправляем ошибки, ещё хуже.
Далее, как я уже сказала,
вносить изменения в программу практически невозможно.
И, что самое печальное для нас,
этому искусству невозможно совершенно научиться и также нельзя научить.
То есть я не возьмусь научить вас писать программы традиционным методом.
Ну мы с вами идём дальше.
Если рассматривать исторически вот этот процесс, то при написании
программ возникли определённые проблемы, которые нужно было решать.
Вот первые программы, они писались одним разработчиком,
и он же потом программу сопровождал, исправлял и так далее.
Но когда появились более или менее большие проекты, понятно,
что один человек за исторически короткие сроки с этим бы не справился.
Тогда возникла необходимость поручить создание программы
коллективу разработчиков.
И вот тут начались очень интересные истории.
Казалось бы, все части программы прекрасно работают, но при соединении
частей в одну общую программу выяснялось, что всё вместе работать перестаёт.
И вот этот вот процесс объединения частей программы в одну, он был сложен.
И вот этот вот этап, когда из отдельных фрагментов создавался большой проект,
он занимал очень много времени.
И тогда в 70‐х годах прошлого века был предложен подход,
который получил название структурного подхода.
Здесь у нас с вами схема следующая.
Сначала есть задача, она как‐то сформулирована, поставлена.
Затем создаётся алгоритм решения этой задачи, который каким‐нибудь
образом записывается, и после этого идёт этап собственно программирования,
то есть кодирования алгоритма на заданном языке программирования.
Этот подход был существенно лучше предыдущего.
Чем же он был лучше?
У структурного подхода есть свои преимущества.
Рассмотрим, каковы они.
Первое преимущество этого подхода — собственно само существование алгоритма.
Если у нас есть алгоритм, то в работе программы разобраться проще,
чем если алгоритма нету.
Причём это может сделать как сам разработчик, так и другие люди.
Затем, программу и алгоритм удобно изменять,
причём изменения начинаются именно с алгоритма.
Далее. Если у нас структурный алгоритм (а что
такое структурный алгоритм, мы с вами подробно рассмотрим чуть позже),
то тогда и программа будет хорошо структурирована,
то есть никаких вот этих вот «блюд спагетти» мы, как правило, не получим.
Ну и недостатки у этого подхода, конечно же, тоже есть.
К недостаткам следует отнести, во‐первых, то,
что переход от нашей задачи к алгоритму, он не формализован.
То есть, во‐первых, неясно, как он происходит, а во‐вторых,
совершенно непонятно, за какое время он произойдёт.
То есть, если рассмотреть ситуацию с точки зрения руководителя проекта,
то на этом этапе нельзя предсказать, когда закончится разработка большой программы.
Ну и второй недостаток то, что у нас с вами алгоритм может не быть структурным.
Это зависит от способа записи алгоритма (способами записи мы с вами
займёмся чуть позже), и при таком подходе всё равно можно
получить плохо структурированную программу.
И тогда последствия будут ровно те же, что были в первом методе.
И тогда, когда возник этот метод и стали ясны его
преимущества и недостатки, был разработан третий,
собственно говоря, подход, которым мы будем с вами пользоваться.
Условно можно назвать этот подход систематическим.
Перед нами схема этого подхода.
Всё начинается, как и в прежних двух вариантах, с условия задачи.
Затем пишется постановка задачи.
Постановка задачи (мы с вами дадим строгое определение чуть позже) — это точное
перечисление того, какие данные у нас есть, какой результат мы можем получить,
и как у нас с вами связаны данные с результатом.
Затем разрабатывается метод решения задачи.
Метод решения задачи — это математика.
То есть здесь записываются все формулы, по которым будут производиться вычисления,
которые необходимы для решения нашей задачи.
Затем создаётся, кстати говоря, может создаваться параллельно методу,
внешняя спецификация, которая показывает,
как именно будет происходить у нас диалог между компьютером и пользователем.
Потом, имея метод и внешнюю спецификацию, можно уже создать алгоритм.
И, когда алгоритм создан, затем происходит процесс записи алгоритма
на заданном языке программирования, и результатом является программа.
Так вот, этот метод хорош, во‐первых, тем, что,
мы с вами видим, что в нём есть несколько этапов.
Если у нас с вами большой проект,
отдельные этапы можно поручить разным людям.
То есть созданием метода может заниматься математик,
разработкой внешней спецификации занимается дизайнер, который смотрит,
чтобы всё было красиво и правильно и учитывались все случаи,
созданием алгоритма занимается алгоритмист, который воплощает всё то,
что у нас записано в методе, и учитывая нашу внешнюю спецификацию в алгоритм,
и затем создаётся программа.
Так вот, какие преимущества и недостатки у этого метода?
К преимуществам метода можно отнести, во‐первых, надёжность программ.
То есть программы, создаваемые этим методом, отличаются тем, что они работают
очень точно, чётко, нет никаких сбоев, зацикливаний и так далее и тому подобное.
Затем, этот метод отличается эффективностью,
программы легко оптимизировать.
Потому что, имея внешнюю спецификацию и алгоритм, мы можем внести определённые
изменения в них и затем уже только изменять свою программу.
И причём важно заметить, что имея алгоритм и все остальные части,
мы с вами можем заняться оптимизацией не только непосредственно,
когда мы только написали программу, но и по прошествии некоторого времени.
То есть, если у нас с вами возникает необходимость эту программу как‐то
улучшить, усовершенствовать, переписать,
то мы можем вернуться к ней даже через значительное время.
И наличие алгоритма очень помогает вносить некоторые правки.
Затем, это метод, который отличается экономичностью: время,
которое затрачивается на отладку программы,
то есть на поиск ошибок и устранение этих ошибок,
у нас с вами существенно меньше, чем в двух предыдущих методах.
Потому что предварительные этапы,
которые мы с вами делаем до того как начинаем писать программу,
очень помогают нам не допускать ошибок, а не исправлять их, когда они уже произошли.
Затем — метод отличается эргономичностью.
Что такое эргономичность?
Ну, может быть, не все знают, — это удобство использования.
То есть когда мы с вами используем этот метод,
то у нас результатом является (промежуточным) алгоритм, и алгоритм
более удобен для чтения и понимания, чем программа на любом языке программирования.
Затем — программы у нас легко модифицируемы.
То есть мы можем внести изменения в программу в любое время и
при этом это сделать легко, потому что у нас с вами есть алгоритм,
который позволяет разобраться, как работает программа,
в том числе и не разработчику, а другим людям, которым будет это поручено.
Затем — у нас с вами программа полностью документирована.
Та схема, которую я вам сейчас рассказываю, полностью соответствует ГОСТу
— государственному общесоюзному стандарту, по которому все программы проверяются и
принимаются, если вы собираетесь эту программу сдавать заказчику.
То есть никакой другой документации, кроме перечисленной здесь,
вам делать будет не нужно.
И затем, что самое важное для нас,
этот метод эффективен при обучении программированию.
То есть, иными словами говоря,
я смогу научить вас разрабатывать этим методом надёжные программы,
правильные, легко модифицируемые, и делать это достаточно быстро.
Есть ли недостатки у этого метода?
Можно сказать,
что недостатком этого метода является большое количество документации,
которую нужно сначала разработать перед тем, как заняться программированием.
Но опыт показывает, что если мы с вами чётко соблюдаем этот метод, то время,
которое затрачивается на разработку программы в целом, с учётом отладки,
с учётом внесения изменений, оказывается меньше, чем если мы используем
традиционный метод или если мы используем метод систематический.
Так вот, мы с вами всё время говорили о том,
что есть такое структурное программирование.
Структурное программирование — это программирование,
в котором применяются только четыре базовые алгоритмические конструкции.
Иногда они называются структурами.
Мы сейчас с вами перечислим эти конструкции,
а чуть позже рассмотрим подробнее, как каждая из них работает,
какие есть ограничения, то есть научимся с ними работать.
Так вот, основные алгоритмические структуры, они же конструкции, — это,
во‐первых, простая последовательность действий, когда действия у нас с вами
выполняются непосредственно одно за другим, без повторов и выборов.
Затем — это условная конструкция, она же конструкция выбора.
Могу сказать заранее, что в языке Pascal, который мы с вами будем изучать,
есть конструкция выбора «если...
то... иначе», по‐английски и на Pascal'е — if...
then...
else. И конструкция выбора,
где больше вариантов чем два — это case...
of. Затем — к основным конструкциям относятся
циклы.
У нас с вами есть следующие разновидности циклов.
Это, во‐первых, цикл «от...
до» (или «цикл со счётчиком»).
В языке Pascal он записывается при помощи конструкции for...
to либо downto...
do. Затем — это цикл с предусловием,
это цикл while...
do.
И третий цикл — это цикл с постусловием: repeat...
until.
И наконец, последние из алгоритмических структур — это у нас с вами подпрограммы.
Подпрограммы в языке Pascal: есть процедуры и есть
функции — procedure и funcion.
[ЗВУК]
[ЗВУК]
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
