Текст книги "Вычислительное мышление: Метод решения сложных задач"

Пол Керзон, Питер Макоуэн
Вычислительное мышление: Метод решения сложных задач

Перевод Таира Мамедова

Редактор Ирина Тулина

Главный редактор С. Турко

Руководитель проекта А. Василенко

Корректоры Е. Аксёнова, О. Улантикова

Компьютерная верстка А. Абрамов

Дизайн обложки Ю. Буга

© World Scientific Publishing Co. Pte. Ltd., 2017

Russian translation arranged with World Scientific Publishing Co. Pte. Ltd., Singapore

© Издание на русском языке, перевод, оформление. ООО «Альпина Паблишер», 2018

Все права защищены. Произведение предназначено исключительно для частного использования. Никакая часть электронного экземпляра данной книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами, включая размещение в сети Интернет и в корпоративных сетях, для публичного или коллективного использования без письменного разрешения владельца авторских прав. За нарушение авторских прав законодательством предусмотрена выплата компенсации правообладателя в размере до 5 млн. рублей (ст. 49 ЗОАП), а также уголовная ответственность в виде лишения свободы на срок до 6 лет (ст. 146 УК РФ).

* * *

Предисловие

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

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

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

Надеемся, что «Вычислительное мышление» увлечет вас и вы будете учиться думать как ученые-информатики.

Об авторах

Пол Керзон – преподаватель информатики Лондонского университета королевы Марии. В его научные интересы входят методика обучения информатике, взаимодействие человека с компьютером и формальные методы. В 2010 г. он стал лауреатом премии для преподавателей, учрежденной Академией высшего образования. В 2007 г. получил приз Совета по инженерным и физическим научным исследованиям как лучший непрофессиональный автор, пишущий о компьютерных науках. Один из основателей ресурса «Преподавание информатики в Лондоне» (Teaching London Computing, www.teachinglondoncomputing.org), который оказывает поддержку преподавателям в непрерывном профессиональном развитии. Самостоятельно освоил программирование, лежа на пляже на юге Франции.

Питер Макоуэн тоже преподаватель информатики Лондонского университета королевы Марии. Среди его научных интересов – машинное зрение, искусственный интеллект и робототехника.

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

Пол и Питер вместе создали проект «Занимательная информатика» (Computer Science for fun, www.cs4fn.org) и стали первыми членами британского объединения «Информатика в учебных заведениях» (Computing at School, CAS). Сейчас Пол – член совета директоров этой организации.

Благодарности

Эта книга – сборник новых материалов и переработанных статей, опубликованных на нашем сайте «Занимательная информатика» (www.cs4fn.org) и на другом нашем сайте «Преподавание информатики в Лондоне» (www.teachinglondoncomputing.org), предназначенном для поддержки учителей.

Мы благодарны Лондонскому университету королевы Марии, который всегда поддерживал нашу работу с общественностью. Все эти годы, пока мы занимались созданием занимательных материалов по информатике, мы получали финансовую поддержку от разных организаций, среди которых Лондонский университет королевы Марии, Совет по инженерным и физическим научным исследованиям (EPSRC), Google, мэрия Лондона, департамент образования, BCS, Исследовательские советы Великобритании (RCUK), Microsoft и ARM.

Нам оказали большую поддержку преподаватели со всей страны и из-за границы. Особую роль сыграли учителя, ученые, представители отрасли и члены нашего объединения «Информатика в учебных заведениях». Они активно содействовали нам и внесли ценный вклад в нашу работу, обмениваясь идеями и тестируя многие из предложенных заданий на практике. Также мы благодарны многим и многим студентам и преподавателям, которых мы в последние десять лет одолевали нашими веселыми занятиями, – за энтузиазм, готовность участвовать и помощь в рождении новых идей. Саймон Пейтон-Джонс из Microsoft Research, Питер Дикман из Google и Билл Митчелл из Британского компьютерного общества невероятно помогли нам. Тим Белл, Куинтин Каттс и команды, разрабатывающие задания по информатике для работы без компьютера в университетах Кентербери и Глазго, стали нашим источником вдохновения – как и многие другие. Задача «Ход конем», в частности, появилась благодаря идее Мацея Сыслё и Анны Беаты Квятковской из Университета Николая Коперника.

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

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

Мы много и с большой пользой обсуждали математику и фокусы с Мэттом Паркером, Джейсоном Дэвисоном и Ричардом Гэрриоттом. Мы также хотели бы поблагодарить изобретательных фокусников наших дней и былых времен за то, что они придумали хитрые математические трюки с использованием вычислительных алгоритмов, которые мы теперь показываем и преподаем. Это Ник Трост, Дж. Хартман, Пол Гордон, Брент Моррис, Колм Малкехи, Артур Бенджамин, Макс Мэйвен, Альдо Коломбини, Перси Дайаконус, Джон Бэннон и, повторимся, великий ныне покойный Мартин Гарднер. Мы рекомендуем вам посмотреть их работы и больше узнать об алгоритмических фокусах. У них вы найдете удивительные приемы, алгоритмы и идеи для развлечения, а еще, возможно, откроете самый важный секрет: фокусы, не говоря уже о вычислительном мышлении, – замечательное хобби.

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

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

Глава 1
Мышление будущего

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

Что с ним делать?

Представьте, что вы ученый и пытаетесь понять поведение птиц, которые ищут корм на земле. Одни кормятся, а другие смотрят в небо, чтобы вовремя увидеть хищника. Как они распределяют роли? Другие ученые тратят время на наблюдения за птицами, но вы идете дальше. Вы придумываете алгоритм – последовательность шагов, – которому должны следовать птицы, чтобы распределить роли. Потом вы создаете компьютерную модель и симулируете сценарии на основе гипотезы, что каждая птица смотрит на своих соседей. Это не только совпадает с результатами ваших наблюдений, но еще и позволяет делать прогнозы, поддающиеся проверке.

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

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

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

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

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

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

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

Навыки для XXI века

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

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

Так что же такое вычислительное мышление? Это не «то, как думают компьютеры», хотя их все чаще программируют на его использование. Это набор разнообразных человеческих навыков для решения задач. Чтобы их приобрести, необходимо изучать природу вычислительных процессов. Кроме того, необходимы такие определенно важные навыки, как умение творить, ясно объяснять и работать в команде, – но их развивают практически все учебные предметы. Вычислительное мышление заимствует элементы из других типов мышления, например математического и научного. Однако в его основе лежат очень конкретные навыки решения проблем, такие как способность мыслить логически и алгоритмически, не упуская ни одной детали, а также умение находить эффективные способы что-нибудь сделать. Также важную роль играет способность понимать других людей. Информатика уникальна в том плане, что она объединяет все эти разнообразные навыки. Вместе они формируют мощный тип мышления, который меняет мир. Именно благодаря ему мы стали по-новому заниматься наукой, делать покупки, вести бизнес, слушать музыку, играть в игры – в общем, жить по-новому.

Алгоритмическое мышление

Алгоритмическое мышление лежит в основе вычислительного мышления. Оно позволяет находить решения задач нетрадиционным способом. Для специалиста по информатике решить задачу – это не просто получить ответ, например «42». И даже не добиться конкретного результата – например, «я решил судоку из сегодняшнего номера». Решения – это алгоритмы! Алгоритм – просто набор инструкций, которым необходимо следовать. Если точно их выполнять, вы получите собственно ответ на задачу («42») или добьетесь, чего хотите (например, решите судоку). Как только вы получите алгоритмическое решение, вы будете решать подобные задачи вообще не задумываясь, просто «слепо» следуя инструкциям. При наличии такого алгоритма задачу, не углубляясь в суть программы, решит кто угодно. При этом не надо знать или понимать, как в конечном итоге работает алгоритм. Можно даже не иметь представления о том, что вы решаете судоку (и что такое вообще судоку). А это значит, что бездушная машина, компьютер, тоже будет механически следовать инструкциям и решать подобные задачи в любой форме. Именно так и работают компьютеры – они выполняют алгоритмы, написанные людьми.

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

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

Изменить мир

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

Научное мышление

Алгоритмическое мышление – это не просто способ решать задачи. Оно открывает новые пути для понимания мира. В традиционной науке используются эксперименты. Биологи ставят эксперименты на крысах и обезьянах, на клеточных культурах. Медики проводят испытания лекарственных препаратов. Физики ставят эксперименты над самим миром. Однако, если мыслить алгоритмически, возможен другой вариант. Если существует теория, объясняющая некое явление, будь то воздействие радиации на поверхность планеты, формирование экосистемы или развитие злокачественной опухоли, мы можем создать алгоритмы, работающие подобным образом. Мы можем создать вычислительную модель – программу, которая должна симулировать интересующие нас феномены, и проводить эксперименты на модели, а не в реальном мире. Если мы правильно понимаем явление, то программа будет вести себя как объект моделирования. Если этого не произойдет, значит, с нашей теорией что-то не так. Обдумывая, что пошло не так, мы обнаружим, чтó надо изменить в теории, и, таким образом, будем лучше понимать явление. Вполне вероятно, что изучение модели выведет нас на новые предположения, которые можно проверить уже в реальном мире.

Вычислительное мышление

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

Глава 2
В поисках способа говорить

Одним из самых тяжелых патологических состояний, какие только можно вообразить, является синдром «запертого человека». Человек в таком состоянии полностью парализован и в лучшем случае в состоянии только моргать. Разум заключен в тюрьму бесполезного тела. Человек воспринимает все вокруг, но не может передавать информацию. Тем, кто хотел бы помочь людям с таким синдромом, очевидно, нужно учиться на медиков. Но может ли что-нибудь сделать программист?

Сидром «запертого человека»

Синдром «запертого человека» – это полный паралич тела после инсульта. Вы продолжаете думать, видеть, слышать. Вы так же разумны, как и прежде. Это может случиться с каждым. Лечения этого заболевания нет, поэтому максимум, что могут сделать медики, – позаботиться об удобстве пациента. Но возникает важный вопрос: как помочь пациентам с синдромом «запертого человека» «разговаривать». Как им общаться с врачами, семьей и друзьями? Очевидно, специалист по информатике мог бы изобрести новую технологию, которая была бы полезна в этой ситуации. Однако благодаря вычислительному мышлению мы можем предложить способ гораздо лучше, чем просто «полезная технология».

«Скафандр и бабочка» – невероятно жизнеутверждающая книга. Это автобиография Жан-Доминика Боби, которую он написал после того, как очнулся в больнице полностью парализованным. Он рассказывает о жизни с синдромом «запертого человека». То есть у него был способ общения, который позволил не только разговаривать с медиками, друзьями и семьей, но и написать книгу. Боби сделал это, вообще не прибегая к технике. Но как?

Представьте себя в его положении – очнулись на больничной койке. Как вы могли бы общаться? Как могли бы написать книгу? Только человек с ручкой и бумагой смотрит на вас, готовый записывать слова. Вы из тех, кому повезло, – вы можете моргать одним глазом, но это все. Это единственное движение, которое вам доступно. Значит, разговаривать вы не в состоянии. Однако вы видите и слышите.

Теперь представьте, что вы врач такого пациента и вам необходимо придумать способ общения с ним.