Лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте




НазваниеЛекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте
Дата конвертации08.02.2013
Размер445 b.
ТипЛекция



Эта лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте.

  • Эта лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте.



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

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

  • Изучение математики развивает архитектурный талант – талант организовывать знания, – который необходим программистам. Начала Евклида – это замечательный учебник для разработчиков сложных систем.

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























196 42

  • 196 42

  • 154 42

  • 112 42

  • 70 42

  • 28 42

  • 28 14

  • 14 14 Done!

  • GCD: 14























  • На современном языке, Пифагор открыл, что √2 иррационален.













Некто, начавший изучать геометрию, прошедши первую теорему, спросил Евклида: «Что я заработаю, выучив все это?» Евклид сказал своему рабу: «Дай ему алтын, ибо он хочет от науки поживиться».

  • Некто, начавший изучать геометрию, прошедши первую теорему, спросил Евклида: «Что я заработаю, выучив все это?» Евклид сказал своему рабу: «Дай ему алтын, ибо он хочет от науки поживиться».

  • Стобей, Антология





В 1959, на конференции учителей математики во Франции, Жан Дьедонне кричал ”Долой Евклида!” и ”Смерть треугольникам!”

  • В 1959, на конференции учителей математики во Франции, Жан Дьедонне кричал ”Долой Евклида!” и ”Смерть треугольникам!”

  • И. М. Яглом Элементарная Геометрия Прежде и Теперь



In summo apud illos honore geometria fuit, itaque nihil mathematicis inlustrius; at nos metiendi ratiocinandique utilitate huius artis terminavimus modum.

  • In summo apud illos honore geometria fuit, itaque nihil mathematicis inlustrius; at nos metiendi ratiocinandique utilitate huius artis terminavimus modum.

  • Среди них [Греков] геометрия была в величайшем почете; ничего не было блистательней математики. Мы [Римляне] ограничили полезность этой науки подсчетами и вычислениями.

  • Цицерон, Тускуланские Беседы









196 42 196 = 42*4 + 28

  • 196 42 196 = 42*4 + 28

  • 42 28 42 = 28*1 + 14

  • 28 14 28 = 14*2 + 0

  • 14 0 Done!

  • GCD: 14











3x2+2x-2

  • 3x2+2x-2

  • x-2 3x3-4x2-6x+10

  • 3x3-6x2

  • 2x2-6x

  • 2x2-4x

  • -2x+10

  • -2x+4

  • 6









Чтобы найти остаток от деления z1 на z2

  • Чтобы найти остаток от деления z1 на z2

  • Постройте квадратную решетку на комплексной плоскости, порожденную z2 (вместе с i*z2, -i*z2 и –z2).

  • Найдите квадрат в решетке, который включает z1.

  • Найдите вершину квадрата w , ближайшую к z1.

  • Остаток равен z1 - w.









«Если мы возьмем множество чисел

  • «Если мы возьмем множество чисел

  • t + n√-a

  • где a – конкретное натуральное число, t и n – произвольные целые числа … то только для некоторых значений of a, например, a = 1, наибольший общий делитель двух чисел может быть найден с помощью такого же алгоритма, как и для ... целых чисел. … Это совсем не так, когда a = 5. … Например, 21 = 3*7 = (1+2√-5)*(1-2√-5)…»

  • Лежен Дирихле

  • Лекции по Теории Чисел





Целые алгебраические числа – это корни многочленов с целочисленными коэффициентами и с ведущим коэффициентом, равным единице.

  • Целые алгебраические числа – это корни многочленов с целочисленными коэффициентами и с ведущим коэффициентом, равным единице.



  • Es steht alles schon bei Dedekind!

  • Эмми Нётер

  • (Это всё есть у Дедекинда.)

  • Всё = кольца, поля, идеалы, модули...



Гаусс

  • Гаусс

    • Правильные многоугольники
    • Пятый постулат
  • Дирихле

    • Простые числа в арифметических прогрессиях
  • Риман

    • Неевклидова геометрия
  • Дедекинд

    • Возрождение теории иррациональностей Евдокса
  • Клейн

    • Эрлангенская программа
  • Гильберт

    • Основания геометрии
    • Арифметизация математики




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

  • Если развитие математики сегодняшнего дня несомненно протекает под знаком алгебраизации, проникновения алгебраических понятий и алгебраических методов в самые различные математические теории, то это стало возможным лишь после работ Эмми Нётер.

  • Павел Сергеевич Александров







Коммутативное кольцо(+, -, *)

  • Коммутативное кольцо(+, -, *)

  • Функция norm: Ring -> Unsigned

    • norm(a*b) >= norm(a)
    • Для всех a, b, где b != 0, существуют q, r, такие что a == q*b + r и
    • r == 0 || norm(r) < norm(b)










Операции и их свойства

  • Операции и их свойства

  • Модели

  • Алгоритмы





196 42

  • 196 42

  • 98 21 2

  • 49 21 2

  • 28 21 2

  • 14 21 2

  • 7 21 2

  • 14 7 2

  • 7 7 2 Done!

  • GCD: 7*2 = 14







  • Используй x как 2!



gcd(p,0) = gcd(0,p) = p

  • gcd(p,0) = gcd(0,p) = p

  • gcd(p, p) = p

  • gcd(x*p1,x*p2) = x*gcd(p1, p2)

  • gcd(x*p1,x*p2+c) = gcd(p1, x*p2+c)

  • gcd(x*p1+c,x*p2) = gcd(x*p1+c,p2)

  • if degree(p1) >= degree(p2)

  • gcd(x*p1+c1,x*p2+c2) =

  • gcd(p1-(c1/c2)*p2, x*p2+c2)

  • if degree(p1) < degree(p2)

  • gcd(p1,p2) = gcd(p2,p1)



x3-3x-2 x2-4

  • x3-3x-2 x2-4

  • x3-.5x2-3x x2-4

  • x2-.5x-3 x2-4

  • x2-2x x2-4

  • x-2 x2-4

  • x2-4 x-2

  • x2-2x x-2

  • x-2 x-2 Done!

  • GCD: x-2



Используй 1+i как 2!

  • Используй 1+i как 2!



a+bi/1+i =(a+bi)(1-i)/(1+i)(1-i)=

  • a+bi/1+i =(a+bi)(1-i)/(1+i)(1-i)=

  • (a+bi)(1-i)/2 = ((a+b) - (a-b)i)/2

  • Гауссово число a+bi делится на 1+i тогда и только тогда a=b(mod 2)



Если два гауссовых числа z1 и z2 не делятся на 1+i, то z1+z2, z1-z2, z1+i*z2 и z1-i*z2 делятся на 1+i.

  • Если два гауссовых числа z1 и z2 не делятся на 1+i, то z1+z2, z1-z2, z1+i*z2 и z1-i*z2 делятся на 1+i.

  • И,

  • min (|z1+z2|, |z1-z2|, |z1+i*z2|, |z1-i*z2|) < max(|z1|, |z2|)



Алгоритм Штейна также работает для чисел Эйзенштейна Z[ζ], то есть целых чисел, расширенных с ζ ( ) (примитивный кубический корень из 1).

  • Алгоритм Штейна также работает для чисел Эйзенштейна Z[ζ], то есть целых чисел, расширенных с ζ ( ) (примитивный кубический корень из 1).

  • Мы используем 1 – ζ как 2.





  • В 2004 Agarwal и Frandsen показали что есть кольца в которых не работает алгоритм Евклида, но работает алгоритм Штейна.



Информатика это Математика

  • Информатика это Математика



  • Многие из книг в библиографии существуют в прекрасных русских переводах.





Laurence E. Siegler, Fibonacci's Liber Abaci, Springer-Verlag, 2002

  • Laurence E. Siegler, Fibonacci's Liber Abaci, Springer-Verlag, 2002

  • Nicolas Bourbaki, Elements of the History of Mathematics, Springer-Verlag, 1999

  • Carl Friedrich Gauss, Disquisitiones Arithmaticae, Yale, 1965

  • John Stillwell, Elements of Number Theory, Springer-Verlag, 2002

  • Peter Gustav Lejeune Dirichlet, Lectures on Number Theory, AMS, 1999

  • Richard Dedekind, Theory of Algebraic Integers, Cambridge, 1996

  • B. L. van der Waerden, Algebra, Springer-Verlag, 1994



Donald Knuth, Art of Computer Programming, vol. 2, Seminumerical Algorithms, Addison-Wesley, 1998

  • Donald Knuth, Art of Computer Programming, vol. 2, Seminumerical Algorithms, Addison-Wesley, 1998

  • Josef Stein, Computational problems associated with Racah algebra, J. Comput. Phys., (1967) 1, 397-405

  • Andre Weilert, (1+ i)-ary GCD Computation in Z[i] as an Analogue of the Binary GCD Algorithm, J. Symbolic Computation (2000) 30, 605-617



Ivan Bjerre Damgård and Gudmund Skovbjerg Frandsen, Efficient algorithms for GCD and cubic residuosity in the ring of Eisenstein integers, Proceedings of the 14th International Symposium on Fundamentals of Computation Theory, Lecture Notes in Computer Science 2751, Springer-Verlag (2003), 109-117

  • Ivan Bjerre Damgård and Gudmund Skovbjerg Frandsen, Efficient algorithms for GCD and cubic residuosity in the ring of Eisenstein integers, Proceedings of the 14th International Symposium on Fundamentals of Computation Theory, Lecture Notes in Computer Science 2751, Springer-Verlag (2003), 109-117

  • Saurabh Agarwal, Gudmund Skovbjerg Frandsen, Binary GCD Like Algorithms for Some Complex Quadratic Rings. ANTS 2004, 57-71



Похожие:

Лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте iconВ 1962 году в Астраханском государственном педагогическом институте им. С. М. Кирова была организована кафедра ботаники завкафедрой доцент Панафутина Н. Н
В 2007 году в связи с переходом на должность заведующего кафедрой д х н., профессора Тыркова А. Г. она была переименована в кафедру...
Лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте iconЯзыки и методы конструирования программ
...
Лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте iconЛекция 26 Сафонов Владимир Олегович
Система распределения физической памяти в Linux занимается размещением и освобождением страниц, групп страниц и небольших блоков...
Лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте iconЛекция 1 Основные понятия и определения теоретической механики Лекция 2 Виды связей и реакции связей Лекция 3 Момент силы относительно точки Лекция 4 Кинематика точки
Теоретическая механика это наука о наиболее общих законах механиче­ского движения и равновесия материальных объектов
Лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте iconАктуальность героев произведения М. Булгакова «Собачье сердце» в наше время. Работу Волчкова Анна Создание
Повесть «Собачье сердце» написана в 1925 году. Рукопись была изъята при обыске на квартире Булгакова в 1926 году. Впервые она была...
Лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте iconВ 1925 году она была переименована в Академию наук ссср, а в 1991 в Российскую академию наук
России была прервана в начале 90-х годов, но в конце прошлого века была вновь возобновлена. В 1999 году Указом Президента РФ от 7...
Лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте iconЛекция 3 Выражения Именующее выражение (lvalue) Объект некоторая непрерывная область памяти. Переменная именованная область памяти, т е. переменная это объект

Лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте iconЛекция №9 Развитие психологических знаний в эпоху Возрождения
Ждан А. Н. История психологии. От античности к современности. М.: Педагогическое общество России, 1999
Лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте iconСохранение памяти о малоизвестных героях, об их значении и роли в Отечественной войне 1812 года
Павловского гренадёрского полка, Тучков был ранен пулей в грудь, после перевязки отправлен в Можайск. После трёх недель мучений скончался...
Лекция была впервые прочитана в 1999 году как Мемориальная Лекция памяти Артура Шофсталя в Ренсселерском Политехническом Институте iconУчебно-методический комплекс дисциплины «риторика» 2008 Риторика Темы лекций в презентации
Лекция № Риторика как научная дисциплина (30 слайдов) Лекция № Краткие сведения из истории риторики (30 слайдов)
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница