Комбинаторная задача с решением 5 класс: Простейшие комбинаторные задачи. 5-й класс

Содержание

Комбинаторные задачи (5 класс)

Этапы урока

Задачи этапа

Визуальный ряд

Деятельность учителя

Деятельность учащихся

Формируемые УУД

Организационный

Собрать домашнее задание, настроить на урок

Слайд на доске:

«тяжело в учении легко в бою»

Прошу теперь сдать на проверку тетради с домашней работой. Напоминаю, что мы сегодня приступаем к изучению новой темы.

Дежурные проходят по классу собирают тетради.

Саморегуляция, прогнозирование и оценка

Актуализации теоретических знаний

Определить цель урока

На доске: дата и название темы: «Комбинаторные задачи»

Ребята, сегодня мы совершим увлекательное путешествие в мир «Комбинаторики»

Мысленно задают вопрос: «а что это такое»

Целеполагание, предметная рефлексия.

Объяснения нового материа

ла

Первичное знакомство с основными понятиями,

методами, способами

решения

комбинаторных задач

Слайд на доске: Слово «комбинаторика» произошло от латинского слова COMBINARE, что означает «соединять», «сочетать»

Учитель задаёт вопрос как вы думаете что означает слово «комбинаторика»?

Учитель делает паузу, слушает ответы потом говорит определение.

Слово «комбинаторика» произошло от латинского слова COMBINARE, что означает «соединять», «сочетать»

Дети отвечают, выдвигая гипотезы

Внимательно слушают, читают определение на раздаточных листках

Выдвижение и проверка гипотез.

Слайд на доске

Чтобы запереть чемодан с кодовым замком, состоящий из двух каких-либо цифр. Хозяин чемодана решил использовать только цифры 1, 2 и 3. Сколькими способами он может выбрать код?

Решить эту задачу можно с помощью древа возможных вариантов или перебора всех возможных вариантов

Внимательно слушают, смотрят слайд, думают, запоминают.

Смысловое чтение.

Слайд на доске:

Решение древом возможных

Вариантов

ДЕРЕВО ВОЗМОЖНЫХ ВАРИАНТОВ

 Часто процесс перебора удобно осуществлять путем построения специальной схемы — так называемого дерева возможных вариантов

  1. изобразите корень дерева, для этого поставьте знак *.

  2. Чтобы выбрать первую цифру кода, у нас есть три варианта: 1; 2; 3. Поэтому от корня дерева проведите три ветви и на их концах поставите цифры 1; 2; 3.

  3. Для выбора второй цифры есть те же три варианта. Проводим «веточки»

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

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Анализ объекта.

Выбор оснований критериев для сравнения, сериации, классификации объектов.

Создание и преобразование модели и схемы для решения задач в зависимости от конкретных условий.

Слайд на доске:

Решение перебором

Подходящие коды - это двузначные числа, которые можно составить из цифр

1, 2, 3. Будем выписывать все такие цифры в порядке возрастания. Такой способ перебора позволит нам не пропустить никакой из кодов и в то же время не повторить ни один из них.

С начало запишем в порядке возрастания все коды, начинающиеся с цифры 1: 11, 12, 13. Затем запишем в порядке возрастания коды, начинающиеся с цифры 2: 21, 22, 23.

Затем запишем в порядке возрастания коды, начинающиеся с цифры 3: 31, 32, 33

Таким образом, имеется 9 способов выбора

кода: 11, 12, 13, 21, 22, 23, 31, 32, 33.

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Анализ объекта.

Выбор оснований критериев для сравнения, сериации, классификации объектов.

Создание и преобразование модели и схемы для решения задач в зависимости от конкретных условий.

Закрепления новых знаний

Показать практическое применение теоретических знаний

через их применение в решении практических задач

Слайд на доске с условием задачи №1

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

Слайд на доске с решением

На слайде изображено дерево возможных вариантов

  1. первый уровень «НАПИТКИ»

два варианта: ЧАЙ, СОК.

  1. второй уровень три варианта: ПИЦЦА, ПЛЮШКА, БУТЕРБРОД.

Итого шесть ВАРИАНТОВ завтрака:

ЧАЙ+ПИЦЦА, ЧАЙ+ПЛЮШКА, ЧАЙ+БУТЕРБРОД, СОК+ПИЦЦА, СОК+ПЛЮШКА, СОК+БУТЕРБРОД.

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Знакомство с профессиями.

Анализ объекта.

Выбор оснований критериев для сравнения, сериации, классификации объектов.

Создание и преобразование модели и схемы для решения задач в зависимости от конкретных условий.

Слайд на доске с условием задачи №2

Из страны «Математика» в страну «Литература» ведут три дороги, а из страны «Литература» в страну «Физкультура» - четыре дороги. Сколькими способами можно попасть из страны «Математика» в

Страну «Физкультура» через страну «Литература»?

Слайд на доске с решением

Рисунок поможет нам решить эту задачу.

Переберём все «ПУТИ»

Обозначим дороги идущие из страны «МАТЕМАТИКА» так: М1, М2, М3,

а из «ЛИТЕРАТУРА» Л1, Л2, Л3,Л4.

Переберём М1+Л1, М1+Л2, М1+Л3,М1+Л4, М2+Л1, М2+Л2, М2+Л3,

М2+Л4, М3+Л1, М3+Л2, М3+Л3, М3+Л4

Натолкнуть

Детей на мысль о перемножении Количества дорог

А можно взять и перемножить количество дорог 3*4 =12

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Слайд на доске с условием задачи №3

Шифр сейфа составляют из букв и цифр, причём на первом месте ставится буква (например А7). Сколько различных вариантов шифра можно составить, используя буквы А, В, С и цифры 3, 7, 9?

Слайд на доске с решением

1) на слайде изображён корень дерева, в виде знака *.

2)Чтобы выбрать букву кода, у нас есть три варианта: А; B; C. Поэтому от корня дерева проведены три ветви и на их концах поставлены буквы: А; B; C .

3)Для выбора цифры есть те же три варианта. Проводим «веточки»

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

А3, А7, А9, В3, В7, В9, С3, С7, С9

Или Всего 3*3=9 вариантов

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Слайд на доске с условием задачи №4

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

Слайд на доске с решением

Первый способ: обозначим цвета полосок первыми буквами названий цветов

Б – белый, К – красный, С – синий.

Решим перебором:

БСК, БКС, СБК, СКБ, КБС, КСБ

Всего шесть вариантов.

Второй способ:

Берем карандаши и рисуем флаги

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Слайд на доске с условием задачи №5

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

Слайд на доске с решением

Второй способ решения

Для наглядности раскрасим стулья разными цветами.

Зафиксируем красный стул вверху и, будем переставлять остальные три, получим шесть вариантов.

Эту же операцию проделаем с остальными цветами, получим 6*4=24 различных вариантов.

Второй способ:

На первый стул может сесть любой член семьи, т. е. 4 варианта; на второй – 3 человека так, как один член семьи уже сидит; на третий – 2 человека так, как

двое сидят; на четвёртый только один так, как три члена семьи уже сидят.

Итак, перемножим все варианты

4*3*2*1= 24

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Слайд на доске с условием задачи №6

Вася решил пойти на новогодний

карнавал в костюме мушкетёра. В ателье проката ему предложили на выбор: три вида брюк, два камзола, три шляпы. Сколько различных карнавальных костюмов можно составить из этих предметов?

Слайд на доске с решением

Обозначим: первую шапку Ш1, вторую – Ш2, третью – Ш3

1) на слайде изображён корень дерева, в виде знака *.

2) первый уровень трое брюк;

3) второй уровень два камзола;

4) третий уровень три шапки;

Всего 18 вариантов

Или просто перемножить «уровни»

3*2*3=18

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Слайд на доске с условием задачи №7

При встрече 7 гномов обменялись рукопожатиями. Сколько всего было сделано рукопожатий?

Семь гномов решили обменяться фотографиями. Сколько нужно фотографий?

Слайд на доске с решением: а)

Слайд на доске с решением: б)

Эти две задачи очень похожи, но всё-таки они разные

При решении таких задач лучше использовать таблицу.

1)Нарисуем таблицу 8*8, первая строка и первый столбец это гномы.

2)Вычеркнем диагональ таблицы так, как гном сам с собою не может поздороваться.

3) Ячейки это кто с кем поздоровался.

4) Нижняя часть таблицы повторяет верхнюю.

Первый гном поздоровался со вторым = второй гном поздоровался с первым.

Всего 21 рукопожатие.

Задача б) отличается от а) тем, что нужно

учитывать нижнюю часть таблицы так, как

первый гном подарил фото второму, НЕРАВНО второй гном подарил фото первому.

Всего 42 фото.

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Знакомятся с моделями и схемами для решения задач в зависимости от конкретных условий.

Систематизации знаний

Систематизировать методы решений комбинаторных задач.

Слайды на доске

И следующий слайд,

Слайды решений задачи №7

Внимательно слушают, смотрят слайды, думают, анализируют, классифицируют, запоминают.

Систематизация знаний по трём

методам.

Усвоения новых знаний

Дать определе-

ние комбинаторных задачач.

Слайд на доске

Отвечают на вопрос

Установление аналогий.

Умение классифициро

вать.

Определить три метода решения задач этого типа.

Следующий слайд;

Слайд решения задачи №7

Отвечают на вопрос

Умение классифициро

вать.

Выбор наиболее эффективных способов решения задач в зависимости от конкретных решений

Сделать вывод о многовариантном решении комбинаторных задач

Слайд

Отвечают на вопрос

Создавать модели и схемы для решения задач в зависимости от конкретных условий

Рефлек

сии

Провести самостоятельную работу в группах, в малых группах, индиви- дуально.

На парте у каждого лист (формата А4) с семью задачами (приложение№1)

Слайд с ответами

Таблица на доске (ответы команд)

Коман-

да №1

Коман-

да №2

1

2

3

4

5

6

7 а

7 б

Выполняют самостоятельную работу в коллективе, в парах, индивидуально.

Сочетание индивидуальной самостоятельной работы и сотрудничество в коллективе

Объяснения домашнего задания

Обеспече

ние понимания детьми цели, содержания и способов выполне

ния домашнего задания.

Саморегуля

ция, развитие самосознания, ответствен

ного отношения

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

Из страны «Математика» в страну «Литература» ведут четыре дороги, а из страны «Литература» в страну «Физкультура» - пять дорог. Сколькими способами можно попасть из страны «Математика» в

страну «Физкультура» через страну «Литература»?

Шифр сейфа составляют из букв и цифр, причём на первом месте ставится буква (например А7). Сколько различных вариантов шифра можно составить, используя буквы А, M, F и цифры 1, 4, 6, 9?

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

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

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

При встрече 4 гнома обменялись рукопожатиями. Сколько всего было сделано рукопожатий?

Пять гномов решили обменяться фотографиями. Сколько нужно фотографий?

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

Из страны «Математика» в страну «Литература» ведут три дороги, а из страны «Литература» в страну «Физкультура» - четыре дороги. Сколькими способами можно попасть из страны «Математика» в

страну «Физкультура» через страну «Литература»?

Шифр сейфа составляют из букв и цифр, причём на первом месте ставится буква (например А7). Сколько различных вариантов шифра можно составить, используя буквы А, В, С и цифры 3, 7, 9?

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

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

На первый стул может сесть любой из четырёх, на второй – только трое, на третий – двое, на четвёртый – один. 4*3*2*1=24 разных вариантов

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

карнавал в костюме мушкетёра. В ателье проката ему предложили на выбор: три вида брюк, два камзола, три шляпы. Сколько различных карнавальных костюмов можно составить из этих предметов?

При встрече 7 гномов обменялись рукопожатиями. Сколько всего было сделано рукопожатий?

Семь гномов решили обменяться фотографиями. Сколько нужно фотографий?

Конспект урока "Решение комбинаторных задач" (5 класс)

АНО ПО “ШКОЛА КЛАССИЧЕСКОГО ТАНЦА”

«Решение комбинаторных задач»

в 5 классе

Подготовила: преподаватель математики

Иофик Татьяна Александровна

г. Москва

Дата: 01.10.2018 г.

Тип урока: урок изучения и первичного закрепления новых знаний

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

Оборудование: компьютер, экран, проектор, презентация к уроку,

Задачи:

  1. Образовательные:

К концу урока учащиеся должны уметь:

  • выделять комбинаторные задачи из ряда предложенных задач;

  • решать простейшие комбинаторные задачи;

  • выработать умение применять математическую теорию в конкретных ситуациях.

  1. Воспитательные:

Способствовать:

  • формированию познавательного интереса к предмету; мировоззрения учащихся,

  • воспитанию чувства патриотизма; ответственности за качество и результат выполняемой работы.

  1. Развивающие:

Способствовать:

  • совершенствованию операций умственной деятельности: анализ, синтез, классификация, способность наблюдать и делать выводы, выделять существенные признаки.

ХОД УРОКА

I. Организационный момент

Проверка готовности учащихся к уроку.

II. Актуализация знаний.

(слайд 1)

- В старинных русских сказаниях повествуется, как богатырь, доехав до распутья, читает на камне: “Прямо поедешь – голову сложишь, направо поедешь – коня потеряешь, налево поедешь – меча лишишься”. Ребята, с какой проблемой сталкивается добрый молодец на перепутье? (с проблемой выбора дальнейшего пути движения)

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

Приведите примеры, когда нам приходится делать выбор? (слайд 2)

Оказывается, существует целый раздел математики, который занят поисками ответов на эти вопросы. А вот называется он - комбинаторика. (слайд 3)

- А как вы понимаете, что такое комбинаторика? (ответы учащихся)

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

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

II. Изучение нового материала.

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

- И еще сегодня в очередной раз убедимся, что наш мир полон математики, и продолжим исследование на предмет выявления математики вокруг нас.

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

Дети рисуют флаги, используя белый, синий и красный цвета.

Итак, сколько вариантов у вас получилось? (Считаем)

- Обычный вопрос в комбинаторных задачах – это «Сколькими способами…?» или «Сколько вариантов…?»

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

КБС КСБ

БСК БКС

СБК СКБ

Ответ: 6 вариантов.

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

Решение

Флаг

Варианты БСК, БКС, СБК, СКБ, КБС, КСБ. Этот метод называется “Дерево возможных вариантов”.

Ответ: 6 вариантов.

Вопрос, ответ на который должны знать все: “ Какой из представленных вариантов флагов – государственный флаг РФ?” Что означает каждый цвет нашего флага?

Белый цвет означает мир, чистоту, непорочность, совершенство; синий - цвет

веры и верности, постоянства; красный цвет символизирует энергию, силу, кровь,

пролитую за Отечество. (слайд 5)

Оказывается, не только флаг России имеет эти три цвета. Есть государства, флаги которых, имеют такие же цвета.

КБС – Люксембург и Нидерланды.

Найдем правило решения таких задач путем логического рассуждения.

Разберем на примере цветных полосок. Возьмем белую полоску – её можно переставить 3 раза, возьмем синюю полоску – её можно переставить только 2 раза, т.к. одно из мест уже занято белой, возьмем красную полоску – её можно положить только 1 раз.

ИТОГО: 3 х 2 х 1=6

Правило умножения: если первый элемент в комбинации можно выбрать а способами, после чего второй элемент – b способами, то общее число комбинаций будет равно а х b.

Физкультминутка для глаз.

Нарисовать глазами квадрат, круг, треугольник, овал, ромб по часовой стрелке, а затем – против часовой стрелки. (Фигуры можно нарисовать на доске)

Откроем учебник на стр. 43 и рассмотрим задачу 1 с дополнением первым после неё. Обратить внимание на логику перебора. Решить задачи №№ 137, 138, 141 методом перебора.

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

В помощь тому, кто составляет расписание, решим задачу:

Задача №2. В 5 классе во вторник 5 уроков: физкультура, русский язык, литература, история и математика. Сколько можно составить вариантов расписания на день, зная точно, что математика – первый урок?

Фронтальная работа

- Как бы вы предложили решить эту задачу? (ответы детей)

- Предлагаю вам закодировать названия предметов их начальной буквой: Ф – физкультура, Р – русский язык, Л – литература, И – история, М – математика.

- С какого урока мы начнем составлять расписание? (с математики)

Какие способы решения этой задачи вы знаете? (перебор, дерево, произведение). А какой вариант здесь самый удобный?

Сколько возможных вариантов расписания уроков у вас получилось? Подсчитайте. (24 варианта)

-А если бы в задаче не было условия, что математика – первый урок, что бы изменилось? (ответ, вариантов расписания было бы намного больше.- Сколько?- 120)

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

IV. Закрепление изученного

- Настало время перекусить. Мы идем в школьную столовую

Задача№3. Сколько различных завтраков, состоящих из 1 напитка и 1 вида выпечки, можно составить из чая (ч), кофе (к), булочки (б), печенья (п) и вафель (в)?

Заполните схему дерева возможных вариантов в соответствии с условием задачи.

Напитки

Выпечка

- Обменяйтесь тетрадями с соседом по парте. Проверьте друг друга. Сколько завтраков у вас должно получиться? (6 завтраков) - Если ваш сосед выполнил задание верно, поставьте «плюс», иначе – «минус». Верните друг другу тетради.

Работа по учебнику.

Разбор решения задачи № 2, стр. 43.

Решение задач из учебника №№ 145, 146 методом «дерева возможных вариантов».

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

Проказница Мартышка,

Осел,

Козел,

Да косолапый Мишка

Затеяли сыграть в ...

Ударили в смычки, дерут, а толку нет.

………………..

«Стой, братцы, стой!» - кричит Мартышка -

Погодите.

Как музыке идти? Ведь Вы не так сидите!

- Из какого произведения данный отрывок и кто автор? (басня Ивана Андреевича Крылова «Квартет») (слайд 6)

- Какую задачу можно решить в этой басне? Каким способом? (ответы детей). Можно дать задание первому варианту (и первому ученику у доски) записать решение методом перебора, второму – методом «дерева вариантов», третьему – способом умножения.

V. Подведение итогов

- С чем вы познакомились сегодня на уроке? (с комбинаторными задачами)

- Какими способами вы научились решать такие задачи? (перебор, дерево, умножение)

- Итак, ученику приходится встречаться с математикой, практически, постоянно. В частности, вы просчитываете различные комбинации – когда? (обсуждение с детьми):

  • когда выбираете меню в столовой,

  • формулируете свой ответ на уроках,

  • составляете график дежурства по классу,

  • планируете, как провести свои выходные или каникулы и так далее.

VI. Домашнее задание

- Запишите в тетрадь домашнее задание:

1. №№ 139, 140 из учебника.

2. Шестеро детей выбирает роли согласно известной считалке «На златом крыльце сидели…» (слайд 7). Сколько вариантов выбора роли у каждого ребенка и сколько вариантов распределения ролей существует?

3. Придумать свою комбинаторную задачу практического характера.

VII. Рефлексия

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

И С П О Л Ь З О В А Н Н Ы Е Р Е С У Р С Ы :

Математика. 5 класс. Дорофеев Г.В., Шарыгин И.Ф., Суворова С.Б. и др. М., «Просвещение», 2017.

https://clck.ru/EZjcE

https://yandex.ru/collections/card/5b1bcde3f03d153c20f867cd/

http://ru.fanpop.com/clubs/homer-simpson/images/10030107/title/homer-wallpaper

http://fb2.booksgid.com/content/16/luchano-malmuzi-neandertalskiy-malchik-v-shkole-i-doma/3.html

http://blog.geneticslab.emory.edu/hubfs/Exome-1.jpg?t=1517074552427

https://ru-static.z-dn.net/files/d65/b5b697993adf15b4b23c95761ef7535d.jpg

https://cf.ppt-online.org/files/slide/y/YVqXDeSM7OZdB3Qvknr4PtpzxwNI8yu1EoCcGj/slide-14.jpg

http://www.speakrus.ru/articles/babycnt.htm#golden1

Методы решения комбинаторных задач - Сайт учителя математики Кобец Анны Викторовны - Сайт учителя математики Кобец Анны Викторовны

Методы решения комбинаторных задач

Перебор возможных вариантов

Простые задачи решают обыкновенным полным перебором возможных вариантов без составления различных таблиц и схем.

Задача 1.
Какие двузначные числа можно составить из цифр 1, 2, 3, 4, 5?

Ответ: 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55.

Задача 2.
В финальном забеге на 100 м участвуют Иванов, Громов и Орлов. Назовите возможные варианты распределения призовых мест.

Ответ:
Вариант1: 1) Иванов, 2) Громов, 3) Орлов.
Вариант2: 1) Иванов, 2) Орлов, 3) Громов.
Вариант3: 1) Орлов, 2) Иванов, 3) Громов.
Вариант4: 1) Орлов, 2) Громов, 3) Иванов.
Вариант5: 1) Громов, 2) Орлов, 3) Иванов.
Вариант6: 1) Громов, 2) Иванов, 3) Орлов.

Задача 3.
В кружок бального танца записались Петя, Коля, Витя, Олег, Таня, Оля, Наташа, Света. Какие танцевальные пары девочки и мальчика могут образоваться?

Ответ:
1) Таня - Петя, 2) Таня - Коля, 3) Таня - Витя, 4) Таня - Олег, 5) Оля - Петя, 6) Оля - Коля, 7) Оля - Витя, 8) Оля - Олег, 9) Наташа - Петя, 10) Наташа - Коля, 11) Наташа - Витя, 12) Наташа - Олег, 13) Света - Петя, 14) Света - Коля, 15) Света - Витя, 16) Света - Олег.

Дерево возможных вариантов

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

Задача 4.
Какие трехзначные числа можно составить из цифр 0, 2, 4?

Решение. Построим дерево возможных вариантов, учитывая, что 0 не может быть первой цифрой в числе.
 

Ответ: 200, 202, 204, 220, 222, 224, 240, 242, 244, 400, 402, 404, 420, 422, 424, 440, 442, 444.

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

Решение. Построим дерево возможных вариантов, обозначив путешествие на поезде П, на автобусе - А, на байдарках - Б, велосипедах - В, пешком - Х, на канатной дороге - К.

 

Ответ: На рисунке перечислены все 12 возможных вариантов путешествия школьных туристов.

Задача 6.
Запишите все возможные варианты расписания пяти уроков на день из предметов: математика, русский язык, история, английский язык, физкультура, причем математика должна быть вторым уроком.

Решение. Построим дерево возможных вариантов, обозначив М - математика, Р - русский язык, И - история, А - английский язык, Ф - физкультура.

 

Ответ: Всего 24 возможных варианта:

Р
М
И
А
Ф

Р
М
И
Ф
А

Р
М
А
И
Ф

Р
М
А
Ф
И

Р
М
Ф
И
А

Р
М
Ф
А
И

И
М
Р
А
Ф

И
М
Р
Ф
А

И
М
А
Р
Ф

И
М
А
Ф
Р

И
М
Ф
Р
А

И
М
Ф
А
Р

А
М
Р
И
Ф

А
М
Р
Ф
И

А
М
И
Р
Ф

А
М
И
Ф
Р

А
М
Ф
Р
И

А
М
Ф
И
Р

Ф
М
Р
И
А

Ф
М
Р
А
И

Ф
М
И
Р
А

Ф
М
И
А
Р

Ф
М
А
Р
И

Ф
М
А
И
Р

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

Решение. Построим дерево возможных вариантов, обозначив Б - брюки, Д - джинсы, С - серая рубашка, Г - голубая рубашка, З - зеленая рубашка, Р - рубашка в клетку, Т - туфли, К - кроссовки.

 

Ответ: а) 16 дней; б) 8 дней; в) 2 дня.

Составление таблиц

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

Задача 8.
Сколько нечетных двузначных чисел можно составить из цифр 1, 3, 4, 6, 7, 8, 9?

Решение. Составим таблицу: слева первый столбец - первые цифры искомых чисел, вверху первая строка - вторые цифры.

 

Ответ: 28.

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

Решение. Составим таблицу: слева первый столбец - имена девочек, вверху первая строка - имена мальчиков.

 

Ответ: Все возможные варианты перечисляются в строках и столбцах таблицы.

Правило умножения

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

Задача 10.
В футбольном турнире участвуют несколько команд. Оказалось, что все они для трусов и футболок использовали белый, красный, синий и зеленый цвета, причем были представлены все возможные варианты. Сколько команд участвовали в турнире?

Решение.
Трусы могут быть белого, красного, синего или зеленого цвета, т.е. существует 4 варианта. Каждый из этих вариантов имеет 4 варианта цвета майки.

4 х 4 = 16.

Ответ: 16 команд.

Задача 11.
6 учеников сдают зачет по математатике. Сколькими способами их можно расположить в списке?

Решение.
Первым в списке может оказаться любой из 6 учеников,
вторым в списке может быть любой из оставшихся 5 учеников,
третьим - любой из оставшихся 4 учеников,
четвертым - любой из оставшихся 3 учеников,
пятым - любой из оставшихся 2 учеников,
шестым - последний 1 ученик.

6 х 5 х 4 х 3 х 2 х 1 = 720.

Ответ: 720 способами.

Задача 12.
Сколько четных двузначных чисел можно составить из цифр 0, 2, 3, 4, 6, 7?

Решение.
Первой в двузначном числе может быть 5 цифр (цифра 0 не может быть первой в числе), второй в двузначном числе может быть 4 цифры (0, 2, 4, 6, т.к. число должно быть четным).
5 х 4 = 20.

Ответ: 20 чисел.

Презентация по математике "Комбинаторные задачи 5 класс"

Презентация на тему: Комбинаторные задачи 5 класс

Скачать эту презентацию

Скачать эту презентацию

№ слайда 1 Описание слайда: № слайда 2 Описание слайда:

Рассмотреть решение комбинаторных задач, которые включены в учебник В. Я. Виленкина « Математика», 5 класс, расширить знания .

№ слайда 3 Описание слайда:

Что такое комбинаторика? В науке и практике часто встречаются задачи, решая которые приходится составлять различные комбинации из конечного числа элементов и подсчитывать число комбинаций. Такие задачи получили название комбинаторных задач, а раздел математики, в котором рассматриваются подобные задачи,называется комбинаторикой. « Комбинаторика»( лат. «combinare», соединять, сочетать)

№ слайда 4 Описание слайда:

Займёмся делом! Задача 11. Запишите все трёхзначные числа, для записи которых употребляются только цифры 1,2. Решение В записи числа на первом месте ( в разряде сотен) может стоять цифра 1 или цифра 2: 1 2

№ слайда 5 Описание слайда:

Рассуждаем далее На втором месте ( в разряде десятков) в каждом случае также одна из двух цифр 1 или 2. 1 2 1 2 1 2

№ слайда 6 Описание слайда:

Рассуждаем далее На третьем месте ( в разряде единиц) в каждом из полученных случаев можно записать либо 1, либо 2: 1 1 2 1 2 1 2 2 1 2 1 2 1 2

№ слайда 7 Описание слайда:

Вывод: В итоге мы видим, что получилось восемь чисел: 111,112,121,122,211,212,221,222 Задача12 . Запишите все трёхзначные числа, для записи которых употребляются числа 0,7. 7 7 о 0 7 7 0 Вывод: получили 4 числа:770, 777, 707,700

№ слайда 8 Описание слайда:

Задача №96 Решение. Президентом фирмы можно избрать одного из 5 человек. После того как президент избран, вице- президентом можно выбрать любого из четырёх оставшихся членов правления. 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 Значит выбрать президента можно пятью способами, и для каждого выбранного президента четырьмя способами можно выбрать вице- президента. Следовательно , общее число способов выбрать президента и вице- президента фирмы равно 5*4=20

№ слайда 9 Описание слайда:

Задача№228 Решение Первой цифрой может быть любая из четырёх цифр,Второй- любая из трёх других,а третьей-любая из двух других. Получаем Первая Вторая Третья 684846 682826 482824 462624 Всего из данных цифр можно составить 4*3*2=24 числа 2 4 6 8 4 6 8 2 6 8 2 4 8 2 4 6

№ слайда 10 Описание слайда:

Можно заглянуть в будущее! Размещением из n элементов по k (k

№ слайда 11 Описание слайда:

Задача№283 О не может стоять на первом месте в числе. Значит первой цифрой будет одна из трёх оставшихся, на втором месте могут стоять цифры отличные от первой, т.к. цифры в записи не должны повторятся. Значит: 2 4 6 0 4 6 0 2 6 0 2 4 Значит общее количество чисел равно 3*3=9

№ слайда 12 Описание слайда:

Задача№323 О не может стоять на первом месте в числе. Значит на первом месте может стоять одна из трёх оставшихся цифр. На втором месте может стоять также одна из трёх цифр не совпадающая с первой. На третьем месте могут стоять две цифры не совпадающие ни с первой ,ни со второй. о второй циф 3 5 05 03 1 5 05 01 1 3 0 3 1 0 Общее количество трёхзначных чисел равно 3*3*2=18 1 3 5 0 3 5 0 1 5 0 1 3

№ слайда 13 Описание слайда:

Задача№356 На первом месте может стоять любая из пяти цифр, на втором месте может стоять любая из четырёх цифр , отличная от первой 3 5 7 9 1 5 7 9 1 3 7 9 1 3 5 9 1 3 5 7 1 3 5 7 9 Количество двузначных чисел равно 5*4=20

№ слайда 14 Описание слайда:

Задача№401 На первом месте не может стоять О. Значит на первом месте может стоять одна из двух оставшихся.На втором месте может стоять любая из трёх, на третьем месте также может стоять любая из трёх. 5 3 0 5 3 0 5 3 0 5 3 0 5 3 0 5 3 0 5 3 5 3 0 3 0 5 Всего чисел 2*3*3 =18

№ слайда 15 Описание слайда:

Задача №510 Соберём все варианты в такой таблице Метро Трамвай Автобус Автобус Троллейбус Метро Всего у Бориса есть 9 способов Метро автобус Трамвай автобус Автобус, автобус Метро, троллейбус Трамвай, троллейбус Автобус,троллейбус Метро, метро Трамвай, метро Автобус, метро

№ слайда 16 Описание слайда:

Рассмотрим ещё 2 задачи Задача №1 Сколько чётных двузначных чисел можно составить из цифр 0,1,2,4,5,9? Составим таблицу: слева от первого поместим первые цифры искомых чисел, а выше первой строки- вторые цифры этих чисел. Т.к. в двузначном числе на первом месте может стоять любая цифра, кроме О, то строки будут отмечены цифрами1,2,4,5,9. Значит, в нашей таблице будет пять строк. На втором месте в искомом числе должна стоять чётная цифра, значит, столбцы будут отмечены цифрами 0,2,4.

№ слайда 17 Описание слайда:

Составим таблицу 0 2 4 1 2 4 5 9 Возможных вариантов-15 10 12 14 20 22 24 40 42 44 50 52 54 90 92 94

№ слайда 18 Описание слайда: № слайда 19 Описание слайда:

Задача№2 На завтрак Вова может выбрать плюшку, бутерброд, пряник или кекс, а запить их он может кофе, соком, или кефиром. Из скольких вариантов завтрака Вова может выбирать? Соберём все варианты в такой таблице. плюшка бутерброт пряник кекс Кофе Сок кефир Кофе, плюшка Кофе, бутерброт Кофе , пряник Кофе,кекс Сок, плюшка Сок, бутерброт Сок,пряник Сок,кекс Кефир, плюшка Кефир, бутерброт Кефир, пряник Кефир, кекс

№ слайда 20 Описание слайда:

Ещё раз подтвердим правило умножения Выбор еды и напитка происходит независимо, то в каждой клетке будет стоять один из возможных вариантов завтрака и, наоборот, любой вариант завтрака будет записан в одной клетке. Значит 4*3=12. Приятного аппетита!

№ слайда 21 Описание слайда:

Дерево возможных вариантов Правило умножения для трёх, четырёх и т. д. испытаний можно объяснить ,с помощью геометрической модели, которую называют деревом возможных вариантов. Вы уже им пользовались в предыдущих задачах. Н.п в задачах №228, № 323. Дерево наглядно и позволяет всё учесть

№ слайда 22 Описание слайда:

Задача №694 (напомним) Семье, состоящей из бабушки, папы, мамы, дочери и сына подарили 5 разных чашек. Сколькими способами можно разделить чашки между членами семьи? Решение. У первого члена семьи( например, бабушка) есть 5 вариантов выбора, у второго члена(например, папа)-4 варианта, у третьего(мама)-3 варианта, у четвёртого(дочь)-2 варианта, у пятого(сын)-1 вариант. 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 1 4 5 1 5 4 5 1 4 5 4 2 4 5 1 2 5 1 2 4 5 1 4 1

№ слайда 23 Описание слайда:

Роскошное дерево вариантов! Правило умножения. Понятие факториала! Получили, что каждому выбору чашки бабушки соответствует 4 возможных выбора папы, т.е. всего5*4 способов. После того как папа выбрал чашку, у мамы есть 3 варианта выбора, у дочери-2, у сына-1, т.е. всего 3*2*1способов. Окончательно получаем, что для решения задачи надо найти произведение 5*4*3*2*1 или 1*2*3*4*5=5!(пять-факториал) Значит количество вариантов равно 5!=120 n!

№ слайда 24 Описание слайда:

Задача №807 Лена, Света, Маша, Катя и Наташа пришли к зубному врачу. Сколькими способами они могут встать в очередь? Рассуждаем. Предположим Лена встаёт в очередь там где ей захочется, у неё есть 5 вариантов, тогда у Светы остаётся встать в очередь 4 вариантами, у Маши-3 вариантами,у Кати-2 вариантами и у Наташи-1 вариантом. По правилу умножения получаем 5*4*3*2*1=5!=120 способов. Заглядывая в учебник 9 класса, мы выяснили, что в данной ситуации у нас получилось число перестановок из 5 элементов!

№ слайда 25 Описание слайда:

Понятие перестановки Перестановкой из n элементов называется каждое расположение этих элементов в определённом порядке. Когда Лена, Света, Катя, Маша, Наташа становились в очередь , они располагались в определённом порядке. Былоих5. Значит это перестановка из 5 злементов. Подсмотрим формулу. Вот она Pn =n! В нашем случае так и получилось P5=5!=120

№ слайда 26 Описание слайда:

Задача №835 Сколькими способами из 7 бусинок разных цветов можно составить ожерелье( с застёжкой)? Рассуждаем. Т.к. застёжка в ожерелье не меняет своё место, то число перестановок из 7 элементов, т.е. 7! 1*2*3*4*5*6*7= 720*7=5040 способов

№ слайда 27 Описание слайда:

Задача №922 На книжную полку ставят 6 разных книг. Сколькими способами эти книги можно разместить на полке? Рассуждаем. Положение 1-й книги будет определяться6 вариантами, положение второй книги-5 вариантами,3книги -4 вариантами, 4-й-соответственно-3вариантами,5-й-2 вариантами,6-й-1вариантом. Значит всего способов по правилу умножения6*5*4*3*2*1=6!=720 А можно по другому?. Да. Найдём число перестановок из 6 элементов т.е.P6 =6! =720

№ слайда 28 Описание слайда:

Задача № 1035 Кодовый замок имеет 6 кнопок. Чтобы его открыть, нужно нажать кнопки в определённой последовательности( набрать код). Сколько существует вариантов кода для этого замка Рассуждаем. Явно нам необходимо найти количество перестановок из 6 элементов.т.е P6 =6! =720

№ слайда 29 Описание слайда:

Задача №1071 К полднику в детском саду на четырёхместный стол поставили сок, молоко, какао и компот. Сколькими способами четверо детей могут выбрать себе один из напитков? Рассуждаем.Первый ребёнок имеет возможность выбрать любой стакан 4вариантами, второму остаётся выбор из 3 вариантов, третьему придётся выбирать из 2 вариантов, четвёртому остаётся выбор одного варианта. По правилу умножения -количество вариантов равно 4*3*2*1=4!=24 А можно по –другому? Да. Количество перестановок P4 =4! =24

№ слайда 30 Описание слайда:

Задача№1728 Сколькими способами 4 пассажира могут разместиться в четырёхместном купе? Рассуждаем. Первый пассажир может выбрать любое место из 4, второму остаётся выбирать из 3 вариантов, третьему из 2вариантов, ну а 4 пассажир займёт то место, которое останется. Значит количество способов 4*3*2*1=24, а по -другому P4 =4!=24 Счастливого пути!

№ слайда 31 Описание слайда:

Спасибо за внимание! Успехов в познании нового и интересного!

Мерзляк 5 класс — § 24. Комбинаторные задачи

Вопросы к параграфу

1. Какие задачи называют комбинаторными?

Комбинаторные задачи — это задачи, решение которых требует рассмотрения и подсчёта все возможных случаев (всех возможных комбинаций).

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

Дерево возможных вариантов.

Решаем устно

1. Одним слоем бумаги оклеили куб, длина ребра которого равна 3 дм. Сколько квадратных дециметров бумаги потребовалось на оклеивание куба?

Найдём площадь поверхности куба:

S = 6a² = 6 • 3² = 6 • 9 = 54 (дм²) — бумаги потребовалось для оклеивания куба.

Ответ: 54 дм².

2. Объём прямоугольного параллелепипеда равен 240 см³. Какая из следующих троек чисел может задавать измерения этого параллелепипеда:

1) 4 см, 6 см, 12 см

4 • 6 • 12 = 24 • 12 = 288 (см³) — нет, эти числа не могут быть измерениями данного прямоугольного параллелепипеда.

2) 5 см, 6 см, 8 см

5 • 6 • 8 = 30 •  8 = 240 (см³) — да, эти числа могут быть измерениями данного прямоугольного параллелепипеда.

3) 3 см, 5 см, 10 см

3 • 5 • 10 = 15 •  10 = 150 (см³) — нет, эти числа не могут быть измерениями данного прямоугольного параллелепипеда.

4) 10 см, 10 см, 24 см

10 • 10 • 24 = 100 • 24 = 2 400 (см³) — нет, эти числа не могут быть измерениями данного прямоугольного параллелепипеда.

Ответ: числа 5 см, 6 см и 8 см.

3. Сколько центнеров пшеницы можно засыпать в бункер, имеющий форму прямоугольного параллелепипеда, если его длина равна 8 м, ширина — 2 м, высота — 1 м, а масса 1 м³ зерна составляет 8 ц?

1) 8 • 2 • 1 = 16 (м²) — объём бункера.

2) 16 • 8 = 128 (ц) — пшеницы можно засыпать в бункер.

Ответ: 128 центнеров.

4. Что больше и на сколько:

1) квадрат суммы чисел 4 и 3 или сумма их квадратов

(4 + 3)² > 4² + 3²
7² > 16 + 9
49 > 25

2) разность квадратов чисел 10 и 8 или квадрат их разности

10² — 8² > (10 — 8)²
100² — 64² > 2²
36 > 4

3) разность кубов чисел 5 и 3 или куб их разности

5³ — 3³ > (5 — 3)³
125 — 27 > 2³
98 > 8

Упражнения

645. Запишите все двузначные числа, в записи которых используются только цифры 1, 2 и 3 (цифры могут повторяться).

Таких двузначных чисел всего 9:

  • 11, 12, 13
  • 22, 21, 23
  • 33, 31, 32

646. Запишите все двузначные числа, в записи которых используются только цифры 1, 2 и 0 (цифры могут повторяться).

Таких двузначных чисел всего 6:

647. У ослика Иа-Иа есть три надувных шарика: красный, зелёный и жёлтый. Он хочет подарить по одному шарику своим друзьям: Винни-Пуху, Пятачку и Кролику. Сколько у ослика Иа-Иа есть вариантов сделать подарки своим друзьям?

Решим задачу при помощи схемы «Дерево возможных вариантов».

Итак, у нас получилось шесть возможных вариантов:

Винни-Пуха

Пятачок

Кролик

Вариант 1

Зелёный Красный Жёлтый

Вариант 2

Зелёный Жёлтый Красный

Вариант 3

Красный Зелёный Жёлтый
Вариант 4 Красный Жёлтый

Зелёный

Вариант 5 Жёлтый Зелёный

Красный

Вариант 6 Жёлтый Красный

Зелёный

Ответ: 6 вариантов.

648. Сколько двузначных чисел, все цифры которых различны, можно составить из цифр 0, 1 и 2?

Таких двузначных чисел всего 4:

649. В футбольном турнире участвуют команды 5 «А» класса, 5 «Б» класса и 5 «В» класса. Сколько существует способов распределения первого и второго мест среди этих команд? Решение какой задачи из номеров 645—648 аналогично решению этой задачи?

Решим задачу при помощи схемы «Дерево возможных вариантов».

Итак, у нас получилось шесть возможных вариантов (последовательно места, занятые 5″А», 5″Б» и 5″В»):

Итак, у нас получилось шесть возможных вариантов (последовательно цвет шарика для Винни-Пуха, Пятачка и Кролика):

5″А»

5″Б»

5″В»

Вариант 1

1 2

Вариант 2

1 2

Вариант 3

2 1
Вариант 4 2

1

Вариант 5 1

2

Вариант 6 2

1

Задача аналогична задаче № 647.

Ответ: 6 вариантов.

650. Запишите все трёхзначные числа, для записи которых используются только цифры (Цифры не могут повторяться.):

1) 3, 4 и 6

  • 346, 364
  • 436, 463
  • 634, 643

2) 4, 7 и 0

651. Сколько различных трёхзначных чисел можно составить из цифр (Цифры могут повторяться.):

1) 1 и 2

  • 111, 112, 121, 122
  • 222, 221, 212, 211

Ответ: 8 чисел.

2) 0 и 1

Ответ: 4 числа.

652. Запишите все двузначные числа, в записи которых используются только цифры 2, 4, 9 и 0. (Цифры могут повторяться.)

  • 22, 24, 29, 20
  • 42, 44, 49, 40
  • 92, 94, 99, 90

653. Сколько двузначных чисел можно составить из цифр 6, 7, 8 и 9 так, чтобы цифры были записаны в порядке возрастания?

Ответ: 6 чисел.

654. Сколько двузначных чисел можно составить из цифр 6, 7, 8 и 9 так, чтобы цифры были записаны в порядке убывания?

Ответ: 6 чисел.

655. Сколько существует двузначных чисел, сумма цифр которых равна 5?

Всего 5 чисел: 14, 23, 32, 41, 50.

Ответ: 5 чисел.

656. Сколько двузначных чисел, сумма цифр которых равна чётному числу, можно составить из цифр 1, 2, 3, 4 (цифры могут повторяться)?

Всего 8 чисел: 11, 13, 22, 24, 31, 33, 42, 44.

Ответ: 8 чисел.

657. Сколько двузначных чисел, сумма цифр которых равна нечётному числу, можно составить из цифр 0, 1,2, 3?

Всего 6 чисел: 10, 12, 21, 23, 30, 32.

Ответ: 6 чисел.

658. Кот Базилио и лиса Алиса решили украсть золотой ключик, который хранится в каморке папы Карло. Чтобы туда проникнуть, нужно подобрать двузначный код. Им известно, что дверь в каморку закрывает Буратино, который знает пока что только четыре цифры: 0, 1, 2 и 3. Какое наибольшее количество вариантов придётся перебрать коту и лисе, чтобы открыть дверь?

Составим таблицу:

  • в первом столбце запишем возможные варианты первой цифры кода
  • в верхней строке — возможные варианты второй цифры кода
  • на пересечении строк и столбцов — возможные варианты кодов.

 

0 1 2 3

0

00 01 02 03

1

10 11 12

13

2 20 21 22

23

3 30 31 32

33

Итак, возможное количество вариантов кода — 16.

Ответ: 16 вариантов.

659. Сколько существует различных прямоугольников, периметры которых равны 24 см, а длины сторон выражены целым числом сантиметров?

P = (a + b) • 2

Если P = 24 см, то сумма длин сторон равна 24 : 2 = 12 см.

Существует 6 возможных вариантов таких прямоугольников. Длины сторон у них должны быть:

  1. 1 см и 11 см
  2. 2 см и 10 см
  3. 3 см и 9 см
  4. 4 см и 8 см
  5. 5 см и 7 см
  6. 6 см и 6 см (квадрат, который также соответствует определению прямоугольника).

Ответ: 6 прямоугольников.

660. У Ани есть 30 одинаковых кубиков. Сколько различных прямоугольных параллелепипедов она может из них составить, если для построения одного параллелепипеда надо использовать все имеющиеся 30 кубиков?

V = abc

Если V = 30, то можно подобрать 5 вариантов постройки прямоугольного параллелепипеда из одинаковых кубиков:

  1. 30 • 1 • 1 = 30 
  2. 15 • 2 • 1 = 30 
  3. 10 • 3 • 1 = 30 
  4. 6 • 5 • 1 = 30 
  5. 5 • 3 • 2 = 30 

Ответ: 5 вариантов.

661. На прямой отметили четыре точки А, В, С и D. Сколько отрезков с концами в отмеченных точках можно провести? Какой из рисунков § 24 помогает решить эту задачу?

Для решения этой задачи можно ориентироваться на рисунок 184 § 24:

Но лучше сделать свой рисунок для этой конкретно задачи:

Ответ: 6 отрезков.

662. Подножие горы и её вершину связывают три тропы. Сколько существует маршрутов, ведущих от подножия к вершине и затем вниз к подножию?

Нарисуем эти три маршрута схематично, изобразив их в виде лучей, выходящих из единой точки, где:

  • O — вершина горы
  • A — первая точка у подножия горы
  • B — вторая точка у подножия горы
  • C — третья точка у подножия горы.

Тогда возможные следующие варианты маршрутов (начало маршрута — вершина — конец маршрута):

  • AOA, AOB, AOC
  • BOA, BOB, BOC
  • COA, COB, COC

Итого — 9 вариантов маршрутов.

Ответ: 9 вариантов.

663. Спортивной команде предлагают футболки трёх цветов — красного, зелёного и синего, а шорты двух цветов — белого и жёлтого. Сколько вариантов выбора формы есть у команды?

Составим таблицу:

  • в первом столбце запишем возможные варианты шорт
  • в верхней строке — возможные варианты футболок
  • на пересечении строк и столбцов — возможные варианты формы

Форма

Футболки
Красные Зелёные

Синие

Шорты

Белые Красная футболка

белые шорты

Зелёная футболка

белые шорты

Синяя футболка

белые шорты

Жёлтые Красная футболка

жёлтые шорты

Зелёная футболка

жёлтые шорты

Синяя футболка

жёлтые шорты

Итак, возможное количество вариантов формы — 6.

Ответ: 6 вариантов.

664. У Тани есть четыре платья и две пары туфель. Сколько у Тани есть вариантов выбора наряда?

Составим таблицу:

  • в первом столбце запишем возможные варианты туфель
  • в верхней строке — возможные варианты платьев
  • на пересечении строк и столбцов — возможные варианты наряда

Наряд

 

Платья
1 2 3

4

Туфли

1 Платье № 1

Туфли № 1

Платье № 2

Туфли № 1

Платье № 3

Туфли № 1

Платье № 4

Туфли № 1

2 Платье № 1

Туфли № 2

Платье № 2

Туфли № 2

Платье № 3

Туфли № 2

Платье № 4

Туфли № 2

Итак, возможное количество вариантов нарядов — 8.

Ответ: 8 вариантов.

665. В отряде космонавтов есть три пилота и два инженера. Сколько существует способов составить экипаж, состоящий из одного пилота и одного инженера?

Составим таблицу:

  • в первом столбце запишем возможные варианты инженеров
  • в верхней строке — возможные варианты пилотов
  • на пересечении строк и столбцов — возможные варианты экипажа

Экипаж

Пилоты
1 2

3

Инженеры

1 Пилот 1

Инженер 1

Пилот 2

Инженер 1

Пилот 3

Инженер 1

2 Пилот 1

Инженер 2

Пилот 2

Инженер 2

Пилот 3

Инженер 2

Итак, возможное количество вариантов нарядов — 6.

Ответ: 6 вариантов.

666. На рисунке 185 изображён план одного района города. Отрезками изображены улицы. Сколько существует маршрутов из точки А в точку В, если передвигаться разрешено по улицам, идущими вверх или вправо?

Существуют следующие варианты маршрутов:

  1. Вверх — вверх — вправо — вправо
  2. Вверх — вправо — вверх — вправо
  3. Вверх — вправо — вправо — вверх
  4. Вправо — вверх — вверх — вправо
  5. Вправо — вверх — вправо — вверх
  6. Вправо — вправо — вверх — вверх

Итак, возможное количество вариантов маршрутов — 6.

Ответ: 6 вариантов.

667. В записи 1 * 2 * 3 * 4 вместо каждой звёздочки можно поставить один из знаков «+» или «•». Чему равно наибольшее значение выражения, которое можно получить?

Наибольшее значение выражения можно получить, если расставить знаки в таком порядке:

1 + 2 • 3 • 4 = 1 + 6 • 4 = 1 + 24 = 25.

Упражнения для повторения

668. Расстояние между двумя сёлами равно 28 км. Из этих сёл одновременно в одном направлении выехали мотоциклист и автобус. Автобус ехал впереди со скоростью 42 км/ч, а мотоциклист ехал со скоростью 56 км/ч. Через сколько часов после начала движения мотоциклист догонит автобус?

1) 56 — 42 = 14 (км/ч) — скорость, с которой мотоциклист догоняет автобус — скорость сближения.

2) 28 : 14 = 2 (часа) — время, за которое мотоциклист догонит автобус.

Ответ: 2 часа.

669. Решите уравнение:

670. 1) Одно из слагаемых в 14 раз больше другого. Во сколько раз их сумма больше меньшего слагаемого?

Пусть х — первое слагаемое. Тогда второе слагаемое равно 14х.

(14х + х) : х = 15х : х = 15

Ответ: в 15 раз.

2) Вычитаемое в 12 раз больше разности. Во сколько раз уменьшаемое больше разности?

Пусть х — разность, тогда вычитаемое равно 12х, а уменьшаемое равно (12х + х).

(12х + х) : х = 13х : х = 13

Ответ: в 13 раз.

671. На ферме есть 156 коров, каждая из которых даёт в день 12 л молока. Молоко с фермы вывозят в бидонах ёмкостью 40 л. В некоторый день на ферме было в наличии 42 пустых бидона. Хватит ли бидонов, чтобы вывезти с фермы надоенное за день молоко?

1) 156 • 12 = 1 872 (литра) — молока надаивают на ферме за 1 день.

2) 42 • 40 = 1 680 (литров) — молока помещается в 42 пустых бидона.

3) 1 680 литров < 1 872 литра, значит 42 бидона не хватит для вывоза всего надоенного за день молока.

Ответ: Нет, не хватит.

672. Решите кроссворд.

По горизонтали:

2. Результат арифметического действия (Частное)
3. Единица измерения времени (Секунда)
4. Единица измерения углов (Градус)
5. Компонент умножения (Множитель)
6. Компонент сложения (Слагаемое)

По вертикали:
1. «Царица наук» (Математика)

Задача от мудрой совы

673. В классе 30 учащихся. Они сидят по двое за 15 партами так, что половина всех девочек сидит с мальчиками. Можно ли учеников класса пересадить так, чтобы половина всех мальчиков сидела с девочками?

1) Если половина всех девочек сидят с мальчиками, значит вторая половина девочек сидит друг с другом по двое за партой. Значит половина девочек — это чётное количество человек.

2) Если половина девочек — это чётное количество человек, то общее количество девочек (две половины) также будет чётным числом.

3) Предположим, что условие задачи выполнимо и половину мальчиков можно посадить с девочками. Это значит, что другая половина мальчиков будет сидеть по двое за партой. То есть половина мальчиков также должно быть чётным числом

4) Половина мальчиков и половина девочек — это ровно половина класса. По нашему предположению это чётное количество человек, так как и половина мальчиков, и половина девочек чётные числа.

5) Но мы знаем, что в классе 30 учащихся, а половина от 30 человек — это 15 человек — нечётное число. Значит наше предположение о мальчиках было неверно и их нельзя посадить так, чтобы половина мальчиков сидела с девочками.

Ответ: Нет, нельзя. 

Комбинаторика 5 класс - математика, презентации

Комбинаторика

5 класс

Contents

  • Click to add Text
  • Click to add Text
  • Click to add Text
  • Click to add Text
  • Click to add Text
  • Click to add Text
  • Click to add Text

Content

Content

Вперед поедешь – голову сложишь, направо поедешь – коня потеряешь, налево поедешь – меча лишишься.

«Витязь на распутье» 1882 г. Васнецов Виктор Михайлович

Комбинаторика - ветвь математики, изучающая комбинации и перестановки предметов.

Термин « комбинаторика » происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять».

Комбинаторика - раздел математики, посвящённый решению задач выбора и расположения элементов в соответствии с данными условиями.

В доисторическую эпоху люди сталкивались с комбинаторными задачами.

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

Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э.

В Древней Греции

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

Со временем появились различные игры ( нарды, карты, шашки, шахматы и т. д.).

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

Задача о семи старухах

Старухи идут в Рим, каждая имеет 7 мулов, каждый мул несет 7 мешков, в каждом мешке лежит 7 хлебов, у каждого хлеба лежит 7 ножей, каждый нож нарежет 7 кусков хлеба. Чему равно общее число всего перечисленного?

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

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

Готфрид Вильгельм Лейбниц (1.07.1646 - 14.11.1716)

Комбинаторику, как самостоятельный раздел математики первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666г. Он также впервые ввел термин «Комбинаторика».

Задача Эйлера о мостах

Река образует острова, и через два речных рукава перекинуто 7 мостов. Спрашивается, можно ли пройти все 7 мостов так, чтобы каждый был пройден по одному лишь разу.

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

Леонард Эйлер

(1707-1783)

Комбинаторная задача задача, в которой идет речь о тех или иных комбинациях предметов

Способы решения комбинаторных задач

Таблица вариантов

Дерево вариантов

Правило умножения

1. Таблица вариантов

КБС

БСК

КСБ

СБК

БКС

СКБ

2. Дерево вариантов

3. Правило умножения

1 полоса - 3 способа

2 полоса - 2 способа

3 полоса - 1 способ

3 ∙ 2 ∙ 1 = 6

Ответ: 6 способов

Нидерланды

Сербия

Россия

Решение задач

Задача 1

Сколько можно составить двузначных чисел, в записи которых используются только цифры:

а) 1 и 2;

б) 3 и 0?

Задача 2

Какие двузначные числа можно составить из цифр 1, 2 и 3, если:

а) цифры в записи числа не повторяются;

б) цифры в записи числа могут повторяться?

Задача 3

Какие трехзначные числа можно составить из цифр 4, 5 и 0, если:

а) цифры в записи числа не повторяются;

б) цифры в записи числа могут повторяться?

Задание 4

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

Способ решения

Плюсы

Дерево вариантов

Минусы

Наглядность, возможность увидеть все варианты

Табличный

Очень громоздкий и длительный, если много различных вариантов

Наглядность, компактность, возможность увидеть все варианты

Правило умножения

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

Компактность,

быстрота решения

«Не видно» самих вариантов, можно только просчитать их количество.

Картинки:

http://server-life.ru/845-tf2-roll-the-dice-brosit-kosti.html

http://vivatcasino.com/istoria_igry_v_kosti.aspx

http://only-most.ru/?p=2098

http://photo.sibnet.ru/alb48804/ft1162009/

necessity

Презентация к уроку математики в 5 классе "Комбинаторные задачи"

Решение комбинаторных задач

1 урок

Учитель математики и информатики

МОБУ Стогинской СШ Ярославской области

Киселева Ирина Владимировна.

Направо пойдёшь - коня потеряешь,

Налево пойдёшь - голову сложишь,

Прямо пойдёшь – друга найдёшь.

Какая проблема стоит перед героем сказки?

Выбирать разные варианты, пути приходится всем людям.

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

Задача 1

Флаг России

Пробное действие. Составьте из полосок флаг РФ. Что означают цвета? Составьте другие комбинации. Это флаги других государств.

Нидерланды

Сербия

Как вы решали задачу если число элементов невелико, можно решить задачу путём перебора возможных вариантов. ? Как решить её эффективнее, рассмотреть все варианты, выбрать нужные и не пропустить? Есть приёмы, способы решения комбинаторных задач.

Франция

Цель урока

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

Задачи урока:

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

Комбинаторика

Комбинаторика- это область математики, которая изучает способы выбора, расположения, сочетания различных объектов.

Combinare – соединять, сочетать

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

Комбинаторная задача

Комбинаторная задача – это задача, в которой нужно найти комбинации каких – либо объектов или (и) количество таких комбинаций.

Попробуйте сами составить разные флаги

Дерево вариантов

Синий

Красный

Белый

С

К

Б

К

С

Б

Таблица. Можно граф.

К

Б

С

К

Б

С

Таблица вариантов

Метод решения- построение таблицы. Где встречаемся? (таблица значений функции, для решения задач)

Правило умножения

1 полоса – 3 способа

2 полоса – 2 способа

3 полоса – 1 способ

Умножение

Комбинаторная задача

Вопрос

Какими способами?

Сколько способов?

Какими

способами?

Вопрос комбинаторной задачи- два вида вопросов

Задача 2

В четверг в 1 классе должно быть 3 урока: русский язык, математика, физкультура. Сколькими способами можно составить расписание?

Отрезки задача 2 из пункта учебника

Решение

Таблица вариантов

С помощью таблицы вариантов. Можно с помощью дерева вариантов.

Дерево вариантов

Выпишите все варианты

Правило умножения

Первый урок – 3 варианта (русский язык, математика, физкультура

Второй урок – 2 варианта (из двух оставшихся)

Третий урок – 1 вариант ( один оставшийся)

3 * 2 * 1 = 6

Задача 3

Мы не чертили отрезки, а обозначали их буквами. Так можно поступать и в других задачах- заменять объекты их условными обозначениями. Такая замена называется кодированием. Каким способом мы решили задачу?

Задача 4

Какие числа называются натуральными?

Вопросы на с. 43. вывод: 3 цифры и отбросить 3, 2 цифры и отбросить 2.

Как записываются натуральные числа? Сколько натуральных чисел можно записать, используя эти цифры?

Назовите все натуральные двузначные числа, которые можно записать цифрами 1, 4, 7.

Древо вариантов

  • Найдите сумму чисел 2, 7 и 6.
  • Сколько чисел можно составить из цифр 2, 7 и 6?
  • Какими способами можно выбрать двух дежурных из шести человек?
  • Вычислите значения выражения (28 + 56) : 2
  • Из пяти блюд в столовой нужно выбрать на обед три. Сколько существует вариантов выбора?

Чем отличаются комбинаторные задачи от других задач математики?

  • Сегодня я узнал (а) …
  • Теперь я умею …
  • Я буду применять это …

учебник

  • № 138
  • № 139
  • № 141
  • № 142
  • № 146

Домашнее задание

П. 2.5 вопросы с. 45

№ 137, 140, 144, 147

Составьте свою комбинаторную задачу

Ресурсы

  • Дорофеев Г.В., Шарыгин И.Ф. Математика 5 класс. М. Просвещение. 2010
  • http://kaygorodova.ru/index.php?option=com_content&view=article&id=212:2011-11-01-06-43-54&catid=71:ushitelaym&Itemid=239
  • http://www.wiki.vladimir.i-edu.ru/images/4/4c/%d0%a0%d0%b5%d1%88%d0%b5%d0%bd%d0%b8%d0%b5_%d0%ba%d0%be%d0%bc%d0%b1%d0%b8%d0%bd%d0%b0%d1%82%d0%be%d1%80%d0%bd%d1%8b%d1%85_%d0%b7%d0%b0%d0%b4%d0%b0%d1%87.doc

Мир математики - Mathigon

Введение

Леонард Эйлер (1707 - 1783)

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

Первые комбинаторные задачи изучались математиками Древней Индии, Арабских стран и Греции. Интерес к этому предмету возрос в XIX и XX веках, вместе с развитием теории графов и таких проблем, как теорема о четырех цветах.Среди ведущих математиков - Блез Паскаль (1623–1662), Якоб Бернулли (1654–1705) и Леонард Эйлер (1707–1783).

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

Факториалы

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

В классе находится В.CombA1 учеников и стульев V.CombA1 , стоящих в ряд. В скольких различных порядках ученики могут сидеть на этих стульях?

Перечислим возможности - в этом примере V.CombA1 разных зрачков представлены V.CombA1 разных цветов стульев.

Существует {2: 2, 3: 6, 4: 24, 5: 120} [V.CombA1] различных возможных порядков. Обратите внимание, что количество возможных порядков очень быстро увеличивается по мере увеличения количества учеников.У 6 учеников есть 720 различных возможностей, и перечислять их все становится непрактично. Вместо этого нам нужна простая формула, которая говорит нам, сколько имеется заказов на n человек, чтобы они сели на n стульев. Затем мы можем просто заменить 3, 4 или любое другое число на на , чтобы получить правильный ответ.

Предположим, у нас есть стулья V.CombB1 , и мы хотим разместить V.CombB1 == 1? 'Один ученик': V.CombB1 == 2? 'Два ученика': V.CombB1 == 3? 'Три ученика ': V.CombB1 == 4? 'Четыре ученика': V.CombB1 == 5? 'Пять учеников': V.CombB1 == 6? 'Шесть учеников': 'семь учеников' на них. {7: «Семь учеников могут сесть на первый стул. Затем есть 6 учеников, которые могли бы сесть на второй стул. Есть 5 вариантов для третьего стула, 4 варианта для четвертого стула, 3 варианта для пятого стула, 2 варианта для шестого стула и только один вариант для последнего стула. ', 6: «Есть 6 учеников, которые могли бы сесть на первый стул. Затем есть 5 учеников, которые могли бы сесть на второй стул.Есть 4 варианта для третьего стула, 3 варианта для четвертого стула, 2 варианта для пятого стула и только один вариант для последнего стула. ', 5: «Пятеро учеников могли бы сесть на первый стул. Затем есть 4 ученика, которые могут сесть на второй стул. Есть 3 варианта для третьего стула, 2 варианта для четвертого стула и только один вариант для последнего стула. ', 4: «Есть 4 ученика, которые могли бы сесть на первый стул. Затем есть 3 ученика, которые могут сесть на второй стул.Есть 2 варианта для третьего стула и только один вариант для последнего стула. ', 3: «Есть 3 ученика, которые могут сесть на первый стул. Затем есть 2 ученика, которые могут сесть на второй стул. Наконец, остался только один ученик, чтобы сесть на третий стул. ', 2: «Есть 2 ученика, которые могут сесть на первый стул. Далее остается только один ученик, который может сесть на второй стул. ', 1: 'Это только один вариант для одиночного стула.'} [V.CombB1] Всего

возможности.Чтобы упростить обозначения, математики используют знак «!» называется факториалом. Например, 5! («Пять факториалов») то же самое, что 5 × 4 × 3 × 2 × 1. Выше мы только что показали, что существует n ! возможности заказать н объектов.

Насколько разными способами 23 ребенка могли сесть на 23 стула в классе математики? Если у вас 4 урока в неделю, а в году 52 недели, сколько лет нужно, чтобы изучить все возможности? Примечание: возраст Вселенной составляет около 14 миллиардов лет.

Для 23 детей, чтобы сесть на 23 стула, их 23! = 25 852 016 738 884 800 000 000 возможностей (это число слишком велико для отображения на экране калькулятора). Испытание всех возможностей займет

23! 4 × 52 = 124 288 542 000 000 000 000 лет.

Это почти в 10 миллионов раз больше нынешнего возраста Вселенной!

Перестановки

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

Сколько различных возможностей существует для любого Math.min (V.CombC1, V.CombC2) из V.CombC1 учеников, чтобы сесть на Math.min (V.CombC1, V.CombC2) стулья? Обратите внимание, что Math.max (0, V.CombC1-V.CombC2) останется включенным, и мы не должны включать его при перечислении возможностей.

Давайте начнем снова, перечислив все возможности:

Чтобы найти простую формулу, подобную приведенной выше, мы можем думать о ней очень похожим образом. «Есть ученики« + V.CombC1 + », которые могут сесть на первый стул. '+ (((Math.min (V.CombC1, V.CombC2)) == 2 || (Math.min (V.CombC1, V.CombC2)) == 3 || (Math.min (V.CombC1, V .CombC2)) == 4)? 'Тогда есть' + (V.CombC1-1) + 'ученики, которые могли бы сесть на второй стул.': '') + (((Math.min (V.CombC1, V.CombC2)) == 3 || (Math.min (V.CombC1, V.CombC2)) == 4)? 'Тогда есть' + (V.CombC1 -2) + 'ученики, которые могли бы сесть на третий стул.': '') + (((Math.min (V.CombC1, V.CombC2)) == 4)? 'Наконец, остался один ученик, который сядет на последний стул.':' ') + ((V.CombC1- (Math.min (V.CombC1, V.CombC2)) == 1 || V.CombC1- (Math.min (V.CombC1, V.CombC2)) == 2 || V. CombC1- (Math.min (V.CombC1, V.CombC2)) == 3)? 'Нас не волнуют оставшиеся' + (V.CombC1-V.CombC2) + 'дети, оставшиеся стоять.': ' ') Всего

возможности. Мы снова должны подумать об обобщении этого. Мы начинаем, как и делали бы с факториалами, но останавливаемся, не дойдя до 1. Фактически мы останавливаемся, как только достигаем числа студентов без стула. При размещении 7 учеников на 3 стульях их

7 × 6 × 5 = 7 × 6 × 5 × 4 × 3 × 2 × 17 × 6 × 5 × 4 × 3 × 2 × 1 = 7 ! 4! = 7 ! ( 7 - 3 )!

возможности, так как 4 × 3 × 2 × 1 будут компенсировать друг друга.Опять же, для этого есть более простое обозначение: 7 P 3 . Если мы хотим разместить n объектов на m позиций, то будет

n P м = n ! ( n - м )!

возможности. P означает « p ermutations», поскольку мы подсчитываем количество перестановок (порядков) объектов. Если m и n такие же, как и в задаче в начале этой статьи, мы имеем

n P n = n ! ( n - n )! = n ! 0 !.

Чтобы понять это, мы определяем 0! = 1. Теперь n P n = n ! как и следовало ожидать от нашего решения первой проблемы.

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

Имеется 10 цифр (0, 1,…, 9), каждая из которых встречается не более одного раза.Число порядков этих цифр составляет 10 P 4 = 5040. Проверка такого количества комбинаций займет очень много времени, поэтому 4-значные блокировки очень безопасны.

Комбинации

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

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

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

, итого их 10. Если бы мы вычислили 5 P 3 = 60, мы бы дважды подсчитали некоторые возможности, как показано в следующей таблице:

При перестановках мы считаем каждую комбинацию из трех футболок 6 раз, потому что их 3! = 6 способов заказать три футболки.Чтобы получить количество комбинаций из количества перестановок, нам просто нужно разделить на 6. Мы пишем

5 C 3 = 5 P 33! = 606 = 10.

Здесь C означает «комбинацию c ». В общем, если мы хотим выбрать r объектов из общего числа n , будет

n C r = n P r r ! = n ! р ! ( n - r )!

различных комбинаций.Вместо n C r математики часто пишут n C r = ( n r ), как дробь в скобках, но без промежуточной линии. (Для упрощения набора мы продолжим использовать первую строчную нотацию.)

(a) В вашем классе 10 детей, но вы можете пригласить только пятерых на свой день рождения. Сколько разных комбинаций друзей вы могли бы пригласить? Объясните, следует ли использовать комбинации или перестановки.

(б) На вечеринке 75 человек. Каждый раз всем пожимает руку. Как часто в целом рукопожатие? Подсказка: сколько людей участвует в рукопожатии?

(a) Количество комбинаций друзей, которых вы можете пригласить, составляет 10 C 5 = 252. Мы использовали комбинации, потому что не имеет значения, в каком порядке мы приглашаем друзей, на какие мы приглашаем.

(b) Вы хотите найти количество всех возможных пар гостей вечеринки.Это просто 75 C 2 = 2775. (Это много рукопожатий!)

Комбинаторика и треугольник Паскаля

Рассчитаем несколько значений n C r . Начнем с 0 C 0. Затем находим 1 C 0 и 1 C 1. Затем 2 C 0, 2 C 1 и 2 C 2. Затем 3 C 0 , 3 C 1, 3 C 2 и 3 C 3. Все эти результаты можно записать в таблицу:

0 С 0 = 1
1 С 0 = 1 1 С 1 = 1
2 С 0 = 1 2 С 1 = 2 2 С 2 = 1
3 С 0 = 1 3 С 1 = 3 3 С 2 = 3 3 С 3 = 1
4 С 0 = 1 4 С 1 = 4 4 С 2 = 6 4 С 3 = 4 4 С 4 = 1
5 С 0 = 1 5 С 1 = 5 5 С 2 = 10 5 С 3 = 10 5 С 4 = 5 5 С 5 = 1

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

Теперь мы также знаем, что r -е число в n -й строке также задается n C r (но мы всегда должны начинать отсчет с 0, поэтому первая строка или столбец фактически нулевой ряд). Если мы применим то, что мы знаем о создании треугольника Паскаля, к нашим комбинациям, мы получим

( n r ) + ( n r + 1) знак равно ( n + 1 r + 1) .

Это известно как идентификатор Паскаля . Вы можете получить его, используя определение n C r в терминах факториалов, или вы можете думать об этом следующим образом:

Мы хотим выбрать r + 1 объектов из набора n + 1 объектов. Это в точности то же самое, что пометить один объект из n + 1 , который будет называться X, и либо выбрать X плюс r других (из оставшихся n), либо не выбрать X и r + 1 других ( от оставшихся n).

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

Звезды и полосы

Решение

Пример

Зеленщик на рынке хранит большое количество из различных видов фруктов. Какими способами мы можем сделать сумку из или фруктов? Обратите внимание, что r может быть меньше, равно или больше n .

Обратите внимание, что с r n существует n C r способов выбрать по одному фрукту каждого вида. Однако мы также можем съесть более одного фрукта каждого вида, например, два яблока, одну клубнику и один банан.

Мы можем представить любой допустимый выбор фруктов цепочкой звезд и полосок, как показано в этом примере:

★★★ | ★★ | | ★★ |
3 типа 1 2 типа 2 0 типа 3 2 типа 4 1 типа 5

Всего имеется r звезд (представляющих r фруктов, которые нам разрешено брать) и n - 1 столбик (деление на разных фруктов).Это составляет r + n - всего 1 место. Любой заказ r звездочек и n - 1 батончик соответствует ровно одному действительному выбору фруктов.

Теперь мы можем применить наши комбинаторные инструменты: есть r + n - 1 разрядов, и мы хотим выбрать n - 1 из них в качестве столбцов (все остальные - звездочки). Что есть ровно ( r + n - 1) C ( n - 1) возможностей для этого!

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

(10 + 5-1) C (5-1) = 14 C 4 = 24 024

возможности. Подумайте об этом в следующий раз, когда пойдете за покупками!

Комбинаторика и вероятность

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

P ( X ) = вероятность того, что произойдет X = количество исходов, при которых случится X , общее количество возможных исходов

Вы можете использовать комбинаторику, чтобы вычислить «общее количество возможных результатов».Вот пример:

Четверо детей, которых зовут A, B, C и D, случайным образом сидят на четырех стульях. Какова вероятность того, что А сядет на первый стул?

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

P (A сидит на первом стуле) = количество результатов, где A сидит на первом стуле, общее количество возможных результатов = 624 = 14.

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

(a) Почтальон должен доставить четыре письма в четыре разных дома на улице. К сожалению, дождь стер адреса, поэтому он просто раздает их случайным образом, по одной букве на дом. Какова вероятность, что каждый дом получит нужную букву? (☆ Какова вероятность, что каждый дом получит неправильную букву?)

(b) В лотерее нужно угадать 6 номеров из 49.Какова вероятность того, что вы все сделаете правильно? Если каждую неделю отправлять 100 предположений, сколько времени в среднем вам понадобится, чтобы выиграть?

(a) Всего 4! = 24 способа случайного распределения букв и только один способ получить их все правильно. Таким образом, вероятность того, что каждое письмо будет доставлено в нужный дом, составляет 1/24 = 0,0417 = 4,17%.

Определить вероятность того, что каждое письмо будет доставлено не в тот дом, немного сложнее.Это не просто 1 - 0,0417, так как во многих случаях один или два, но не , все домов получают правильную букву. В этом простом случае самым простым решением было бы записать все 24 варианта. Вы обнаружите, что в 9 из 24 случаев каждый дом получает неправильную букву, что дает вероятность 0,375 = 37,5%. Если домов слишком много, чтобы записать все возможности, вы можете использовать идею под названием «Принцип включения-исключения» .

(b) Существует 49 C 6 = 13 983 816 возможных результатов лотереи, поэтому вероятность получения правильного решения составляет 1/49 C 6 = 0.000000072.

В среднем также потребуется 13 983 816 попыток, чтобы выиграть. Если мы отправляем 100 предположений каждую неделю, это соответствует 139 838 неделям, что равняется 2689 годам. Урок, который нужно усвоить: не играйте в лото!

Искусство решения проблем

Формирование комитета - это один из методов решения определенных задач комбинаторики.

Введение

Сначала мы познакомимся с формированием комитета на простом примере.

Проблема

Сколько комитетов из 3 человек можно сформировать из группы из 12 человек?

Решение

Предположим, что порядок, в котором мы выбираем членов комитета, не имеет значения.Тогда будет 12 вариантов для первого человека, 11 для второго и 10 для последнего. Итак, по принципу умножения, будут полные комитеты.

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

Примечание: существует специальное обозначение для обозначения количества способов выбрать комитет размера из набора размеров.Мы используем, который называется биномиальным коэффициентом. В дальнейшем в этой статье мы будем использовать это обозначение.

Доказательство комбинаторных тождеств

Метод формирования комитета может быть очень мощным инструментом для доказательства комбинаторной идентичности.

Проблема

Докажите, что

Решение

Мы можем рассматривать каждый термин индивидуально: это количество способов, которыми может быть выбран комитет размера 0, это количество способов, которыми может быть выбран комитет размера 1, и так далее.Таким образом, проблема может быть сформулирована заново как определение количества комитетов любого размера, которые могут быть сформированы из группы людей. Каждый человек может входить в комитет или не входить в комитет. Поскольку у каждого человека есть две возможности, и каждый человек независим от другого человека, существуют комитеты.

Дальнейшие проблемы

Вводные проблемы

  1. Найдите количество способов выбрать комитет размера 4 из группы из 8 человек.
  2. Сколько способов можно выбрать комитет размера 3 из группы из 10 человек, если один из 3 человек в комитете назначен президентом?
  3. Вычислить значение.

Промежуточные задачи

  1. Три листка бумаги опущены в шляпу. На них написаны цифры 1, 3 и 9 соответственно. Из шляпы вынимается любое количество листовок, и числа, написанные на них, складываются. Сколько возможных сумм?
  2. Докажите это.
  3. Подтвердите личность Паскаля:
  4. Докажите, что

См. Также

Александр Постников: 18.211 Комбинаторный анализ

класс собраний: понедельник, среда, пятница; 14 - 15 часов; комната 4-145

инструктор: Александр Постников

часы работы: Понедельник с 15 до 16 или по предварительной записи

грейдер: Чжэнкун Ли zhenkun @ mit.edu

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

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

уровень курса: бакалавриат

рекомендуемый учебник:
* Миклош Бона, Прогулка по комбинаторике: Введение в теорию перечисления и графов , 4-е издание, World Scientific. (Предыдущие издания учебника также подходят для курса.)

дополнительное чтение: По комбинаторике существует множество отличных учебников. Тебе не нужно следующие книги для этого класса. Но, если вы хотите узнать больше, вы можете взглянуть на них.
* Ричард П. Стэнли, Алгебраическая комбинаторика: прогулки, деревья, картины и многое другое . Эта книга написана для 18.212 алгебраической комбинаторики, что является продолжением этого курса.
* Ричард П. Стэнли, Перечислительная комбинаторика , Том 1 и Том 2. Это известная книга о перечислительная комбинаторика. Это учебник для выпускников. Он охватывает многие темы из этого курса на более глубоком уровне.

оценка: Наборы задач каждые две недели 50% + 3 включительно викторины 50%.Заключительного экзамена не будет.

наборов задач:

  • Набор задач 1 (до среды, 18 сентября 2019 г.)
  • Набор задач 2 (срок до пятницы, 4 октября 2019 г.)
  • Набор задач 3 (до пятницы, 18 октября 2019 г.)
  • Набор задач 4 (до понедельника, 28 октября 2019 г.)
  • Набор задач 5 (до понедельника, 18 ноября 2019 г.)
  • Набор задач 6 (до среды, 27 ноября 2019 г.)
  • Необязательный набор задач 7 (включите любое количество решения до среды, 11 декабря 2019 г.).Отправьте свои решения по электронной почте на адрес [email protected] (cc to [email protected]) или написанное от руки решения Zhenkun Li.

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

практика для викторин:

  • Тест 1 охватывает перекресток материала, изложенного в лекциях 1–9 и главах 1–5 [Bona].Здесь

    4 проблемы а также Еще 5 проблем из прошлых лет, и их ответы.

  • Тест 2 охватывает пересечение лекций 11–23 и глав 6–9 книги [Bona].

    Вот несколько практических задач из старых викторин:

    одна практика Quiz 2, еще одна практика Quiz 2, еще одна практика Quiz 2 с ответами.

  • Тест 3 будет охватывать материал лекций 25-35, кроме матроидов, многочленов Тутте и игр со стрельбой по фишкам. В основном речь пойдет о теории графов.Материал может включать в себя: графики, остовные деревья, матрицы смежности и лапласа, теорема о матричном дереве, остовные деревья минимального веса, сопоставления в графах, теорема Холла о браке, раскраски графов, хроматический многочлен, и хроматическое число, ациклические ориентации, удаление-сжатие, планарные графы, Формула Эйлера, парковочные функции и др.

    Вот несколько практических задач из старых викторин:

    одна практика Quiz 3, еще одна практика Quiz 3, еще одна практика Quiz 3 с ответами.

    (Проблема 2 в последнем практическом тесте касается сопротивления. Мы не обсуждали электрические сети в классе. Так что не беспокойтесь о таких проблемах.)

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

    Чтобы подготовиться к викторине, вам следует

    • Просмотрите материал лекций 24–35, включая определения, теоремы и примеры.
    • Решите указанные выше практические задачи.
    • Решите столько задач из глав 10-12 [Bona], сколько захотите.

Средние баллы за наборы задач и викторин: P1: 96,88 / 100, Q1: 37,94 / 40, P2: 95,47 / 100, P3: 91,76 / 100, P4: 44,97 / 50, 2-й квартал: 33,15 / 40, П5: 72,09 / 80, П6: 45,5 / 50, Вопрос 3: 36,33 / 40.

лекция (с предложением чтения от [Бона]):

  1. Вт 04.09.2019. Вступление. Что такое комбинаторный анализ?
  2. F 06.09.2019.Принцип голубиной норы. Теоремы Рамсея и Эрдоша-Секереса. [Бона, Глава 1].
  3. M 09.09.2019. Математическая индукция. [Бона, Глава 2].
  4. Вт 11.09.2019. Перестановки. [Бона, Глава 3].
  5. F 13.09.2019. Биномиальная теорема. Биномиальные и полиномиальные коэффициенты. [Бона, Глава 4].
  6. M 16.09.2019. Длина и количество инверсий перестановок. q-факториал.
  7. Вт 18.09.2019. q-биномиальные коэффициенты. Композиции. [Бона, Раздел 5.1]. Выполняется набор задач 1.

    F 20.09.2019. Студенческий отпуск - без занятий.

  8. M 23.09.2019. Композиции (продолжение), наборы разделов и целые разделы. Числа Фибоначчи. [Бона, Глава 5].
  9. Вт 25.09.2019. Установите разделы и целочисленные разделы (продолжение). Числа Белла и Стирлинга.
  10. F 27.09.2019. Тест 1.
  11. M 30.09.2019. Целочисленные переносы (продолжение).
  12. Вт 02.10.2019. Циклы в перестановках. Числа Стирлинга 1-го рода vs числа Стирлинга 2-го рода.[Бона, Глава 6].
  13. F 10.04.2019. Числа Стирлинга 1-го рода (продолжение). Записи перестановок. Введение в принцип включения-исключения. Выполняется набор задач 2.
  14. M 07.10.2019. Принцип включения-исключения. Психологические расстройства. [Бона, Глава 7].
  15. Вт 09.10.2019. Обычные производящие функции. Примеры: генерирующие функции для числа разделов и числа Фибоначчи. [Бона, Глава 8].
  16. F 11.10.2019. Производящие функции (продолжение). От рекуррентных соотношений к производящим функциям.Каталонские числа.

    М 14.10.2019. День Колумба - каникулы.

  17. Вт 16.10.2019. Производящие функции (продолжение). Экспоненциальные производящие функции. Экспоненциальная формула.
  18. F 18.10.2019. Производящие функции (продолжение). Решается набор задач 3.
  19. M 21.10.2019. Производящие функции (продолжение). Обычные производящие функции против экспоненциальных производящие функции. Рекуррентные соотношения и дифференциальные уравнения. Каталонские числа и метод отражения.
  20. Вт 23.10.2019. Каталонские числа (продолжение): циклические сдвиги, двоичные деревья, плоские деревья и поиск в глубину.
  21. F 25.10.2019. Каталонские числа (продолжение): перестановки с сортировкой по очереди и сортировкой по стеку, избегание шаблонов [Bona, Глава 14]. Теория графов: проблема Кенигсбергского моста Эйлера и эйлеровы тропы [Бона, глава 9].
  22. М 28.10.2019. Эйлеровы тропы и гамильтоновы циклы. Формула Кэли для числа деревьев и кодов Прюфера [Бона, Глава 10].Набор задач 4 подлежит рассмотрению.
  23. Вт 30.10.2019. Остовные деревья графов.
  24. F 01.11.2019. Тест 2.
  25. M 04.11.2019. Остовные деревья минимального веса. Жадный алгоритм Крускала. Матроиды.
  26. Вт 11.06.2019. Графики и матрицы. Доказательство теоремы о матричном дереве.
  27. F 11.08.2019. Сопоставления в графиках. Теорема Холла о браке. [Бона, Глава 11].

    М 11.11.2019. День ветеранов - праздник.

  28. Вт 13.11.2019. Раскраски графиков.Хроматический полином. Повторение удаления-сокращения.
  29. F 15.11.2019. Ациклические ориентации графов. Хордовые графы.
  30. M 18.11.2019. Полином Дихромата Тутте. Набор задач 5 подлежит рассмотрению.
  31. Вт 20.11.2019. Планарные графы. Формула Эйлера. Теорема Куратовски. Многогранники. [Бона, Глава 12].
  32. F 22.11.2019. Функции парковки. Многочлен обращения дерева.
  33. M 25.11.2019. Чип-игра на графах.
  34. Вт 27.11.2019.Руководил эйлеровыми турами и деревьями. ЛУЧШАЯ теорема. Теорема о матричном дереве для ориентированных графов. Набор задач 6 подлежит рассмотрению.

    F 29.11.2019. Отпуск на День Благодарения.

  35. M 02.12.2019. Системы различных представителей. Собственные значения матрицы смежности vs собственные значения матрицы Лапласа. Количество остовных деревьев в графе d-куба.
  36. Вт 04.12.2019. Тест 3.
  37. F 06.12.2019. Домино мозаики.
  38. M 09.12.2019.Гостевая лекция № 1 профессора Томаса Лэма (Университет штата Мичиган и Массачусетский технологический институт): Электрические сети.
  39. Вт 11.12.2019. Гостевая лекция №2 Томаса Лэма: «Электрические сети» (продолжение).
    Сдайте любое количество решений для (необязательного) набора проблем 7 до этой даты.

Титу Андрееску, Цзуминг Фэн: 9780817643171: Amazon.com: Книги

Из обзоров:

«51« вводная задача »Андрееску и 51« сложная задача », все новые, были бы прекрасным дополнением любого университетского курса комбинаторики или дискретной математики.Этот том содержит подробные решения, иногда несколько решений, для всех проблем, а некоторые решения предлагают дополнительные возможности для дальнейшего размышления. . . "

CHOICE

" Еще одна отличная попытка развития комбинаторных навыков, особенно для учащихся, участвующих в математических соревнованиях, представлена ​​в этой книге через 102 избранных комбинаторных задачи. "

―ZENTRALBLATT MATH

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

―МАТЕМАТИЧЕСКАЯ ГАЗЕТА

" Эта книга содержит 102 тщательно отобранных комбинаторных задачи, используемых при обучении и тестировании в США Команда Международной математической олимпиады.Половина задач - вводные, остальные - более сложные. У всех проблем есть комплексные решения. . . Это не набор очень сложных, непонятных вопросов. Вместо этого книга постепенно развивает комбинаторные навыки и методы учащихся. Его цель - расширить представление учащихся о математике при подготовке к возможному участию в математических соревнованиях ».

10IASI POLYTECHNIC MAGAZINE

« Оба автора являются тренерами команды Международной математической олимпиады США (IMO). несколько лет.… Книга постепенно развивает у студентов комбинаторные навыки и приемы. Он направлен на то, чтобы расширить представление учащихся о математике при подготовке к возможному участию в математических олимпиадах. … Это книга для тех, кто решает проблемы. … Настоящий сборник проблем и представленные решения тщательно разработаны, чтобы развить у читателей способности решать проблемы. … Удачи, работая над ними! »(Петер Хайнал, Acta Scientiarum Mathematicarum, Vol. 69, 2003)

(PDF) Стратегия и методы решения комбинаторных задач начального обучения математике

International Journal of Modern Education Research 2015; 2 (6): 77-87 79

комбинаторика, чтобы дать им возможность применять приобретенные знания

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

и развить умственные способности учащихся

, особенно в область логического и комбинаторного мышления

и применение комбинаторных

концепций и моделей в различных областях.

Преподавание комбинаторики в этом возрасте требует от молодых

учеников уметь распознавать комбинаторную сущность в

различных задачах и решать их интуитивно с большой свободой и творчеством

, но не запоминать и применять

готово. сформулировал формулы при решении комбинаторных задач.

Операционные задачи начального обучения комбинаторике в начальном образовании

могут быть определены с точки зрения результатов и успеваемости

учеников следующим образом:

• На основе заданных критериев, манипулируя предметами,

используя диаграммы или таблицы студенты должны уметь формировать

различных конкретных наборов и подмножеств объектов, изображений и

символов;

• Они должны иметь возможность сравнивать заданные наборы и подмножества

объектов, чисел, букв и т. Д .;

• Студенты должны быть в состоянии изучить различные возможности

формирования подмножеств данного набора, а также возможные

способов организации подмножеств;

• На простых конкретных примерах учащиеся должны уметь определять

упорядоченных пар заданных наборов и определять

их кардинальное число;

• Студенты должны быть в состоянии произвести систематическую процедуру

для различного формирования и расположения

бетонных наборов и на более простых примерах определить

количество всех возможностей;

• Студенты должны уметь распознавать и успешно применять комбинаторные идеи и методы

для решения

задач из реальной повседневной жизни и других областей, в

случаях, чувствительных к элементарному комбинаторному моделированию.

Согласно Скемпу (1971) бесполезно смешивать логический

и психологический подходы в начальном обучении математике,

, поскольку основная цель логического подхода - «убедить скептика

», в то время как основная цель в психологическом подходе к

облегчить понимание. С другой стороны, логический подход

представляет конечные результаты обучения и, следовательно, лишает

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

(Skemp, 1971).Студенты изучают

математических понятий вместо того, чтобы развивать математические

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

, также

подчеркивает примат развития математического мышления

над математическими мыслями (Freudenthal, 1974). Основные идеи

его реалистичной концепции начального обучения математике

заключаются в следующем: ученики не должны получать

готовой математики, а должны создавать различные

реальных проблемных ситуаций как основу для открытия различных

математические идеи, концепции и восприятия.Таким образом,

вместо пассивного получателя знаний

ученик станет активным творцом собственных знаний.

В большинстве стран подход к начальному обучению

математике был основан на творческой деятельности, например

как: обучение через игру и манипуляции с предметами,

изобилие учебных материалов, творческий подход к обучению

, спиральное формирование понятий, поэтапно,

дифференциация и индивидуализация.

Таким образом, определенная творческая энергия позволяет детям

изучать тонкое содержание, такое как множества, логика, комбинаторика и

вероятности.

Базовая парадигма современного начального обучения математике

- это творческий подход к математизации реальности, а не алгоритмическое решение математических задач

, в котором

делает упор на развитие вычислительной техники, а

- на решение множества готовых математические модели (Автор,

2013).

Именно из-за возраста детей, вовлеченных в этот этап обучения

, процессы и достижения их познания

ограничены конкретным, материальным и очевидным.

Содержимое комбинаторного характера преподается таким образом

, что инструкция начинается с формирования наборов и подмножеств,

порядок предметов, лиц или некоторого другого дидактического материала,

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

подмножеств с меньшим количеством элементов из большего количества элементов, таким образом создавая

комбинаций, а затем формируются упорядоченные

подмножеств, вариаций, а также упорядоченные пары из двух элементов

наборов.

Методическая трансформация этих концепций предполагает

творческого подхода и использование новых методов и техник

, таких как метод обнаружения, метод задачи, метод предположения

, кибернетические методы, графики, различные диаграммы, таблицы

и наборы.

Решение комбинаторных задач происходит поэтапно:

следует:

• Экспериментальное решение - игры или манипуляции с объектами

.Затем в более сложных задачах необходимо

, чтобы нарисовать дерево событий, использовать таблицы и ряды,

и т. Д. Вначале нет необходимости определять общее количество возможностей

(перестановок,

комбинаций). , вариации или упорядоченные пары), но, скорее,

важно найти как можно больше примеров.

• Позже, в простых случаях можно начать с пиктограммы

проблемы или даже с правильного символического представления

, которое должно быть

, с последующим установлением требований для создания всех

возможностей, или определить или оценить количество из

запрошенных возможностей без использования заранее определенной формулы

.Для символического представления одним из наиболее подходящих устройств

являются компьютеры с соответствующим

аппаратным и программным обеспечением (Автор, 2009).

• Применение комбинаторики к различным областям обучения, таким как

как: формирование слов определенной длины из заданных

букв, формирование предложений с определенным количеством

слов из заданных слов, алфавитные расписания: библиотеки,

словарей, лексиконы и т. д., создание мелодий из заданных

нот, возможности раскрашивания различных картинок с

множественными полями, возможности комбинирования цветов и

создания оттенков, возможность перегруппировки учеников, возможности

для формирования спортивных команд из определенного количества студенты,

возможности выбрать несколько (2-3) лидеров или

представителя от большего числа студентов,

Как лучше всего ориентироваться в ландшафте возможных экспериментов?

Bioessays.2012 Март; 34 (3): 236–244.

Дуглас Б. Келл

1 Школа химии и Манчестерский междисциплинарный биоцентр, Манчестерский университет, Манчестер, Ланкс, Великобритания

2 Исследовательский совет биотехнологии и биологических наук, Polaris House, Суиндон

9000, Великобритания 1 Школа химии и Манчестерский междисциплинарный биоцентр, Манчестерский университет, Манчестер, Ланс, Великобритания

2 Исследовательский совет биотехнологии и биологических наук, Polaris House, Суиндон, Уилтс, Великобритания

Повторное использование этой статьи разрешено в соответствии с Соглашением о Creative Commons, Attribution 2.5, что не допускает коммерческую эксплуатацию.

Эта статья цитируется в других статьях в PMC.

Abstract

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

Ключевые слова: автоматизация, эпистемология, эволюционные вычисления, эвристика, научное открытие

Введение

Очень важно знать, что делает научную проблему «сложной» и почему это так, поскольку такое знание может Сама по себе, укажите лучшие способы борьбы с ней. Действительно, твердость и выполнимость, возможно, представляют собой два главных атрибута, лежащих в основе разумного выбора научной проблемы, за которую нужно взяться 1 .Многие научные проблемы могут быть сформулированы таким образом, чтобы они были `` ограниченными '', в том смысле, что существует дискретное (если большое) количество возможных решений и где качество `` целевой функции '' (решения) известно или равно наименее узнаваемый. Примерами таких проблем могут быть «найдите мне ген, который существенно влияет на процесс X (например, время цветения 2 или длину корня 3 у растения)», «найдите мне низкомолекулярный препарат, который в концентрации 1 мкМ подавляет активность. фермента Y не менее чем на 50% »или« найдите мне набор из трех ферментов, удаление (или модификация) каждого из которых привело бы к максимальному увеличению биотехнологического производства молекулы Z ».

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

Задачи этого типа известны как неполиномиальные (NP) -сложные задачи (например,грамм. 4 , 5 ), количество возможных решений обычно астрономическое, поэтому большинство стратегий (известных как эвристических методов 6 ) просто ищут «хорошее», но не доказуемо оптимальное решение.

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

«Интеллектуальная карта» 7 , излагающая основное содержание этого эссе, дается в.

«Интеллектуальная карта» 7 , излагающая основное содержание этой статьи. Чтобы читать его, начните с «12 часов» и читайте по часовой стрелке.

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

Стоит немного изучить вопрос об экспоненциальном масштабировании с количеством переменных. Для этого я выбрал биологический пример на основе аптамеров.Аптамеры представляют собой последовательности нуклеиновых кислот, которые могут связываться с лигандом-мишенью (например, 8 ). Возьмем случай, когда ищут ДНК-аптамер с наивысшим коэффициентом связывания для такого целевого лиганда 9 - 11 . Если мы рассмотрим 30меров, в которых каждая позиция может быть A, T, G или C, количество возможных 30меров составит 4 30 , что составляет ∼10 18 , и даже если расположить их в виде пятен размером 5 мкм, массив будет занимать 29 км 2 9 ! Очевидно, что количество возможностей экспоненциально масштабируется с количеством оснований в нуклеотидной цепочке (т.е.е. переменные). Время жизни известной Вселенной в секундах составляет ∼10 17 12 , поэтому очевидно, что мы не можем попробовать их все.

Для белков, претерпевающих естественную или направленную эволюцию и использующих только 20 «общих» аминокислот, количество вариантов последовательностей для замен M в данном белке из N аминокислот составляет 13 . Для белка из 300 аминокислот с заменами всего в 1, 2 и 3 аминокислоты это 5700, приблизительно. 16 миллионов и ок.30 миллиардов. Даже для очень небольшого белка из N = 50 аминокислот количество вариантов превышает 10 12 , когда M = 10. Та же комбинаторная формула применима для нахождения подмножества k ферментов из n, которое можно было бы пожелать. изменить ради некоторой выгоды; если n равно 1000 (разумное число для метаболизма 14 , 15 ), для k = 1, 2, 3, 4, 5 и 6, эти числа равны 1000, 499 500, 166 167 000, 41 417 124 750, 8,25 × 10 12 и 1.37 × 10 15 . Эти числа уже экспериментально трудноразрешимые для k = 3, что приводит к ряду важных выводов. Во-первых, если (как это имеет место) большинство биологических процессов контролируются множественными генными продуктами, поиск «под фонарным столбом» любого количества из отдельных генных продуктов будет гораздо менее успешным, чем поиск решений среди гораздо большего числа комбинаций. генных продуктов 16 . Во-вторых, одно это частично объясняет огромные исторические трудности в разработке штаммов путем случайной мутации и отбора для улучшения процессов ферментации.Это также указывает на полезность первой компьютерной модели системы, с помощью которой можно гораздо более эффективно исследовать ландшафт возможностей. Знание того, где находится объект в пространстве поиска - в данном случае последовательностей (строк) - определенно может помочь в его поиске (например, 9 , 10 ).

«Надежность» отражает природу ландшафтов и легкость, с которой их можно эффективно искать.

Еще одна проблема, которая усложняет навигацию по этим ландшафтам - и действительно можно представить себе их как естественные ландшафты - в том, что они труднопроходимые, в том смысле, что для достижения более крупного пика «путешествие» может означать спуск до уровня («приспособленности») ниже, чем тот, на котором он находится сейчас.Эта концепция фитнес-ландшафта, конечно же, является метафорой Сьюэлла Райта 17 и означает, что обычно необходимо исследовать менее подходящие решения на пути к открытию «лучшего» решения (reculer pour mieux sauter 18 ). В одном хорошо выполненном примере in silico почти для одной трети улучшенных вариантов требовалось это 19 .

Существует очень большое количество количественных показателей (суммированных в ссылке 20) для того, что означает «жесткость», но в целом, если небольшие изменения положения в ландшафте соответствуют небольшим изменениям в приспособленности, тогда как большие изменения положения ландшафта соответствуют при больших изменениях пригодности ландшафт можно считать плавным.С другой стороны, если две величины (приспособленность и расстояние) по существу не коррелируют, ландшафт будет неровным. Основная проблема заключается в том, что мы обычно знаем только крошечную часть ландшафта (а эффективная структура ландшафта зависит от того, какие виды движений возможны). Из того, что мы знаем, например, из-за существования дивергентной эволюции большинство ландшафтов являются сравнительно труднопроходимыми, со многими синергетическими или эпистатическими взаимодействиями (т.е.значение одной переменной может сильно влиять на оптимальное значение другой переменной).В одном из наших примеров, рассматривая эффект изменения параметров в простой модели 21 , 22 колебаний в сигнальном пути NF-κB, влияние одного параметра может быть качественно различным (вызывая частота колебаний повышается или понижается) в зависимости от значения второго параметра 23 . Это является прямым следствием нелинейности большинства уравнений биохимической кинетической скорости 24 вместе с существованием петель обратной связи.

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

Эвристические подходы к NP-трудным задачам оптимизации

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

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

Эволюционные вычисления и генетическое программирование

Область, которая довольно ясно высказывалась в своем взгляде на то, что решение многих научных и технологических проблем следует рассматривать как проблему комбинаторной оптимизации, - это проблема эволюционных вычислений (см., Например, 6 , 28 - 31 ).

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

Существует много специфических типов советников. Одна из причин этого заключается в том, что можно доказать (так называемая теорема «без бесплатного обеда»), что «лучший» полностью зависит от структуры рассматриваемого набора данных 32 , 33 , без каких-либо быть лучше любых других, включая случайный поиск, когда он интегрирован по всем возможным наборам данных.Однако мы рассматриваем советников как надмножество основных видов стратегии, которые могут быть приняты для навигации по этим очень большим пространствам поиска потенциальных ответов в надежде найти те, которые работают адекватно. Часто априори неизвестно, какой алгоритм может быть лучшим для какого набора данных. Может быть полезно попробовать несколько. Известно, что объединение даже «слабых» алгоритмов намного эффективнее, чем выбор одного «сильного» алгоритма 34 .

Оптимизация для нескольких целей

До сих пор неявно предполагалось, что оптимизация только одного выхода (например,грамм. активность фермента или продуктивность процесса ферментации). На практике для большинства проблем характерно то, что есть несколько вещей, которые можно было бы оптимизировать. Следовательно, есть компромиссы: решение, оптимальное для одной цели, может быть неоптимальным для другой. Они известны как задачи многокритериальной оптимизации, и некоторые из них описаны в справочных материалах. 35 , 36 , а некоторые из алгоритмов, которые использовались для их атаки, можно найти в соответствующих обзорах (например,грамм. 37 ).

Эти компромиссы обычно выражаются в терминах так называемого фронта Парето или «недоминируемого» фронта, представленного решениями, которые являются лучшими с точки зрения по крайней мере одной цели и не хуже с точки зрения любой другой. Оптимальный по Парето набор решений (индивидуумов) состоит из всех тех решений, которые невозможно улучшить в какой-либо цели без одновременного ухудшения какой-либо другой цели, и схематично проиллюстрирован на.

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

Большинство примеров, которые мы здесь рассматриваем, также неявно многоцелевые по своей природе, например с точки зрения оптимизации белка мы могли бы пожелать, чтобы он имел очень высокий k cat , но также выжил при повышенных температурах или в высоких концентрациях растворителя (выбор которого сам по себе является комбинаторной и многоцелевой проблемой 38 ), что само по себе может привести к медленному изменению значения k cat во времени.Очень распространенный набор проблем представлен теми, для которых «лучшее» решение также является более дорогостоящим, и поэтому стоимость обычно является одним из критериев (многоцелевой) целевой функции. Обычно выбор решений с фронта Парето делается по воле экспериментатора, и по этой причине мы в значительной степени игнорируем мультиобъективизм, поскольку мы сосредоточены на комбинаторной проблеме. Однако стоит обратить внимание на то, что чем больше целей включается, тем ближе поиск к случайному поиску.

Некоторые конкретные примеры задач комбинаторной оптимизации в биологии

Приведенный выше пример аптамера формально эквивалентен любой проблеме «направленной эволюции белка», предсказания структуры белка или фолдинга. Кроме того, стоит выделить следующие проблемы, которые лучше всего решить с помощью комбинаторной оптимизации: открытие лекарств; оптимизация коктейлей из известных препаратов; определение целей для метаболической инженерии. Я игнорирую другие довольно общие NP-сложные проблемы, такие как «кластеризация», когда может быть много объектов и переменных (например,грамм. 39 - 41 ).

Открытие лекарств и химикатов

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

Однако из-за множественной валентности углерода и его способности связываться со многими другими многовалентными атомами, такими как N и O и одновалентными H, Cl, Br и F, количество возможных молекул с данным числом таких атомов огромен - десятки миллионов даже для молекул с молекулярной массой ниже 160 Да и числом атомов C, N, O и F до 11 43 без учета стереоизомеров.Реймонд и его коллеги недавно расширили анализ до ок. 977 миллионов соединений с 13 атомами C, H, N, O, S и Cl 44 (см. Http://www.dcb-server.unibe.ch/groups/reymond/). Некоторые из этих соединений были созданы, и с реалистичным объемом открытия лекарств, возможно, 10 60 соединений 45 , большинство из них не будет. Действительно, даже самые простые гетероциклы вообще не исследованы.

Новым решением этой проблемы является «эволюция» молекул с желаемыми свойствами путем объединения фрагментов, которые сами по себе не являются оптимальными - так называемое открытие лекарств (или свинца) на основе фрагментов (например,грамм. 46 ). В этом случае открытие происходит аналогично описанному выше эволюционному поиску, когда каждый член популяции представляет собой молекулу, представляющую решение-кандидат. Пригодность (например, сила связывания) различных растворов оценивается, а затем растворы мутируют и / или рекомбинируют, чтобы получить разные и часто более крупные молекулы (поскольку они будут иметь больше атомов, которые могут связываться с мишенью). В каждом поколении обычно используются всего несколько сотен молекул, а не десятки тысяч или даже миллионы, имеющиеся в библиотеках фармацевтических препаратов.Возможные решения могут быть проверены фактически путем выполнения количественного анализа структуры-активности на каждом этапе, то есть предоставления компьютерной модели, которая производит сопоставление между известными структурами и их пригодностью, а затем оценивает качество потенциальных отведений in silico. Это значительно упрощается за счет онлайн-списков огромного количества коммерчески доступных молекул, например в базе данных ZINC http://zinc.docking.org/, выбранные из виртуального скрининга подмножества могут быть протестированы экспериментально.(Аналогичный подход с использованием виртуального скрининга аптамеров оказался чрезвычайно успешным 9 .) Также обратите внимание, что может потребоваться оптимизация других аспектов, например вероятность того, что такие молекулы будут субстратами для клеточных переносчиков лекарств (например, 47 - 49 ).

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

Оптимизация нескольких лекарств или целевых лекарств

Растет понимание того, что для того, чтобы быть эффективными (как по отдельности, так и в комбинации), фармацевтические препараты должны воздействовать на несколько этапов одновременно 50 - 52 . Это частично следует из того факта, что (i) поток через сети очень редко контролируется одним шагом, поскольку это системное свойство 53 , и (ii) биологические системы имеют тенденцию развиваться в сторону устойчивости (если модифицируют только одну параметр вызывает смерть, тогда эволюция вскоре делает выбор против такой клетки или организма).Однако в целом у нас по-прежнему отсутствуют хорошие модели биохимических сетей 54 , 55 , по которым можно было бы рассуждать.

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

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

Оптимизация таких смесей, по сути, аналогична оптимизации компонентов среды для повышения продуктивности ферментации для биотехнологии, и Weuster-Botz и его коллеги разработали такую ​​стратегию с большим эффектом (например.грамм. 57 ). То же самое относится к оптимизации любого «рецепта» или процесса, который имеет ряд возможных компонентов и этапов, природа и / или свойства которых могут варьироваться.

Оптимизация манипуляций с ферментами для метаболической инженерии или синтетической биологии

Оптимизация биотехнологических процессов в современную эпоху, вероятно, лучше всего рассматривается как включение ферментов, которые больше всего нуждаются в модификации, а затем их индивидуальная оптимизация путем направленной эволюции 58 .Нахождение простой комбинации ферментов, которыми можно манипулировать для улучшения желаемого свойства, формально эквивалентно поиску (небольшого) набора целевых лекарственных средств и, безусловно, является проблемой комбинаторной оптимизации, и действительно кажется, что небольшое количество тщательно выбранных цели часто могут иметь большие эффекты (например, 14 , 59 - 61 ). Исторически нам не хватало как необходимых моделей 53 , так и методов молекулярной биологии, и прогресс был медленным и эмпирическим 62 .В частности, если нам нужно манипулировать только четырьмя ферментами из, скажем, 1000 (типичное число для микробных метаболических сетей 15 , 63 , 64 ), количество комбинаций составляет около 41 миллиарда, что несколько за пределами типичных возможностей влажной лаборатории. Однако такое число можно проверить in silico за сравнительно короткое время (и, как и большинство подобных анализов 20 , тест можно идеально распараллелить). Это объясняет необходимость иметь полуприличную модель in silico, с которой можно было бы работать и делать прогнозы.

В особенно хорошем примере из «белой» или промышленной биотехнологии это именно то, что Санг Юп Ли и его коллеги сделали 14 для улучшения (значительного) производства валина в Escherichia coli , впервые изучив in silico ∼10 8 область поиска, чтобы найти три фермента из ок. 1000, которыми нужно манипулировать, а затем делать это экспериментально. В целом аналогичные стратегии оказались эффективными для множества других продуктов 58 .

Роль компьютеров в научных открытиях

Рассмотрение многих или большинства научных проблем как комбинаторных следует рассматривать как подмножество более широкой области, которая стремится формализовать использование компьютеров или «искусственного интеллекта» в научных открытиях ( е.грамм. 26 , 65 , 66 ), причем показатель того, являются ли такие результаты «конкурентоспособными для человека» 67 является по крайней мере одним из критериев успеха. В самом деле, каждый эксперимент состоит из различных этапов с разными свойствами, которые можно изменять независимо, и поэтому проектирование эксперимента является комбинаторной проблемой.

Обучение может осуществляться посредством ассоциации шаблонов

Настоящий вид принципиального подхода к рассуждению обычно включает в себя некоторый вид анализа ассоциаций или сопоставления с образцом, основанный на методах интеллектуального анализа данных, и его следует рассматривать как своего рода индуктивное рассуждение 68 в парные данные используются в качестве входных данных для обучающей системы, из которой, как ожидается, появятся более общие правила 69 .Начиная с системы DENDRAL 28 - 31 , которая неявно стремилась изучить правила молекулярного разложения в масс-спектрометрах и тем самым идентифицировать молекулы по их масс-спектрам («от спектра к структуре» 74 ), был предложен ряд компьютерных систем научных открытий. Можно процитировать пару обзоров (например, 65 , 75 ), и я перечислю некоторые из конкретных систем в. Некоторые из них являются итеративными и даже замкнутыми (не требующими вмешательства человека), в результате чего результаты анализа приводят к предложению и проведению следующего «мокрого» эксперимента в серии (активное обучение - см. Выше) в качестве системы учится оптимизировать то, что пытается обнаружить.

Таблица 1

Некоторые из систем, которые были разработаны для автоматизации процесса научного мышления

319 named / Eureqa
Имя Область деятельности Избранные ссылки
Dendral (и мета-дендральный) Масс-спектрометрическая идентификация молекул 70, 72, 73
Бекон Термодинамика, теплоемкость и тепловой поток 76
Фаренгейт Электрохимия контроль химических реакций 78– 80
Робот-ученый Метаболизм дрожжей 27, 28–31
Робот-хроматограф Хроматографическая оптимизация 9034 85, 86
Dynamics 87, 88 9031 9
Clade Aptamer evolution 9–11,75,89

Роль научной литературы и онтологий

Средства сбора, инкапсуляции и передачи знаний лежат в основе науки, и с вычислительной точки зрения литература остается ресурсом с несовершенным доступом 90 , 91 .Непросто даже ответить на вопрос «Какую статью мне лучше всего читать дальше?». Что еще более важно, это общая концепция семантики, которая отличает необработанный текст от текста со смыслом (например, 28 - 31 ). В настоящее время считается, что использование троек RDF для простых отношений, а для более сложных - более полноценных онтологий, из которых, вероятно, наиболее известна Gene Ontology 96 (http://www.geneontology.org/). для биологов - это наиболее эффективный способ наполнить текст смыслом в рамках общей вычислительной области, известной как интеллектуальный анализ текста (например, интеллектуальный анализ текста).грамм. 92 , 97 ). Поскольку многие знания можно закодировать в виде графиков, язык разметки системной биологии 98 , который предназначен для их принципиального описания, кажется естественным средством сделать это 99 , тем более что он может напрямую ссылаться на свою собственную онтологию ( например, 15 , 100 - 102 ). Это частично предполагает поиск литературы, которая предоставляет доказательств для конкретного пути; обратная проблема («учитывая литературу, проложи путь») является важным направлением, но значительно труднее.

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

Байесовский анализ научных рассуждений и научных открытий

Сравнительно недавним достижением (например, 68 , 103 - 108 ) является признание того, что применение методов байесовского вывода обеспечивает простой и естественные средства понимания относительной роли старых и новых свидетельств в развитии теории и убеждений.Конечно, вряд ли можно отрицать, что наука и другие начинания включают непрерывный ряд выводов, основанных на неполных данных. В классической форме (например, 109 - 113 ) правило Байеса (точнее правило Байеса, Прайса и Лапласа 107 ) просто утверждает, что новый набор наблюдений («свидетельство») B относительно двух событий A и B дополняет нашу веру в конкретную точку зрения A в соответствии с формулой Байеса

, где P ( A | B ) является 'апостериорная' или условная вероятность A при B , P ( B | A ) - это условная вероятность A при B (также известная как вероятность), P ( A ) - это `` априорная '' или априорная вероятность A при отсутствии дополнительных знаний, полученных путем измерения B , а P ( B ) - это априорная (или предельная) вероятность Б .(Во многих экспериментальных установках A следует рассматривать как «причину» экспериментально наблюдаемого «эффекта» B .)

Определение апостериорных вероятностей

Чтобы увидеть, как это работает, представьте себе членов двух племен. (назовем их ястребами и джетами), населяющие остров. Ястребов в 1,5 раза больше, чем самолетов. Все Ястребы носят синие туники, но 50% Джетсов носят синие туники и 50% носят коричневые туники. Если вы встретите человека в синей тунике, какова вероятность того, что он Джет?

Если P ( A ) является априорной вероятностью быть Jet, она равна 0.4. P ( B ), априорная вероятность ношения синего цвета составляет 0,6 + (0,5 × 0,4) = 0,8. P ( B | A ), вероятность того, что вы наденете синий, если вы Джет, составляет 0,5. Таким образом, применение формулы Байеса дает запрашиваемую вероятность P ( A | B ), вероятность того, что вы являетесь Джетом при условии, что вы носите синий цвет, как 0,5 × 0,4 / 0,8 = 0,25. Эти двоичные результаты можно представить в виде таблицы, где доля «голубых джетов» и «всего синего» явно равна 20/80 = 0.25.

Коричневый 919 Итого
Hawks Jets Всего
Синий 60 20 80
60 40 100

Явные преимущества знания априорных значений

Байесовский анализ также позволяет принимать во внимание априорные факторы, чего не делает так называемая частотная статистика.В двоичных результатах (истина / ложь) в диагностических тестах, например. для болезни у нас может быть четыре результата: истинно положительные (TP), ложноположительные (FP), истинно отрицательные (TN) и ложно отрицательные (FN). Чувствительность теста (см., Например, 114 ) описывает его способность обнаруживать положительные результаты (т. Е. У испытуемого есть заболевание, для которого тест является диагностическим):

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

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

Если A - это болезнь, а B - положительный результат, применение формулы Байеса дает

и P ( B ) = 0,99 × 0,01 + 0,99 × 0,01 = 0,0198, поэтому P ( A | B ) вероятность заболевания при положительном результате равна 0.99 × 0,01 / 0,0198, что составляет всего 0,5. Таким образом, несмотря на очень высокую чувствительность и специфичность диагностики, очень низкая распространенность болезни (предшествующая) означает, что на самом деле тест (и, вероятно, любой индивидуальный тест…) довольно плохой.

Эквивалентная таблица (с округлением до целых чисел для 1000 тестов) выглядит следующим образом:

3
Заболевший Незаболевший Всего
Прогнозируемое заболевание 10
Заболевание не предсказано 0 980 98
Всего 10 990 1000

A Bayesian

новые доказательства изменения Недавно байесовское мышление было применено с точки зрения того, как новые данные меняют нашу степень веры в что-либо, как часть научного процесса.Как недавно сформулировали Tenenbaum et al. 108 ,

«Фоновые знания кодируются через ограниченное пространство гипотез H о возможных значениях скрытых переменных, возможных мировых структурах, которые могли бы объяснить наблюдаемые данные. Более детальное знание проявляется в «априорной вероятности» P ( h ), степени веры учащегося в конкретную гипотезу h до наблюдений (или независимо от них). Правило Байеса обновляет априорные вероятности до «апостериорных вероятностей» P ( h | d ) при условии наличия наблюдаемых данных d :

Апостериорная вероятность пропорциональна произведению априорной вероятности и правдоподобия P ( d | h ), измеряя, насколько ожидаемые данные соответствуют гипотезе h по сравнению со всеми другими гипотезами h ′ в H .”

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

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

Это, кажется, естественным образом переводится в признание того, что многие научные проблемы являются комбинаторными проблемами с большим, но эффективно ограниченным пространством поиска, и по мере того, как мы улучшаем наши знания о пространстве поиска, мы тем самым увеличиваем нашу степень веры в любые более общие свойства этого поиска. пробел (в предыдущем примере отношение последовательность-действие, представленное в исх.9 через так называемый «случайный лес». В другом примере байесовские методы могут быть успешно применены для анализа и ранжирования моделей сетевой или системной биологии, которые начинаются с наблюдаемых и ищут основные параметры или причины (например, 28 - 31 ).

Заключительные замечания

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

С этой целью я привел серию примеров, в которых области научных проблем легко распознаются как задачи комбинаторной оптимизации, где очень большое пространство поиска допускает значительно меньшее пространство решений «адекватных» ответов.Если принять, что любая научная проблема имеет количество решений, намного меньшее, чем «возможное» количество экспериментов, которые могли бы их искать, то то же самое верно и в более общем плане. Поскольку поиск комбинаторного ландшафта с помощью вычислений (то есть in silico) значительно быстрее и эффективнее, чем выполнение `` реальных '' экспериментов в каждой точке, очевидно, что нам нужны гораздо более эффективные модели биологии, чем те, которые есть сегодня 54 . Это побуждает нас создавать и анализировать их как часть повторяющегося процесса научных открытий.

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

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

Глоссарий

FP
EA эволюционный алгоритм
FN ложноотрицательных
NP неполиномиальных
FP
TP истинно положительных результатов

Ссылки

1.Алон У. Как выбрать хорошую научную задачу. Mol Cell. 2009. 35: 726–8. [PubMed] [Google Scholar] 2. Melzer S, Lens F, Gennen J, Vanneste S и др. Гены времени цветения модулируют детерминированность меристемы и форму роста у Arabidopsis thaliana . Нат Жене. 2008; 40: 1489–92. [PubMed] [Google Scholar] 3. Келл ДБ. Селекция сельскохозяйственных культур с глубокими корнями: их роль в устойчивом связывании углерода, питательных веществ и воды. Энн Бот. 2011; 108: 407–18. [Бесплатная статья PMC] [PubMed] [Google Scholar] 4. Гарей М., Джонсон Д.Компьютеры и непоколебимость: руководство по теории NP-полноты. Сан-Франциско: Фриман; 1979. [Google Scholar] 5. Пирс Н.А., Уинфри Э. Дизайн белков NP-жесткий. Protein Eng. 2002; 15: 779–82. [PubMed] [Google Scholar] 6. Михалевич З., Фогель ДБ. Как это решить: современная эвристика. Гейдельберг: Springer-Verlag; 2000. [Google Scholar] 8. Эллингтон А.Д., Шостак Дж. В.. In vitro отбор молекул РНК, связывающих определенные лиганды. Природа. 1990; 346: 818–22. [PubMed] [Google Scholar] 9.Knight CG, Platt M, Rowe W., Wedge DC и др. Эволюция ДНК-аптамеров на основе массивов позволяет моделировать явный ландшафт соответствия последовательности. Nucleic Acids Res. 2009; 37: e6. [Бесплатная статья PMC] [PubMed] [Google Scholar] 10. Роу В., Платт М., Клин Д., Дэй П.Дж. и др. Анализ полного пейзажа сродства ДНК к белку. Интерфейс J R Soc. 2010; 7: 397–408. [Бесплатная статья PMC] [PubMed] [Google Scholar] 11. Роу В., Платт М., Ведж Д.К., Дэй ПДЖР и др. Конвергентная эволюция к аптамеру наблюдается в небольших популяциях на ДНК-микрочипах.Phys Biol. 2010; 7: 036007. [PubMed] [Google Scholar] 12. Барроу Дж. Д., Силк Дж. Левая рука творения: происхождение и эволюция расширяющейся Вселенной. Лондон: Пингвин; 1995. [Google Scholar] 13. Мур Дж. К., Джин Х. М., Кучнер О., Арнольд Ф. Х. Стратегии эволюции функции белка in vitro : эволюция ферментов путем случайной рекомбинации улучшенных последовательностей. J Mol Biol. 1997. 272: 336–47. [PubMed] [Google Scholar] 14. Пак Дж. Х., Ли К. Х., Ким Т. Я., Ли Си. Метаболическая инженерия Escherichia coli для производства L-валина на основе анализа транскриптома и моделирования нокаута гена in silico .Proc Natl Acad Sci USA. 2007; 104: 7797–802. [Бесплатная статья PMC] [PubMed] [Google Scholar] 15. Herrgård MJ, Swainston N, Dobson P, Dunn WB и др. Консенсусная метаболическая сеть дрожжей, полученная на основе общественного подхода к системной биологии. Nature Biotechnol. 2008; 26: 1155–60. [Бесплатная статья PMC] [PubMed] [Google Scholar] 16. Мур Дж. Х., Ассельбергс Ф. В., Вильямс С. М.. Проблемы биоинформатики для полногеномных ассоциативных исследований. Биоинформатика. 2010; 26: 445–55. [Бесплатная статья PMC] [PubMed] [Google Scholar] 17. Райт С.Роли мутации, инбридинга, скрещивания и отбора в эволюции. В: Джонс Д.Ф., редактор. Proc. Шестой Int. Конф. Генетика. Остин, Техас: Американское генетическое общество; 1932. С. 356–66. [Google Scholar] 18. Винсон МК, Келл ДБ. Идущие места: принудительная и естественная молекулярная эволюция. Trends Biotechnol. 1996; 14: 323–5. [PubMed] [Google Scholar] 19. Ленски Р.Э., Офриа К., Пеннок Р.Т., Адами К. Эволюционное происхождение сложных функций. Природа. 2003. 423: 139–44. [PubMed] [Google Scholar] 20. Клин Д., Келл ДБ.Быстрое предсказание оптимального размера популяции в генетическом программировании с использованием новой корреляции между генотипом и приспособленностью. В: Райан С., Кейзер М., редакторы. GECCO 2008. Нью-Йорк, Нью-Йорк: ACM; 2008. С. 1315–22. [Google Scholar] 21. Ихекваба AEC, Брумхед Д.С., Гримли Р., Бенсон Н. и др. Анализ чувствительности параметров, контролирующих осцилляторную передачу сигналов в пути NF-κB: роль IKK и IκBα Syst Biol. 2004; 1: 93–103. [PubMed] [Google Scholar] 22. Nelson DE, Ihekwaba AEC, Elliott M, Gibney CA и др. Колебания в передаче сигналов NF-κB контролируют динамику экспрессии генов.Наука. 2004. 306: 704–8. [PubMed] [Google Scholar] 23. Ихекваба AEC, Брумхед Д.С., Гримли Р., Бенсон Н. и др. Синергетический контроль колебаний сигнального пути NF-κB. IEE Syst Biol. 2005; 152: 153–60. [PubMed] [Google Scholar] 24. Мендес П., Келл ДБ. Нелинейная оптимизация биохимических путей: приложения к метаболической инженерии и оценке параметров. Биоинформатика. 1998. 14: 869–83. [PubMed] [Google Scholar] 25. Берштейн С., Сегал М., Бекерман Р., Токурики Н. и др. Связь между устойчивостью и эпистазом формирует фитнес-ландшафт случайно дрейфующего белка.Природа. 2006; 444: 929–32. [PubMed] [Google Scholar] 26. Сакс Дж., Велч В., Митчелл Т., Винн Х. Дизайн и анализ компьютерных экспериментов (с обсуждением) Stat Sci. 1989. 4: 409–35. [Google Scholar] 27. Кинг Р. Д., Уилан К. Э., Джонс Ф. М., Рейзер ПГК и др. Генерация функциональной геномной гипотезы и экспериментирование ученым-роботом. Природа. 2004; 427: 247–52. [PubMed] [Google Scholar] 28. Бек Т., Фогель Д. Б., Михалевич З. Справочник по эволюционным вычислениям. Оксфорд: Издательство IOP / Издательство Оксфордского университета; 1997 г.[Google Scholar] 29. Корн Д., Дориго М., Гловер Ф. Новые идеи в оптимизации. Лондон: Макгроу Хилл; 1999. [Google Scholar] 30. Кауфман С., Лобо Дж., Макреди РГ. Оптимальный поиск в технологическом ландшафте. J Econ Behav Organ. 2000; 43: 141–66. [Google Scholar] 31. Goldberg DE. Дизайн инноваций: уроки компетентных генетических алгоритмов и для них. Бостон: Клувер; 2002. [Google Scholar] 32. Рэдклифф, штат Нью-Джерси, Полицейский Сурри. Фундаментальные ограничения алгоритмов поиска: эволюционные вычисления в перспективе. Компьютерные науки сегодня.1995; 1995: 275–91. [Google Scholar] 33. Вольперт Д.Х., Макреди РГ. Никаких теорем о бесплатном обеде для оптимизации. IEEE Trans Evol Comput. 1997; 1: 67–82. [Google Scholar] 34. Хасти Т., Тибширани Р., Фридман Дж. Элементы статистического обучения: интеллектуальный анализ данных, вывод и прогнозирование. Берлин: Springer-Verlag; 2001. [Google Scholar] 35. Хэндл Дж., Келл Д.Б., Ноулз Дж. Оптимизация нескольких целей в биоинформатике и вычислительной биологии. IEEE Trans Comput Biol Bioinformatics. 2007; 4: 279–92. [PubMed] [Google Scholar] 36.Ноулз Дж., Корн Д., Деб К. Решение многоцелевых задач из природы: от концепций к приложениям. Гейдельберг: Спрингер; 2008. [Google Scholar] 37. Ноулз Дж., Корн Д., Деб К. Решение многоцелевых задач из природы. Берлин: Springer; 2008. [Google Scholar] 38. Солтер Г.Дж., Келл ДБ. Выбор растворителя для биотрансформации целых клеток в органических средах. CRC Crit Rev Biotechnol. 1995; 15: 139–77. [PubMed] [Google Scholar] 39. Эверит Б.С. Кластерный анализ. Лондон: Эдвард Арнольд; 1993. [Google Scholar] 40.Келл ДБ, Король Р.Д. Об оптимизации классов для назначения неопознанных рамок чтения в программах функциональной геномики: необходимость машинного обучения. Trends Biotechnol. 2000; 18: 93–8. [PubMed] [Google Scholar] 41. Хэндл Дж., Ноулз Дж., Келл ДБ. Вычислительная кластерная валидация в постгеномном анализе данных. Биоинформатика. 2005; 21: 3201–12. [PubMed] [Google Scholar] 42. Лисон П.Д., Спрингторп Б. Влияние концепций, подобных лекарствам, на принятие решений в медицинской химии. Nat Rev Drug Discovery.2007; 6: 881–90. [PubMed] [Google Scholar] 43. Финк Т., Реймонд Ж.Л. Виртуальное исследование химической вселенной до 11 атомов C, N, O, F: сборка 26,4 миллиона структур (110,9 миллиона стереоизомеров) и анализ новых кольцевых систем, стереохимии, физико-химических свойств, классов соединений и открытия лекарств. Модель J Chem Inf. 2007; 47: 342–53. [PubMed] [Google Scholar] 44. Blum LC, van Deursen R, Reymond JL. Визуализация и подмножества базы данных химической вселенной GDB-13 для виртуального просмотра.J. Comput Aided Mol Des. 2011; 25: 637–47. [PubMed] [Google Scholar] 45. Бохачек Р.С., Макмартин К., Гуида В. Искусство и практика дизайна лекарств на основе структуры: перспектива молекулярного моделирования. Med Res Rev.1996; 16: 3–50. [PubMed] [Google Scholar] 46. Хайдук П.Дж., Грир Дж. Десятилетие разработки лекарств на основе фрагментов: стратегические достижения и извлеченные уроки. Nat Rev Drug Discovery. 2007; 6: 211–9. [PubMed] [Google Scholar] 47. Добсон П.Д., Келл Д.Б. Опосредованное переносчиком клеточное поглощение фармацевтических препаратов: исключение или правило.Nat Rev Drug Discovery. 2008; 7: 205–20. [PubMed] [Google Scholar] 48. Добсон П.Д., Патель Й., Келл Д.Б. «Метаболитоподобность» как критерий при разработке и выборе библиотек фармацевтических препаратов. Диск с наркотиками сегодня. 2009; 14: 31–40. [PubMed] [Google Scholar] 49. Келл Д. Б., Добсон П. Д., Оливер С. Г.. Транспортировка фармацевтических препаратов: проблемы и последствия того, что он, по сути, опосредован только носителями. Диск с наркотиками сегодня. 2011; 16: 704–14. [PubMed] [Google Scholar] 50. Циммерманн Г.Р., Лехар Дж., Кейт СТ. Многоцелевое лечение: когда целое больше суммы частей.Открытие наркотиков сегодня. 2007; 12: 34–42. [PubMed] [Google Scholar] 51. Хопкинс АЛ. Сетевая фармакология: новая парадигма в открытии лекарств. Nat Chem Biol. 2008; 4: 682–90. [PubMed] [Google Scholar] 52. Small BG, McColl BW, Allmendinger R, Pahle R и др. Эффективное открытие противовоспалительных комбинаций малых молекул с использованием эволюционных вычислений. Nat Chem Biol. 2011; 7: 902–8. [Бесплатная статья PMC] [PubMed] [Google Scholar] 53. Kell DB, Westerhoff HV. Теория метаболического контроля: ее роль в микробиологии и биотехнологии.FEMS Microbiol Rev. 1986; 39: 305–20. [Google Scholar] 54. Келл ДБ. Виртуальный человек: к глобальной системной биологии многомасштабных распределенных моделей биохимических сетей. IUBMB Life. 2007. 59: 689–95. [PubMed] [Google Scholar] 55. Тиле I, Палссон Бё. Протокол для создания высококачественной метаболической реконструкции в масштабе генома. Nat Protoc. 2010; 5: 93–121. [Бесплатная статья PMC] [PubMed] [Google Scholar] 56. Фила Дж. Д., Кортес Дж., Даксбери П. М., Пьермарокки С. и др. Системные подходы и алгоритмы открытия комбинаторных методов лечения.Wiley Interdiscip Rev Syst Biol Med. 2010; 2: 181–93. [PubMed] [Google Scholar] 57. Гавел Дж., Линк Х., Хофингер М., Франко-Лара Э. и др. Сравнение генетических алгоритмов экспериментальной многоцелевой оптимизации на примере дизайна среды для цианобактерий. Biotechnol J. 2006; 1: 549–55. [PubMed] [Google Scholar] 58. Ли Дж. У., Ким Т. Ю., Чан Ю. С., Чой С. и др. Системная метаболическая инженерия для химикатов и материалов. Trends Biotechnol. 2011; 29: 370–8. [PubMed] [Google Scholar] 59. Томас Х, Томас Х. М., Угэм Х.Годичность, многолетность и гибель клеток. J Exp Bot. 2000; 51: 1781–8. [PubMed] [Google Scholar] 60. Патил К.Р., Роча И., Ферстер Дж., Нильсен Дж. Эволюционное программирование как платформа для метаболической инженерии in silico . BMC Bioinformatics. 2005; 6: 308. [Бесплатная статья PMC] [PubMed] [Google Scholar] 61. Уорнер Дж. Р., Ридер П. Дж., Каримпур-Фард А., Вудрафф Л. Б. и др. Быстрое профилирование микробного генома с использованием смесей олигонуклеотидов со штрих-кодом. Nat Biotechnol. 2010. 28: 856–62. [PubMed] [Google Scholar] 62.Kell DB, van Dam K, Westerhoff HV. Контрольный анализ роста и продуктивности микробов. Symp Soc Gen Microbiol. 1989; 44: 61–93. [Google Scholar] 63. Feist AM, Herrgard MJ, Thiele I, Reed JL и др. Реконструкция биохимических сетей у микроорганизмов. Nat Rev Microbiol. 2009; 7: 129–43. [Бесплатная статья PMC] [PubMed] [Google Scholar] 64. Добсон П.Д., Смоллбоун К., Джеймсон Д., Симеонидис Э. и др. Дальнейшие разработки в направлении модели метаболизма дрожжей в масштабе генома. BMC Syst Biol. 2010; 4: 145. [Бесплатная статья PMC] [PubMed] [Google Scholar] 65.Лэнгли П., Саймон Х.А., Брэдшоу Г.Л., Зитков Дж. М.. Научное открытие: вычислительное исследование творческих процессов. Кембридж, Массачусетс: MIT Press; 1987. [Google Scholar] 66. Охотник А., Лю WR. Обзор формализмов для представления и обоснования научных знаний. Knowl Eng Rev.2010; 25: 199–222. [Google Scholar] 67. Koza JR, Keane MA, Streeter MJ, Mydlowec W. и др. Генетическое программирование: рутинный человеческий конкурентный машинный интеллект. Нью-Йорк: Клувер; 2003. [Google Scholar] 68. Чалмерс А.Ф.Что такое наука? Оценка сущности и состояния науки и ее методов. Мейденхед: Издательство Открытого университета; 1999. [Google Scholar] 69. Келл ДБ, Оливер С.Г. Вот доказательства, а какова гипотеза? Дополнительные роли индуктивной науки и науки, основанной на гипотезах, в постгеномную эпоху. BioEssays. 2004. 26: 99–105. [PubMed] [Google Scholar] 70. Бьюкенен Б.Г., Фейгенбаум Е.А. DENDRAL и META-DENDRAL: их прикладные аспекты. Artif Intell. 1978; 11: 5–24. [Google Scholar] 72.Фейгенбаум Э.А., Бьюкенен Б.Г. DENDRAL и META-DENDRAL: истоки систем знаний и приложений экспертных систем. Artif Intell. 1993; 59: 223–40. [Google Scholar] 73. Линдси Р.К., Бьюкенен Б.Г., Фейгенбаум Е.А., Ледерберг Дж. ДЕНДРАЛ - пример первой экспертной системы для формирования научных гипотез. Artif Intell. 1993; 61: 209–61. [Google Scholar] 74. Фаррелли К., Келл Д. Б., Ноулз Дж. Предсказание молекулярной структуры с использованием оптимизации муравьиной колонии: предварительное исследование. LNCS. 2008; 5217: 120–31. [Google Scholar] 75.Ноулз Дж. Эволюционная многокритериальная оптимизация с обратной связью. IEEE Comput Intell M. 2009; 4: 77–91. [Google Scholar] 76. Брэдшоу Г.Ф., Лэнгли П.В., Саймон Х.А. Изучение научных открытий с помощью компьютерного моделирования. Наука. 1983; 222: 971–5. [PubMed] [Google Scholar] 77. Ytkow JM, Zhu J, Hussam A. Автоматическое открытие в химической лаборатории. В: Dietterich T, Swartout W, редакторы. Proc. Восьмой нац. Конф. на Артиф. Интеллект. Бостон: AAAI Press; 1990. С. 889–94. [Google Scholar] 78. Джадсон Р.С., Рабиц Х.Обучение лазерам управлению молекулами. Phys Rev Lett. 1992; 68: 1500–3. [PubMed] [Google Scholar] 79. Даниэль С., Фулл Дж., Гонсалес Л., Лупулеску С. и др. Расшифровка динамики реакции, лежащей в основе оптимального управления лазерными полями. Наука. 2003; 299: 536–9. [PubMed] [Google Scholar] 81. Уилан К.Э., король Р.Д. Интеллектуальное программное обеспечение для автоматизации лабораторий. Trends Biotechnol. 2004; 22: 440–5. [PubMed] [Google Scholar] 82. Кинг Р.Д., Роуленд Дж., Оливер С.Г., Янг М. и др. Автоматизация науки. Наука. 2009. 324: 85–9.[PubMed] [Google Scholar] 83. Кинг Р.Д., Роуленд Дж., Обри В., Лиаката М. и др. Робот-ученый Адам. Компьютер. 2009; 42: 46–54. [Google Scholar] 85. О'Хаган С., Данн В. Б., Браун М., Ноулз Дж. Д. и др. Закрытая, многокритериальная оптимизация аналитического оборудования: газовая хроматография-времяпролетная масс-спектрометрия метаболомов сыворотки крови человека и дрожжевых ферментаций. Anal Chem. 2005; 77: 290–303. [PubMed] [Google Scholar] 86. О'Хаган С., Данн В. Б., Бродхерст Д., Уильямс Р. и др. Закрытая, многоцелевая оптимизация двумерной газовой хроматографии (GCxGC-tof-MS) для метаболомики сыворотки.Anal Chem. 2007. 79: 464–76. [PubMed] [Google Scholar] 88. Шмидт М., Липсон Х. Извлечение естественных законов свободной формы из экспериментальных данных. Наука. 2009. 324: 81–5. [PubMed] [Google Scholar] 89. Роу В., Клин Д.К., Платт М., Келл Д.Б. и др. Прогностические модели производительности популяции на реальных ландшафтах биологической пригодности. Биоинформатика. 2010; 26: 2125–42. [PubMed] [Google Scholar] 90. Халл Д., Петтифер С.Р., Келл Д.Б. Размораживание цифровой библиотеки: библиографические инструменты для Интернета следующего поколения. PLoS Comput Biol.2008; 4: e1000204. [Бесплатная статья PMC] [PubMed] [Google Scholar] 91. Аттвуд Т.К., Келл Д.Б., Макдермотт П., Марш Дж. И др. Calling International Rescue: объем знаний, потерянных в литературе и огромном количестве данных. Биохим Дж. 2009; 424: 317–33. [Бесплатная статья PMC] [PubMed] [Google Scholar] 92. Ananiadou S, Kell DB, Tsujii J. Text Mining и его потенциальные приложения в системной биологии. Trends Biotechnol. 2006; 24: 571–9. [PubMed] [Google Scholar] 93. Гобл С., Вольстенкрофт К., Годерис А., Халл Д. Открытие знаний для биологии с помощью Taverna: создание и использование семантики в Web of Science.В: Baker CJO, Cheung K-H, et al., Редакторы. Семантическая сеть: революционное открытие знаний в науках о жизни. Нью-Йорк: Спрингер; 2007. [Google Scholar] 95. Петтифер С.Р., Торн Д., Макдермотт П., Марш Дж. И др. Визуализация биологических данных: семантический подход к интеграции инструментов и баз данных. BMC Bioinformatics. 2009; 10: S19. [Бесплатная статья PMC] [PubMed] [Google Scholar] 97. Ананиаду С., Пюйсало С., Цуджи Дж., Келл ДБ. Извлечение событий для системной биологии путем анализа текстов литературы. Trends Biotechnol.2010; 28: 381–90. [PubMed] [Google Scholar] 98. Хука М., Финни А., Сауро Х.М., Болури Х. и др. Язык разметки системной биологии (SBML): среда для представления и обмена моделями биохимических сетей. Биоинформатика. 2003; 19: 524–31. [PubMed] [Google Scholar] 99. Келл Д. Б., Мендес П. Разметка - это модель: рассуждения о моделях системной биологии в эпоху семантической паутины. J Theor Biol. 2008; 252: 538–43. [PubMed] [Google Scholar] 100. Листер А.Л., Лорд П., Покок М., Випат А. Аннотации моделей SBML посредством семантической интеграции на основе правил.J Biomed Seman. 2010; 1: С3. [Бесплатная статья PMC] [PubMed] [Google Scholar] 101. Курто М., Юти Н., Кнюпфер С., Вальтемат Д. и др. Управляемые словари и семантика в системной биологии. Mol Syst Biol. 2011; 7: 543. [Бесплатная статья PMC] [PubMed] [Google Scholar] 102. Hoehndorf R, Dumontier M, Gennari JH, Wimalaratne S, et al. Интеграция моделей системной биологии и биомедицинских онтологий. BMC Syst Biol. 2011; 5: 124. [Бесплатная статья PMC] [PubMed] [Google Scholar] 103. Хаусон С., Урбах П. Научное обоснование: байесовский подход.Чикаго: Открытый суд; 1989. [Google Scholar] 104. Перл Дж. Причинность: модели, рассуждения и выводы. Кембридж: Издательство Кембриджского университета; 2000. [Google Scholar] 105. Маккей DJC. Теория информации, логические выводы и алгоритмы обучения. Кембридж: Издательство Кембриджского университета; 2003. [Google Scholar] 106. Нидхэм CJ, Брэдфорд JR, Bulpitt AJ, Westhead DR. Вывод в байесовских сетях. Nat Biotechnol. 2006; 24: 51–3. [PubMed] [Google Scholar] 107. Берч МакГрейн С. Теория, которая не умрет: как правило Байеса взломало код загадки, выследило российские подводные лодки и вышло победителем из двух столетий противоречий.Лондон: Издательство Йельского университета; 2011. [Google Scholar] 108. Тененбаум Дж. Б., Кемп С., Гриффитс Т. Л., Гудман Н. Д.. Как вырастить ум: статистика, структура и абстракция. Наука. 2011; 331: 1279–85. [PubMed] [Google Scholar] 109. Smith AFM, Skene AM, Shaw JEH, Naylor JC и др. Реализация байесовской парадигмы. Теория коммунизма. 1985. 14: 1079–102. [Google Scholar] 110. Берри Д.А. Статистика: байесовская перспектива. Бельмонт: Duxbury Press; 1996. [Google Scholar] 111. Леонард Т., Хсу JSJ. Байесовские методы: анализ для статистиков и междисциплинарных исследователей.Кембридж: Издательство Кембриджского университета; 1999. [Google Scholar] 112. Бернардо Дж. М., Смит AFM. Байесовская теория. Чичестер: Уайли; 2000. [Google Scholar] 113. Кеннеди М.С., О'Хаган А. Байесовская калибровка компьютерных моделей. J R Stat Soc B. 2001; 63: 425–50. [Google Scholar] 114. Бродхерст Д., Келл Д. Б.. Статистические стратегии, позволяющие избежать ложных открытий в метаболомике и связанных с ней экспериментах. Метаболомика. 2006; 2: 171–96. [Google Scholar] 115. Уилкинсон DJ. Байесовские методы в биоинформатике и вычислительной системной биологии.Краткий биоинформ. 2007. 8: 109–16. [PubMed] [Google Scholar] 116. Rohr JR, Raffel TR, Romansic JM, McCallum H, et al. Оценка связи между климатом, распространением болезней и сокращением численности земноводных. Proc Natl Acad Sci USA. 2008; 105: 17436–41. [Бесплатная статья PMC] [PubMed] [Google Scholar] 117. Джаявардхана Б., Келл Д. Б., Рэттрей М. Байесовский вывод мест нарушений в метаболических путях с помощью цепи Маркова Монте-Карло. Биоинформатика. 2008; 24: 1191–7. [PubMed] [Google Scholar] 118. Вышемирский В, Гиролами М.А.Байесовское ранжирование моделей биохимических систем. Биоинформатика. 2008; 24: 833–9. [PubMed] [Google Scholar]

комбинаторика | математика | Британника

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

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

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

Наконец, есть проблемы с оптимизацией. Например, функция f , экономическая функция, присваивает числовое значение f ( x ) любой конфигурации x с определенными заданными свойствами.В этом случае проблема состоит в том, чтобы выбрать конфигурацию x 0 , которая минимизирует f ( x ) или делает его ε = минимальным, то есть для любого числа ε> 0, f ( x ). 0 ) f ( x ) + ε, для всех конфигураций x с указанными свойствами.

Получите подписку Britannica Premium и получите доступ к эксклюзивному контенту. Подпишитесь сейчас

История

Ранние разработки

Некоторые типы комбинаторных задач привлекали внимание математиков с давних времен.Например, магические квадраты, представляющие собой квадратные массивы чисел со свойством, что строки, столбцы и диагонали в сумме дают одно и то же число, встречаются в И Цзин, , китайской книге, датируемой XII веком до нашей эры. Биномиальные коэффициенты, или целочисленные коэффициенты в разложении ( a + b ) n , были известны индийскому математику XII века Бхаскара, который в своей книге Līlāvatī («Изящный»): посвященный красивой женщине, привел правила их расчета вместе с наглядными примерами.«Треугольник Паскаля», треугольный массив биномиальных коэффициентов, преподавал персидский философ 13-го века Накир ад-Дин ас-Суси.

Считается, что на Западе комбинаторика началась в 17 веке с Блеза Паскаля и Пьера де Ферма, оба из Франции, которые открыли многие классические комбинаторные результаты в связи с развитием теории вероятностей. Термин комбинаторный впервые был использован в современном математическом смысле немецким философом и математиком Готфридом Вильгельмом Лейбницем в его Dissertatio de Arte Combinatoria («Диссертация о комбинированных искусствах»).Он предвидел применение этой новой дисциплины во всем диапазоне наук. Швейцарский математик Леонард Эйлер был, наконец, ответственен за развитие школы аутентичной комбинаторной математики, начиная с 18 века. Он стал отцом теории графов, когда решил проблему Кенигсбергского моста, и его знаменитая гипотеза о латинских квадратах не была решена до 1959 года.

В Англии Артур Кейли в конце XIX века внес важный вклад в создание перечислительного графа. теории, и Джеймс Джозеф Сильвестр открыл много комбинаторных результатов.Британский математик Джордж Буль примерно в то же время использовал комбинаторные методы в связи с развитием символической логики, а также комбинаторные идеи и методы Анри Пуанкаре, которые развились в начале 20 века в связи с проблемой n. тел, привели к дисциплине топологии, которая занимает центральное место в математике. Многие комбинаторные проблемы были поставлены в 19 веке как чисто развлекательные и идентифицированы под такими названиями, как «проблема восьми королев» и «проблема школьницы Киркман».С другой стороны, изучение тройных систем, начатое Томасом П. Киркманом в 1847 году и продолженное Якобом Штайнером, немецким математиком швейцарского происхождения, в 1850-х годах стало началом теории дизайна. Среди первых книг, посвященных исключительно комбинаторике, - книга немецкого математика Ойгена Нетто Lehrbuch der Combinatorik (1901; «Учебник комбинаторики») и книга британского математика Перси Александра Мак-Магона Combinatory Analysis (1915–16), которые дают представление о комбинаторная теория в том виде, в котором она существовала до 1920 г.

Комбинаторика в 20 веке

Многие факторы способствовали ускорению темпов развития комбинаторной теории с 1920 года. Одним из них было развитие статистической теории планирования экспериментов английскими статистиками Рональдом Фишером и Фрэнком Йейтсом. что породило множество проблем, представляющих комбинаторный интерес; методы, изначально разработанные для их решения, нашли применение в таких областях, как теория кодирования. Теория информации, зародившаяся примерно в середине века, также стала богатым источником комбинаторных проблем совершенно нового типа.

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

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

Статистическая механика - один из старейших и наиболее продуктивных источников комбинаторных задач.С середины 20 века прикладными математиками и физиками была проделана значительная комбинаторная работа - например, работа над моделями Изинга (см. Ниже проблему Изинга).

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *