История Развития Комбинаторики Реферат
⚡ 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
История Развития Комбинаторики Реферат
Главная
Коллекция "Revolution"
Математика
История развития элементов комбинаторики
Понятие комбинаторики, история развития науки: древний период, средневековье, новое время. Современное развитие комбинаторики. Анализ элементов комбинаторики: размещение с повторением, без повторения, перестановки и сочетания. Примеры из комбинаторики.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
"История развития элементов комбинаторики"
1. Элементы комбинаторики и примеры решений
6. История развития элементов комбинаторики
Комбинаторика занимается различного вида соединениями, которые можно образовывать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии ещё во 2 в. до н.э. Индийцы умели вычислять числа, которые сейчас называют " сочетания ". В 17 веке Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские учёные изучали соединения в связи с применением их в поэтике , науке о структуре стиха и поэтических произведениях. Например, в связи с подсчётом возможных сочетаний ударных(долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в 12 веке, в книге "Теория и практика арифметики". Книга была написана французским автором в 1656 году. Автор посвятил сочетаниям и перестановкам целую главу.
1. Элементы комбинаторики и примеры решений
Комбинато м рика (Комбинаторный анализ) -- раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики -- алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например, в генетике, информатике, статистической физике).
Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.
Если из множества, содержащего m элементов, требуется выбрать какие-то k элементов, то возникает вопрос: сколькими способами это можно сделать и какие подмножества при этом получаются. Такие задачи называются комбинаторными, а соответствующий раздел математики - комбинаторикой.
Все формулы для подсчета числа решений в комбинаторных задачах опираются на правило произведения: если элемент X можно выбрать k способами, а элемент Y можно выбрать n способами, то пару XY можно составить kn способами.
Размещение с повторением . Из множества, содержащего m элементов, нужно выбрать k элементов, причем выбранный элемент, после того, как его взяли, вновь возвращается в исходное множество (то есть элементы в выбранном множестве могут повторяться). Пользуясь правилом произведения, получим, что каждый из k элементов может быть выбран m способами. Таким образом, общее число комбинаций равно .
Пример. Сколько различных четырехзначных чисел можно составить из цифр 2, 3, 5, 7.
Решение. Первой цифрой в числе может быть любая из четырех имеющихся. То же самое можно сказать и о последующих цифрах числа, поэтому общее число комбинаций:
Размещение без повторений . Из множества, содержащего mразличных элементов, надо выбрать упорядоченное подмножество изk элементов (k?m), то есть такое подмножество, в котором элементы располагаются в определенном порядке, и изменение порядка элементов изменяет подмножество. Кроме этого, элементы в выбранном подмножестве не повторяются. Требуется выяснить, сколько таких комбинаций существует. По правилу произведения получаем, что первый элемент можно выбрать m способами, второй элемент - (m-1) способом, и так далее, а элемент с номером k можно выбрать (m - k + 1) способами. Следовательно, число упорядоченных k-элементных подмножеств, взятых из множества, содержащего mэлементов равно m(m-1)(m-2)…(m-k+1). Такие подмножества называются размещениями из m элементов по k элементов, а их общее число можно выразить формулой
элемент комбинаторика пример развитие
Пример . Сколько различных четырехзначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6, при условии. Что цифры в числе не повторяются?
Решение. Общее число комбинаций равно числу размещений из 6 элементов по 4:
Перестановки. Пусть множество содержит m различных элементов. Рассмотрим все возможные варианты перестановок элементов этого множества. Получаемые при этом упорядоченные множества отличаются друг от друга только порядком входящих в них элементов. Такие упорядоченные множества называются перестановками. Число перестановок из m элементов равно:
Пример. Сколько различных четырехзначных чисел можно составить из цифр 2, 3, 5. 7, если цифры в числе не повторяются?
Решение. Количество чисел равно числу перестановок из четырех элементов:
Сочетания. Пусть из множества, содержащего m различных элементов, требуется выбрать подмножество, содержащее kразличных элементов (k--Ј m). Получаемые при этом подмножества не упорядочены.
Такие неупорядоченные подмножества называются сочетаниями. Число сочетаний из m элементов по k элементов вычисляется по формуле:
Пример. В группе 10 студентов. Сколькими способами можно выбрать из этой группы троих студентов для участия в конференции?
Решение. Число способов равно числу сочетаний из 10 элементов по 3 элемента:
Комбинаторные мотивы можно заметить в символике китайской «Книги Перемен» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо [1] . Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты.
Классическая задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н. э.). [2] . Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона [2] . Во II веке до н. э. индийцы знали, что сумма всех биномиальных коэффициентов степени n равна .
Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло. Хрисипп (III век до н. э.) и Гиппарх (II век до н. э.) подсчитывали, сколько следствий можно получить из 10 аксиом; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха -- более 100000 [3] . Аристотель при изложении своей логики безошибочно перечислил все возможные типы трёхчленных силлогизмов. Аристоксен рассмотрел различные чередования длинных и коротких слогов в стихотворных размерах. [3] Какие-то комбинаторные правила пифагорейцы, вероятно, использовали при построении своей теории чисел и нумерологии (совершенные числа, фигурные числа, пифагоровы тройки и др.).
В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями.
В Западной Европе ряд глубоких открытий в области комбинаторики сделали два еврейских исследователя, Авраам ибн Эзра (XII век) и Леви бен Гершом (он же Герсонид, XIV век). Ибн Эзра подсчитывал число размещений с перестановками в огласовках имени Бога [4] и обнаружил симметричность биномиальных коэффициентов, а Герсонид дал явные формулы для их подсчёта и применения в задачах вычисления числа размещений и сочетаний.
Несколько комбинаторных задач содержит «Книга абака» (Фибоначчи, XIII век). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.
Джероламо Кардано написал математическое исследование игры в кости, опубликованное посмертно. Теорией этой игры занимались также Тарталья и Галилей. В историю зарождавшейся теории вероятностей вошла переписка заядлого игрока шевалье де Мерэ сПьером Ферма и Блезом Паскалем, где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных игр, комбинаторные методы использовались (и продолжают использоваться) в криптографии -- как для разработки шифров, так и для их взлома.
В начале XX века начала развиваться комбинаторная геометрия: были доказаны теоремы Минковского -- Радона, Радона, Хелли, Юнга, Бляшке, а также строго доказана изопериметрическая теорема. На стыке топологии, анализа и комбинаторики были доказаны теоремы Борсука -- Улама и Люстерника -- Шнирельмана. Во второй четверти XX века были поставлены проблема Борсука и проблема Нелсона -- Эрдёша -- Хадвигера. В1940-х годах оформилась теория Рамсея. Отцом современной комбинаторики считается Пал Эрдёш, который ввёл в комбинаторику вероятностный анализ. Внимание к конечной математике и, в частности, к комбинаторике значительно повысилось со второй половины XX века, когда появились компьютеры. Сейчас это чрезвычайно содержательная и быстроразвивающаяся область математики.
Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Наряду с Лейбницем, он считается основоположником современной комбинаторики. Сам термин «комбинаторика» придумал Лейбниц, который в 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику [5] . Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.
В этот же период формируется терминология новой науки. Термин «сочетание» (combination) впервые встречается у Паскаля (1653, опубликован в 1665 году). Термин «перестановка» (permutation) употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал и термин «размещение» (arrangement).
После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр и Джеймс Стирлинг нашли формулы для аппроксимации факториала. [6]
Окончательно комбинаторика как самостоятельный раздел математики оформилась в трудах Эйлера. Он детально рассмотрел, например, следующие проблемы:
· задача о семи мостах, с которой началась теория графов;
· построение греко-латинских квадратов;
6. История развития элементов комбинаторики
C задачами, получишими название комбинаторных, оказывается, люди сталкивались в глубокой древности. Уже несколько тысячелетий назад в Древнем Китае увлеклись составлением магических квадратов, в которых заданные числа располагались так, что их сумма по всем горизонталям, вертикалям и главными диагоналям была одной и той же. В Древней Греции подсчитывали число различных комбинаций длинных и коротких слов в стихотворных размерах, занимались теорией фигурных чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата и т.д.
Первым рассматривал комбинаторику, как самостоятельную ветвь науки всемирно известный немецкий учёный Готфирд Вильгельм Лейбниц. В 1666 году Лейбниц опубликовал “Рассуждения о комбинаторном искусстве”. В своём сочинении учёный, вводя специальные символы, термины, находит все k-сочетания из n элементов ,выводит свойства сочетаний, строит таблицы сочетаний, после чего рассуждает о приложениях комбинаторики к логике, арифметике, о проблемах стихосложения и др. Мечтой Лейбница, оставшейся неосуществлённой, осталось построение общей комбинаторной теории.
В 18 веке к решению комбинаторных задач обращались выдающиеся математики. Замечательные достижения в области комбинаторики принадлежат Леонарду Эйлеру. Он рассматривал задачи о разбиении чисел, о циклических расстановках, о построении магических и латинских квадратов. В 1713 году было опубликовано сочинение Бернулли в котором с достаточно полной силой были изложены известные к тому времени комбинаторные факты. Комбинаторными задачами интересовались математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей. Теперь комбинаторика находит применение во многих областях науки: в биологии, где она применяется для изучения состава белков и ДНК, в химии, механике сложных сооружений и т.д. Комбинаторные задачи в физике, химии, биологии и других наук, которые не поддавались ранее решению из-за трудоёмкости вычислений, стали успешно решаться.
1. Виленкин Н.Я. Популярная комбинаторика. -- М.: Наука, 1975. -- 208 с.
2. История математики. С древнейших времен до начала Нового времени // История математики / Под редакцией А.П. Юшкевича, в трёх томах. -- М.: Наука, 1970. -- Т. I.
3. Математика XVII столетия // История математики / Под редакцией А. П. Юшкевича, в трёх томах. -- М.: Наука, 1970. -- Т. II.
4. Математика XVIII столетия // История математики / Под редакцией А. П. Юшкевича, в трёх томах. -- М.: Наука, 1972. -- Т. III.
5. Рыбников К. А. Комбинаторный анализ. Очерки истории. -- М.: Изд. мехмата МГУ, 1996. -- 124 с.
6. Рыбников К. А. История математики в двух томах. -- М.: Издательство МГУ, 1960-1963.
Определение понятий множества и факториала. Условия равности двух кортежей. Содержание основных разделов комбинаторики - перечислительного, экстремального и вероятностного. Сущность теории Рамсея. Сведения о размещении, перестановке и сочетании элементов. реферат [509,5 K], добавлен 21.02.2012
Возникновение комбинаторики как раздела математики. Исследование на практических примерах особенностей чисел размещений с повторениями и без них. Анализ задач, решение которых опирается на правила комбинаторики и относящиеся к ней вычислительные формулы. курсовая работа [175,3 K], добавлен 05.01.2018
Решение задач по факультативному курсу комбинаторики, подготовка сообщений и докладов. Комбинаторика как ветвь математики, изучающая комбинации и перестановки предметов. Основные правила суммы и правило произведения. Поиск числа сочетаний с повторениями. дипломная работа [508,5 K], добавлен 26.01.2011
Знакомство с основными понятиями и формулами комбинаторики как науки. Методы решения комбинаторных задач. Размещение и сочетание элементов, правила их перестановки. Характеристики теории вероятности, ее классическое определение, свойства и теоремы. презентация [1,3 M], добавлен 21.01.2014
Основные принципы и формулы классической комбинаторики. Использование методов комбинаторики в теории вероятностей. Формулы числа перестановок, сочетаний, размещений. Формула бинома Ньютона. Свойства биномиальных коэффициентов. Решение комбинаторных задач. учебное пособие [659,6 K], добавлен 07.05.2012
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .
© 2000 — 2020, ООО «Олбест»
Все права защищены
История развития элементов комбинаторики
История комбинаторики | Образовательная социальная сеть
Реферат : Комбинаторика - BestReferat.ru
История комбинаторики
Реферат по математике курсанта 1 курса по теме: История ...
Один День Первобытного Человека Мини Сочинение
Реферат Приборы Контроля Ми 8т
Прикладная Магистерская Диссертация
Психология Дружбы Реферат По Психологии
Аудит Розрахунків З Дебіторами Та Кредиторами Реферат