Является ли математика частью информатики?
Цейтин Г.
Я не согласен с утверждением, что информатика (какой бы термин для нее ни использовали) - это набор практических навыков и решений, в лучшем случае - искусство, и никакого фундаментального научного содержания она иметь не может. Я думаю, что, несмотря на возможные терминологические недоразумения, мы все более или менее одинаково понимаем, о какой области деятельности идет речь. Информационные технологии в современном мире - это уже давно утвердившаяся реальность, так же, как и то, что существуют профессионалы, специализирующиеся именно в этой области, что необходимо готовить специалистов в этой области, писать книги и статьи, издавать журналы, оценивать профессиональный уровень и т.п. Раз есть область, должно быть имя, чтобы ни с чем не спутать. Термин информатика (французское informatique) представляется мне достаточно удачным, и, во всяком случае, лучшим, чем американское computer science.
Прежде, чем пытаться уточнить содержание этой области (насколько это вообще возможно), хотелось бы проследить, как вообще формировалось самоосознание этой области, как особой области знаний, а также общественное признание ее самостоятельности (сегодня такое признание - уже свершившийся факт).
Но ни самоосознание области, пионеры которой были и считали себя специалистами в других областях, ни выделение ей места под солнцем в ряду других специальностей, не могли быть простыми. Новая область требует выделения ей отдельных ресурсов, и людских, и материальных, а это не могло происходить бесконфликтно и вполне добросовестно. Я имею в виду не только СССР, где все эти проблемы многократно усиливались научным монополизмом и порожденными им интригами. Эти проблемы существовали и в более благополучных странах.
Нового предмета, отличного от всего, что было прежде, информатика не создала. Программа вполне подходит под математическое понятие алгоритма (с некоторыми уточнениями из-за параллельного исполнения или недетерминированности), так где же новый предмет? И представители традиционных областей, стремясь удержать под своим контролем ресурсы, выделение которых на новые приложения диктовалось практическими потребностями, пользовались этим аргументом. Как говорил один мой коллега-матфизик: "И чего это все так носятся с этим системным программированием? Это ведь всего-навсего программирование для системы машин!" А другой коллега, просматривая проект учебных программ по информатике, заявлял: "Это какая-то эклектика, просто собраны вместе кусочки, принадлежащие другим дисциплинам". Впрочем, подобная аргументация известна еще из пушкинской "Сказки о царе Салтане", где "ткачиха с поварихой, с сватьей бабой Бабарихой" развенчивали (и небеcкорыстно) одно за другим все чудеса, о которых рассказывали заморские гости.
Надо признать, что и представители новой области допуcкали натяжки ради того, чтобы организационно выделить свой предмет. Мне приходилось видеть математические работы, где поверхностно формализовывались некоторые, уже устарелые, программистские концепции, а затем доказывались "сногсшибательные" результаты, основанные на совершенно нереальных примерах (в математике это нормально, но на основе этого следовало просто заменить первоначальные понятия, чтобы они не включали подобные случаи). И все это делалось ради того, чтобы заявить о принадлежности своих (не бог весть каких) результатов новой перспективной области. Впрочем, эти болезни были постепенно преодолены.
А как осознает себя эта область теперь, когда организационное признание состоялось? К сожалению, осознания особого предмета по-настоящему нет. Авторитетные специалисты, пришедшие из других областей, зачастую связаны прежними представлениями, а молодежь, похоже, просто работает, не задумываясь об отграничении предмета.
А необходимость в таком осознании есть. Действительно, компьютерная программа может рассматриваться как разновидность алгоритма, но почему в таком случае возникают все новые и новые языки программирования и новые концепции, например, объектно-ориентированное программирование? Ведь в принципе любая программа эквивалентна некоторой машине Тьюринга, так что вроде бы ничего нового все эти языки не несут! А дело в том, что даже в одном и том же предмете с разных точек зрения могут быть важны разные стороны, и то, что важно с точки зрения математики, не совпадает с тем, что важно с точки зрения информатики. Различие между математикой и информатикой в оценочных критериях в свое время достаточно четко описал Ласло Кальмар*, пришедший в программирование из математической логики.
Главное отличие от математики, хотя бы и рассматривались одни и те же объекты, состоит, на мой взгляд, в том, что в информатике определяющим является человеческий фактор. Программы пишутся людьми, часто большими коллективами; даже если программу пишет один человек, он пользуется полученными от других людей знаниями и приемами, и, возможно, получил первоначальное задание от кого-то другого. Программа имеет жизненный цикл: после создания она может модифицироваться, переноситься в другую среду, стыковаться с другими программами, и в конце концов выходить из употребления (тоже по разным причинам). Учитывает ли эти реальности математическое понятие, претендующее на определение программы? Разве может алгоритм (в точном математическом понимании) меняться? Если что-то изменится, это будет просто другой алгоритм, который не надо путать
www.studsell.com
Цейтин Г.
Я не согласен сутверждением, что информатика (какой бы термин для нее ни использовали) - этонабор практических навыков и решений, в лучшем случае - искусство, и никакогофундаментального научного содержания она иметь не может. Я думаю, что, несмотряна возможные терминологические недоразумения, мы все более или менее одинаковопонимаем, о какой области деятельности идет речь. Информационные технологии всовременном мире - это уже давно утвердившаяся реальность, так же, как и то,что существуют профессионалы, специализирующиеся именно в этой области, чтонеобходимо готовить специалистов в этой области, писать книги и статьи, издаватьжурналы, оценивать профессиональный уровень и т.п. Раз есть область, должнобыть имя, чтобы ни с чем не спутать. Термин информатика (французскоеinformatique) представляется мне достаточно удачным, и, во всяком случае,лучшим, чем американское computer science.
Прежде, чемпытаться уточнить содержание этой области (насколько это вообще возможно),хотелось бы проследить, как вообще формировалось самоосознание этой области,как особой области знаний, а также общественное признание ее самостоятельности(сегодня такое признание - уже свершившийся факт).
Но нисамоосознание области, пионеры которой были и считали себя специалистами вдругих областях, ни выделение ей места под солнцем в ряду другихспециальностей, не могли быть простыми. Новая область требует выделения ейотдельных ресурсов, и людских, и материальных, а это не могло происходитьбесконфликтно и вполне добросовестно. Я имею в виду не только СССР, где все этипроблемы многократно усиливались научным монополизмом и порожденными иминтригами. Эти проблемы существовали и в более благополучных странах.
Новогопредмета, отличного от всего, что было прежде, информатика не создала.Программа вполне подходит под математическое понятие алгоритма (с некоторымиуточнениями из-за параллельного исполнения или недетерминированности), так гдеже новый предмет? И представители традиционных областей, стремясь удержать подсвоим контролем ресурсы, выделение которых на новые приложения диктовалосьпрактическими потребностями, пользовались этим аргументом. Как говорил один мойколлега-матфизик: "И чего это все так носятся с этим системнымпрограммированием? Это ведь всего-навсего программирование для системымашин!" А другой коллега, просматривая проект учебных программ поинформатике, заявлял: "Это какая-то эклектика, просто собраны вместекусочки, принадлежащие другим дисциплинам". Впрочем, подобная аргументацияизвестна еще из пушкинской "Сказки о царе Салтане", где "ткачихас поварихой, с сватьей бабой Бабарихой" развенчивали (и небеcкорыстно)одно за другим все чудеса, о которых рассказывали заморские гости.
Надо признать,что и представители новой области допуcкали натяжки ради того, чтобыорганизационно выделить свой предмет. Мне приходилось видеть математическиеработы, где поверхностно формализовывались некоторые, уже устарелые,программистские концепции, а затем доказывались "сногсшибательные"результаты, основанные на совершенно нереальных примерах (в математике этонормально, но на основе этого следовало просто заменить первоначальные понятия,чтобы они не включали подобные случаи). И все это делалось ради того, чтобызаявить о принадлежности своих (не бог весть каких) результатов новойперспективной области. Впрочем, эти болезни были постепенно преодолены.
А как осознаетсебя эта область теперь, когда организационное признание состоялось? Ксожалению, осознания особого предмета по-настоящему нет. Авторитетныеспециалисты, пришедшие из других областей, зачастую связаны прежнимипредставлениями, а молодежь, похоже, просто работает, не задумываясь об отграничениипредмета.
А необходимостьв таком осознании есть. Действительно, компьютерная программа можетрассматриваться как разновидность алгоритма, но почему в таком случае возникаютвсе новые и новые языки программирования и новые концепции, например, объектно-ориентированноепрограммирование? Ведь в принципе любая программа эквивалентна некоторой машинеТьюринга, так что вроде бы ничего нового все эти языки не несут! А дело в том,что даже в одном и том же предмете с разных точек зрения могут быть важны разныестороны, и то, что важно с точки зрения математики, не совпадает с тем, чтоважно с точки зрения информатики. Различие между математикой и информатикой воценочных критериях в свое время достаточно четко описал Ласло Кальмар*,пришедший в программирование из математической логики.
Главное отличиеот математики, хотя бы и рассматривались одни и те же объекты, состоит, на мойвзгляд, в том, что в информатике определяющим является человеческий фактор.Программы пишутся людьми, часто большими коллективами; даже если программупишет один человек, он пользуется полученными от других людей знаниями иприемами, и, возможно, получил первоначальное задание от кого-то другого.Программа имеет жизненный цикл: после создания она может модифицироваться,переноситься в другую среду, стыковаться с другими программами, и в концеконцов выходить из употребления (тоже по разным причинам). Учитывает ли этиреальности математическое понятие, претендующее на определение программы? Развеможет алгоритм (в точном математическом понимании) меняться? Если что-тоизменится, это будет просто другой алгоритм, который не надо путать с первым.Если же мы хотим, чтобы программа, например, адаптируемая к другому окружению,оставалась тем же самым объектом, то понятие программы должно существенноизмениться (в общем, некоторые математические подходы к описанию этого тожевозможны, но никогда теоретики со стороны математики этого не предлагали).Важной особенностью программ является то, что они могут иметь ошибки, и, вовсяком случае, необходимы меры для уменьшения их числа и ущерба от них. Этотоже не из математики. Вспомним, кстати, и о проблеме двухтысячного года.
Для чегопридумываются новые и новые языки программирования? "Для большегоудобства", возможно, ответят. А что такое удобство? Это снова человеческийфактор. Если всерьез, то это более точное соответствие элементов предлагаемогоязыка и тех понятий и знаний, которыми пользуется человек, ставя и решая ту жезадачу. Значит, надо понимать структуру человеческого знания и человеческогомышления. Целый ряд особенностей новых языков программирования, возможно,казавшихся первоначально случайными удачными находками, отражает глубокие чертыорганизации человеческих знаний и человеческого языка. Но достаточного вниманияэтому не уделяется. (Один мой коллега из промышленности, нуждавшийся вспециалистах по языкам программирования, спрашивал меня, не на филологическомли факультете их искать.)
Кромеиндивидуального фактора, есть еще и социальный. Уже упоминалось о разработкепрограмм большими коллективами, а также о сопровождении программ. Есть ещенеобходимость переносить программы на вновь разрабатываемую технику иливключать в новые системы. Надо считаться и с тем, что программы, работающие наодной машине или иным образом взаимодействующие либо совместно пользующиесяресурсами, могут отражать интересы разных людей, возможно, находящихся вконфликте, и, значит, надо заниматься защитой программ.
Когда сталшироко входить в жизнь Интернет, стала насущной необходимостью разработкаподходов, обеспечивающих правильное взаимодействие большого числа независиморазработанных программ (или их элементов). Одновременно увеличение скоростимашин сделало менее существенной экономию команд на нижнем уровне. В сумме этопривело к использованию структур данных, которые раньше считались бынеприемлемыми из-за неэффективности, и, соответственно, к новой организацииязыков. Широкое распространение модульности вместе с приемлемостью большихнакладных расходов на межмодульное взаимодействие привело к уменьшению размеровотдельных модулей, и, как следствие, к упрощению синтаксиса языков. Кстати, вэтом я вижу и причину создания и последующего широкого распространения языкаJava.
Кому жезаниматься исследованием человеческих и социальных факторов в информатике?Снова чудится мне указующий перст чиновного скептика, внушающего, что это делотаких-то и таких-то уже существующих наук: психологии, социологии, и т.п. Неполучится! И не только потому, что во всех этих науках есть свои интересы ипредпочтения, а их представители могут и не понять важности проблем, диктуемыхзадачами информатики (у меня есть определенный отрицательный опыт). Достаточнорассмотреть, к чему привело отождествление информатики с математикой.
Информатикаполучила от математики ряд результатов и теорий, нашедших широкое применение, вособенности в теории языков и трансляции, а также (в меньшей мере) поверификации программ. Вместе с тем, поскольку это делали математики (или люди,относившие себя к математике) выбор задач диктовался желанием получитьрезультаты, интересные в математическом смысле, а другие, не менее важные дляинформатики, задачи оставались без внимания. Теория языков и трансляции,например, оказалась слишком раздутой, а вопросы модульности (что на сегодняважнее) не получили должного развития. Преувеличена была и роль логическойверификации - на практике требования к программам редко оформляются влогических понятиях. Отрицательную роль сыграла и ориентация на"диссертабельность". Программистские работы, содержавшие достаточный творческийвклад, обладавшие и новизной, и полезностью, и делавшие ее автора достойнымученой степени, искусственно подводились, ввиду отсутствия надлежащих рубрик,под вычислительную математику, экспериментальную физику и т.п., и люди,причастные к прохождению работы, закрывали глаза на то, что она заявленнойспециальности не соответствует. Это, в свою очередь, приводило к появлению, всилу прецедента, диссертаций, не содержавших серьезного вклада ни в"титульную" область, ни в информатику. С другой стороны,программистские работы иногда снабжались "орнаментальной"математикой, когда определения искусственно стилизовывались под математическиетеории.
Нет основанийрассчитывать и для других смежных областей, что вопросы, практически важные дляинформатики, будут успешно решаться в рамках этих областей. Отсутствиеполномасштабного самоосознания информатики как особой науки начинает мешать ееразвитию. Списоклитературы
Для подготовкиданной работы были использованы материалы с сайта http://en.edu.ru/
2dip.su
Преподаватель: Привалов А.А. доцент кафедры ТИДМ
Структура и содержание дисциплины
Общая трудоемкость дисциплины составляет 6 зачетных единиц (216 часов).
Структура дисциплины
№ п/п
Наименование раздела дисциплины
Семестр
Виды учебной работы
(в академических часах)
Л
С
ПЗ
ЛБ
СР
1
Множества.
2
4
1
2
2
Операции и функции над множествами.
2
4
4
2
3
Числа комбинаторики.
2
4
1
2
4
Начала алгебры
2
2
2
4
5
Симметрическая группа.
2
4
2
2
6
Функции и размещения
2
4
4
3
7
Перестановки
2
2
4
4
8
Генерирование перестановок
2
4
6
6
9
Подмножества, множества с повторениями
2
2
2
4
10
Генерирование k-элементных подмножеств
2
2
4
6
11
Разбиение множества
2
2
4
6
12
Числа Стирлинга первого и второго рода
2
2
2
4
13
Генерирование разбиений множества
3
2
6
4
14
Разбиения чисел
3
2
6
4
15
Производящие функции
3
1
4
4
16
Рекуррентные последовательности и уравнения
3
2
4
4
17
Принцип включения и исключения
3
1
4
4
18
Обратные задачи комбинаторики
3
2
2
4
19
Конечные поля.
3
1
2
4
20
Уравнения и системы уравнений над Zm.
3
2
2
5
21
Цепные дроби.
3
2
2
4
22
Алгоритм Евклида
3
1
2
4
23
Рекурсия
3
2
2
4
^ Содержание дисциплины
№п/п
Наименование раздела дисциплины
Содержание раздела
(дидактические единицы)
1
Множества.
Множества. Кортеж. Декартово произведение множеств. Конечные и бесконечные множества. Мощность множества
2
Операции и функции над множествами.
Операции и функции над множествами. Решение уравнений на нахождение неизвестного множества. Моделирование подмножеств множества. Введение в комбинаторику.
3
Числа комбинаторики.
Числа комбинаторики. Моделирование сочетаний множества
4
Начала алгебры
Группы и подгруппы. Теорема Лагранжа. Теоремы Ферма и Эйлера
5
Симметрическая группа.
Симметрическая группа. Теорема Кэли. Моделирование перестановок. Кольцо и поле
6
Функции и размещения
Решение задач на нахождение функция и размещения с помощью ЭВМ
7
Перестановки
Различные алгоритмы моделирования перестановок. Разложение на циклы. Тип перестановки.
8
Генерирование перестановок
Различные компьютерные программы, моделирующие перестановки, сравнение их по сложности. Программы для определения четности и типа перестановки
9
Подмножества, множества с повторениями
Алгоритмы и компьютерные программы, моделирующие подмножества и множества с повторениями
10
Генерирование k-элементных подмножеств
Алгоритмы и компьютерные программы, моделирующие k-элементные подмножества
11
Разбиение множества
Алгоритмы, моделирующие разбиения множества. Тип разбиения множества.
12
Числа Стирлинга первого и второго рода
Свойства и теоремы для чисел Стирлинга. Число сюръективных отображений. Числа Белла.
13
Генерирование разбиений множества
Алгоритмы и компьютерные программы, моделирующие разбиения множества
14
Разбиения чисел
Алгоритмы и компьютерные программы, моделирующие разбиения множества. Диаграммы Ферреса. Тип разбиения числа.
15
Производящие функции
Теормы о производящих функциях. Числа Фибоначчи. Бинарные деревья и числа Каталана.
16
Рекуррентные последовательности и уравнения
Решение рекуррентных уравнений и систем. Задачи на нахождение пределов некоторых рекуррентных последовательностей с использованием ЭВМ
17
Принцип включения и исключения
Задачи и теоремы принципа включения и исключения.
18
Обратные задачи комбинаторики
Постановка задачи. Примеры решения обратных комбинаторных задач.
19
Конечные поля.
Конечные поля. Кольца и поля Zm. Теорема Гаусса. Теорема Эйлера – Гаусса. Алгебра и криптология
20
Уравнения и системы уравнений над Zm.
Уравнения и системы уравнений над Zm. Решение уравнений и систем уравнений над Zm на ЭВМ. Позиционные и непозиционные системы счисления.
21
Цепные дроби.
Алгоритм Евклида и цепные дроби. Моделирование цепных дробей. Представления числа обыкновенной дробью с ограничением на знаменатель.
22
Алгоритм Евклида
Алгоритм Евклида и теорема Безу. Аддитивные цепочки и их применение. Быстрое умножение. Разложение на бесквадратные множители. Теорема Остроградского.
23
Рекурсия
Понятие рекурсии. Рекурсивные программы: факториал, «Ханойские башни», генерирование перестановок и сочетаний.
Примерный перечень вопросов к зачету.
Понятие множества. Кортеж. Декартово произведение множеств.
Мощность множества. Конечные и бесконечные множества.
Операции и функции над множествами. Решение уравнений на нахождение неизвестного множества.
Моделирование подмножеств множества..
Числа комбинаторики. Моделирование сочетаний множества
Группы и подгруппы. Теорема Лагранжа. Теоремы Ферма и Эйлера
Симметрическая группа. Теорема Кэли.
Моделирование перестановок. Кольцо и поле
Решение задач на нахождение функция и размещения с помощью ЭВМ
Различные алгоритмы моделирования перестановок. Разложение на циклы. Тип перестановки.
Различные компьютерные программы, моделирующие перестановки, сравнение их по сложности. Программы для определения четности и типа перестановки.
Алгоритмы и компьютерные программы, моделирующие подмножества и множества с повторениями
Алгоритмы и компьютерные программы, моделирующие k-элементные подмножества
Алгоритмы, моделирующие разбиения множества. Тип разбиения множества.
Свойства и теоремы для чисел Стирлинга. Число сюръективных отображений. Числа Белла.
Алгоритмы и компьютерные программы, моделирующие разбиения множества
Алгоритмы и компьютерные программы, моделирующие разбиения множества.
Диаграммы Ферреса. Тип разбиения числа.
Теормы о производящих функциях.
Числа Фибоначчи.
Бинарные деревья и числа Каталана.
Решение рекуррентных уравнений и систем.
Задачи на нахождение пределов некоторых рекуррентных последовательностей с использованием ЭВМ.
Задачи и теоремы принципа включения и исключения.
Примеры решения обратных комбинаторных задач.
Конечные поля. Кольца и поля Zm. Теорема Гаусса. Теорема Эйлера – Гаусса.
Уравнения и системы уравнений над Zm.
Решение уравнений и систем уравнений над Zm на ЭВМ.
Позиционные и непозиционные системы счисления.
Алгоритм Евклида и цепные дроби.
Моделирование цепных дробей.
Представления числа обыкновенной дробью с ограничением на знаменатель.
Алгоритм Евклида и теорема Безу.
Аддитивные цепочки и их применение. Быстрое умножение. Разложение на бесквадратные множители. Теорема Остроградского.
Понятие рекурсии. Рекурсивные программы: факториал.
Рекурсивные программы: «Ханойские башни», генерирование перестановок и сочетаний.
Учебно-методическое и информационное обеспечение дисциплины
а) основная литература:
Белоусов А.И., Ткачев С.Б., Дискретная математика, М., Изд.МГТУ им.Н.Э.Баумана, 2006
Гашков С.Б., Современная элементарная алгебра, М., Изд. МЦНМО, 2006
Дэвенпорт Г., Высшая арифметика, М., Наука, 1965
б) дополнительная литература::
Акулич И.М. Математическое программирование в примерах и задачах. - М.: Высшая школа,1993.
Л. Аммерал. Машинная графика на персональных компьютерах. - М.: "Сол систем", 1992.
Гостко А.Б. Познакомьтесь с математическим моделированием. - М.: Знание, 1991.
Моисеев Н.Н. Математика ставит эксперимент. - М.: Наука, 1979. Николис Дж. Динамика иерархических систем: эволюционное представление. - М.: Мир, 1989.
Амелькин В. В., М., Дифференциальные уравнения в приложениях , М., Наука,1987
www.ronl.ru
