Лекция 2
Добавлено: 17 янв 2025, 15:07
На второй лекции мы продолжили разбор тонкостей в постановках задач, вновь концентрируясь на проблеме "пробивания барьера сложности": даже если строго доказана невозможность построения алгоритма, решающего поставленную проблему за количество действий, меньшее, чем некоторая оценка снизу, нельзя ли изменить формулировку и (иногда кардинально!) улучшить эту оценку?
Основными поучительными прикладными примерами будут алгоритмы сортировки и поиска.
Несмотря на их вездесущесть (в том числе в учебных программах университетов) и, казалось бы, ясность в постановке таких задач, мы увидим, что приходится иногда признать: "Очевидное - невероятное!"
Центральным моментом будут следующие 2 вопроса:
Нелли Литвак: "“Математика и жизнь. О том, как благодаря математике вертится современный мир.”
Лекция состоялась в 2017 г. в центре "Архэ" (http://arhe.msk.ru):
https://www.youtube.com/watch?v=NPl280z ... G&index=11
Лектор: Нелли Литвак — профессор математики, преподаватель в Университете Твенте (Нидерланды).
В ходе лекции было продемонстрировано, что прогресс в ускорении работы алгоритмов (уменьшения количества операций для решения поставленной задачи) намного опережает ускорение "железа" (скорости работы процессоров) за период 15 и 25 лет. Изложение можно найти в разделе "Математика, обогнавшая компьютер" (с. 41-43) книги Нелли Литвак и Андрея Райгородского "Кому нужна математика? Понятная лекция о том, как устроен цифровой мир" (издательство "Манн, Иванов и Фербер", 2017)
Основными поучительными прикладными примерами будут алгоритмы сортировки и поиска.
Несмотря на их вездесущесть (в том числе в учебных программах университетов) и, казалось бы, ясность в постановке таких задач, мы увидим, что приходится иногда признать: "Очевидное - невероятное!"
Центральным моментом будут следующие 2 вопроса:
- Какие "ингредиенты" в постановке задачи - лишние?
Достаточно часто (выкинув "ненужное"), в математике можно получить более сильный результат.
В нашем случае мы выкинем компоненты, которые, как кажется с первого взгляда, абсолютно необходимы... Однако, найдя обходной путь, удается таким способом пробить "барьер сложности" в задачах сортировки. - Нельзя ли найти что-то вроде "катализатора" для алгоритмов - компонента, который (подобно катализатору, ускоряющему химические реакции) формально ни в постановке задачи не участвует, ни в ответе не нужен, но радикально ускоряет решение задачи? И, как всегда на наших лекциях, вопреки строго доказанным оценкам снизу на скорость решения (количество операций, необходимых для ее решения), "добавив ненужное", мы вновь пробьем барьер сложности ...
Нелли Литвак: "“Математика и жизнь. О том, как благодаря математике вертится современный мир.”
Лекция состоялась в 2017 г. в центре "Архэ" (http://arhe.msk.ru):
https://www.youtube.com/watch?v=NPl280z ... G&index=11
Лектор: Нелли Литвак — профессор математики, преподаватель в Университете Твенте (Нидерланды).
В ходе лекции было продемонстрировано, что прогресс в ускорении работы алгоритмов (уменьшения количества операций для решения поставленной задачи) намного опережает ускорение "железа" (скорости работы процессоров) за период 15 и 25 лет. Изложение можно найти в разделе "Математика, обогнавшая компьютер" (с. 41-43) книги Нелли Литвак и Андрея Райгородского "Кому нужна математика? Понятная лекция о том, как устроен цифровой мир" (издательство "Манн, Иванов и Фербер", 2017)