Лекция 6

Дополнительная литература для самостоятельной работы по теме

Контрольные вопросы

1. Какую трактовку понятия «переживание» предложил в свое вре­мя Л. С. Выготский?

2. Какова динамика переживаний школьника на различных этапах процесса обучения согласно взглядам Л. И. Божович?

3. Каким образом развитие личности школьника связано с органи­зацией учебной деятельности? 4. Какую роль играет Я-концепция в процессе обучения и воспита­ния школьников?

5. В чем заключается психологическая сущность «аффекта неадек­ватности» в поведении школьников?

6. Какие психологические предпосылки были положены в основу концепции общего развития младших школьников Л. В. Занкова?

7. Как протекает процесс воспитания развивающегося человека с точки зрения теории Р. Штейнера?

8. Какое место занимает эстетическое переживание школьника в про­цессе его воспитания?

9. Каковы психологические предпосылки предупреждения и пре­одоления дидактогений у школьников?

1. Берне Р. Развитие Я-концепции и воспитание. — М.: Прогресс, 1986. 424 с.

2. Божович Л. И. Личность и ее формирование в детском возрасте. — М.: Просвещение, 1968. 464 с.

3. Божович Л. И. Проблемы формирования личности. — М.: Изд-во «Институт практической психологии»; Воронеж: Изд-во НПО «МОДЭК», 1995. 352 с.

4. Василюк Ф. Е. Психология переживания. — М.: Изд-во Моск. ун­та, 1984. 200 с.

5. Выготский Л. С. Вопросы детской (возрастной) психологии // Выготский Л. С. Собр. соч.: В 6 т. Т. 4. Детская психология. — М.: Педагогика, 1984. С. 243-385.

6. Выготский Л. С. Педагогическая психология. — М.: Педагогика, 1991.480с.

7. Дусавицкий А. К. Развитие личности в учебной деятельности. — М.: Дом педагогики, 1996. 208 с.

8. Жутикова Н. В. Учителю о практике психологической помощи. — М.: Просвещение, 1988. 176с.

9. Славина Л. С. Трудные дети. — М.: Изд-во «Институт практичес­кой психологии»; Воронеж: Изд-во НПО «МОДЭК», 1998.447 с.

10. Смирнов Н. К. Здоровьесберегающие образовательные техноло­гии и психология здоровья в школе. — М.: АРКТИ, 2005. 320 с.

6.1. ОСНОВЫ ТЕОРИИ АЛГОРИТМОВ

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

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

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

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

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

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

Первый способ - суперпозиция, т. е. подстановка функций в функции, порождающая математические формулы, в которых порядок действий определяется расстановкой скобок. Например, формула а × b + c/d получается подстановкой в функцию х + у функций а × b вместо х и c/d вместо у.

Другой способ – рекурсия, т. е. определение очередного значения функции через ранее вычисленные значения этой же функции. Классическим примером рекурсии служит функция «факториал»:

n! = 1 × 2× 3 × … n.

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

0! = 1;

(n +1)! = n! (n+1).

Структура такого определения функций (называемого примитивно-рекурсивным) состоит из двух частей: определения значения функции f для начального значения аргумента (в нашем примере - для 0) и определения f (n + 1) через f (n) и другую функцию, которая считается определенной ранее (в примере роль этой функции играет умножение). Т. е. для вычисления f (n + 1) надо вычислить f в предыдущих точках: 1, 2... n.

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

Второе направление поиска теоретических моделей алгоритмов основано на простой идее: для того чтобы алгоритм понимался однозначно, а каждый его шаг можно было считать элементарным и выполнимым, он должен быть представлен так, чтобы его могла выполнять машина. Чем проще структура машины и ее действия, тем убедительнее выглядит утверждение, что ее работа и есть выполнение некоторого алгоритма. При этом структура машины должна быть универсальной, такой, чтобы на ней можно было выполнить любой алгоритм. Эта идея привела к концепциям абстрактной машины как универсальной алгоритмической модели. Она была выдвинута А. Тьюрингом и Э. Постом практически одновременно (в 1936 — 1937 гг.). Действия абстрактной машины сводятся к тому, что она обозревает символы, записанные в памяти, и в зависимости от своего состояния и того, каков обозреваемый символ, она стирает его или заменяет другим символом или какой-то последовательностью символов, после чего переходит в новое состояние и читает следующий символ. Наибольшую известность среди моделей такого типа получила модель Тьюринга, за которой закрепилось название «машина Тьюринга».

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

Наиболее известная алгоритмическая модель этого типа – так называемые нормальные алгоритмы Маркова (название происходит от имени советского математика А. А. Маркова).

В теории алгоритмов установлен важный факт: в универсальной алгоритмической модели всегда существует универсальный алгоритм, т. е. алгоритм, который способен моделировать работу любого другого алгоритма, описанного в этой модели. Универсальный алгоритм устроен следующим образом. Имеется метод кодирования S для любого алгоритма А в данной модели. Если на вход универсального алгоритма U подать код S(A) алгоритма A и исходные данные х, то результат работы U будет равен результату работы А над х: U(S(A),x) = А(х). По существу, метод кодирования алгоритмов - это язык программирования, а код S(A) - это программа алгоритма А в языке S. Поэтому концепция универсального алгоритма, существование которого было доказано в 30-х гг. нашего века (раньше, чем появились универсальные ЭВМ), свидетельствует о том, что в основе работы ЭВМ лежат не только физические, но и математические идеи (успехи электроники влияют лишь на быстродействие и размеры ЭВМ).

С гордостью отметим, что значительный вклад в развитие теории алгоритмов внесли советские ученые А. А. Марков, А. И. Мальцев, В. М. Глушков, А. Н. Колмогоров, А. П. Ершов, Ю. Л. Ершов, А. А. Ляпунов, П. С. Новиков, С. В. Яблонский и многие другие.

В настоящее время теорию алгоритмов разделяют на классическую и прикладную.

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

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

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

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

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

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

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

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

6.2. ФОРМЫ ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ

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

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

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

Безусловные шаги принято изображать прямоугольниками, условные шаги – ромбами. Из ромба всегда выходят две стрелки: одна имеет пометку «да» (условие выполнено), другая - пометку «нет» (условие не выполнено). Граф, изображенный на рисунке 8, соответствует процессу отыскания максимального числа в последовательности, который был описан ранее.

Процесс выполнения алгоритма представляется в графе как путь из начальной вершины в конечную. Если все шаги алгоритма безусловные, то этот путь при любых данных одинаков, хотя результаты, разумеется, могут быть различными. Если же в алгоритме есть условные шаги (а чаще всего так и бывает), то путь зависит от выполнения содержащихся в них условий. Как правило, алгоритм содержит циклы, т. е. замкнутые пути, возвращающиеся в пройденную ранее вершину. Алгоритм на нашем рисунке содержит цикл между шагами 6 и 10, который разветвляется в шаге 7. Поэтому возможны два варианта прохождения цикла 6, 7, 8, 9, 10, 6 и 6, 7, 10, 6. Цикл обязательно содержит условную вершину, в которой можно выйти из цикла. В данном примере такой вершиной является шаг 10. Выход из цикла происходит, когда все числа последовательности просмотрены. Если условия выхода из цикла сформулированы неправильно, то может оказаться, что они никогда не выполняются, и процесс исполнения алгоритма становится бесконечным (зацикливается).

Для компактного описания циклов в языках программирования имеются специальные операторы циклов. Основную часть нашего примера (шаги 2 - 10) с помощью такого оператора можно записать гораздо короче. Правда, оператор цикла нельзя считать элементарным шагом, в частности, потому, что время его выполнения зависит от исходных данных и может быть сколь угодно большим.

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

Крупный шаг - это фактически алгоритм, являющийся частью (подалгоритмом) более сложного алгоритма. Такие подалгоритмы называются блоками. Блок обычно не элементарен (его размеры неограниченны и выбираются произвольно). Однако правильно сформулированный блок обладает всеми другими признаками алгоритмического шага. В частности, он имеет точно выделенное начало (точку входа) и может быть условным или безусловным. У безусловного блока — всегда одна точка выхода. Условный блок имеет несколько точек выхода (их может быть больше двух, если блок содержит несколько условий). Другие блоки алгоритма связаны с данным блоком только через точки входа и выхода. Поэтому если блок правильно решает свою задачу, т. е. всегда дает нужный результат, то его внутренняя структура несущественна для остальной части алгоритма. Из этого следуют два важных вывода.

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

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

Блок-схемы являются частным случаем наглядных форм представления алгоритмов. Существуют и другие способы представления: операторные алгоритмы, диаграммы смены состояний и т. п. Развивается и теория таких представлений.

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

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

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

Дата добавления: 2013-12-13