Ворожцов А.В. ПУТЬ В СОВРЕМЕННУЮ ИНФОРМАТИКУ:
Комбинаторика, анализ, теория графов, теория игр, моделированию, теория информации, логика и теория множеств. Изд. 3

Оглавление

Введение

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

Информатика – это наука об информационных и вычислительных технологиях.

С какого момента отсчитывать историю информатики вопрос определения, а не факта. Первые арифмометры, с помощью которых можно было складывать и вычитать числа, создавались еще в XVII веке. Блез Паскаль в 1645 году сконструировал машину, которая умела складывать пятиразрядные числа, через три века Джон фон Нейман описал устройство будущего компьютера EDVAC, где дал детальное определение концепции хранимой программы, и через 5 лет, в мае 1949 года, архитектура фон Неймана была реализована в компьютере EDSAC. С тех пор немногие успевают следить за эволюцией компьютеров, или, как сейчас говорят, информационных и вычислительных технологий.

Итак, полвека назад ученые и инженеры получили в свое распоряжение вычислительные машины и стали осваивать профессию программиста. В первую очередь шли задачи моделирования и управления. БЭСМ-6 (1967 г.) – первая машина с быстродействием 1 млн операций в секунду – использовалась для моделирования ядерных реакций, управления полетом космически комплексов, проектирования новых ЭВМ. Время шло, появлялись новые задачи, возникали новые вопросы.

Информатика из науки чисто вычислительной превратилась в науку междисциплинарную.

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

Может показаться, что у информатики нет фундаментальной составляющей. Конечно, это не так. Основы информатики обширны и глубоки. Это логика, языки и исчисления, вычислимые функции, дискретная математика, теория компиляции и многое другое. Завоевывая все новые и новые территории, информатика заимствует фундаментальные идеи из самых разных наук. В частности, "генетические алгоритмы", одно из направлений интеллектроники (термин интеллектроника начал активно использовать Станислав Лем в своих научно"=популярных и фантастических книгах ("Сумма Технологий", 1967; "Мегабитовая Бомба", 1999). Сегодня под интеллектроникой понимается прикладная информатика, занимающаяся созданием интеллектуальных компьютерных систем. Исследователи, работающие в этом направлении, надеются достичь такого понимания механизмов интеллекта, при котором можно будет составлять компьютерные программы с человеческим или более высоким уровнем интеллекта. Общий подход состоит в разработке методов решения задач, для которых отсутствуют формальные алгоритмы: понимание естественного языка, обучение, доказательство теорем, распознавание сложных образов и т.д. Теоретические исследования направлены на изучение интеллектуальных процессов и создание соответствующих математических моделей. Экспериментальные работы ведутся путем составления компьютерных программ и создания машин, решающих частные интеллектуальные задачи или разумно ведущих себя в заданной ситуации), основаны на идее, которая лежит в основе теории эволюции Чарльза Дарвина. А именно, создается некоторая "популяция" программ, решающих одну и ту же задачу. Затем начинается "жизнь" с отбором тех, которые лучше всего проявили себя при решении поставленной задачи. Только эти лучшие представители будут подвергаться дальнейшим мутациям и рекомбинациям в поисках более эффективных "особей".

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

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

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

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

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

В этой книге я постарался собрать опыт преподавания "занимательной математики" в летних математических школах – Кировской ЛМШ и Московской компьютерной школе в Дубне, а также в Физтех-Колледже.

Я благодарен Алексею Белову за замечательные семинары, которые он вел в Кировской Летней математической школе и на которых мне посчастливилось присутствовать, а также всем моим друзьям, которые активно помогали мне, давали умные советы и находили ошибки – Оле Люлько, Григорию Лабзину и Кате Татариновой.