Джон Кемени – Математик, профессор Дартмутского колледжа (США). Окончил Принстонский университет, где изучал математику и философию. В 1949 году защитил. - презентация

1 Джон Кемени – Математик, профессор Дартмутского колледжа (США). Окончил Принстонский университет, где изучал математику и философию. В 1949 году защитил диссертацию, а в 1953 году был приглашен в Дартмут. Джоном Кемени и Томасом Курцем руководило желание предоставить возможность работы на компьютере как можно большему числу студентов В первый день мая 1964 года профессора Дартмундского колледжа Джон Кемени и Томас Курц продемонстрировали созданный ими язык программирования BASIC (Beginners All-purpose Symbolic Instruction Code), ставший впоследствии самым распространенным. С тех пор эту первую реализацию языка так и называют «дартмундский BASIC», а всего создано свыше 250 различных его диалектов.

2 Наверняка авторы не предполагали, что их изобретение вызовет такие последствия. Курц писал в своих воспоминаниях, что они с Кемени хотели всего лишь предоставить возможность работы на компьютере как можно большему числу студентов. На тот момент колледж уже располагал мэйнфреймом General Electric 226, но не хватало языка программирования, и его было решено создать собственными силами. Стоит заметить, что математики Кемени и Курц не были профессионалами-программистами. Не отягощенные излишними знаниями предмета, они руководствовались лишь представлением о том, что им нужно. Создатели BASIC частично использовали свою компетентность в языках Fortran II и Algol 60, а остальное «додумали» сами. Новый язык должен был быть доступным для начинающих, универсальным, расширяемым, интерактивным, обеспечивать быстрое выполнение небольших программ, сообщать об ошибках понятно и «дружелюбно» и скрывать от пользователя особенности операционной системы.

3 Кемени и Курц посягнули на святое: до появления BASIC программирование было уделом ограниченного круга профессионалов, а новый простенький язык нарушил их избранность. Он позволил решать, пусть ограниченные задачи, но практически любому грамотному человеку. Реакция на BASIC со стороны профессионалов оказалась сугубо негативной, главным критиком стал выдающийся программист своего времени Эдсгер Дейкстра, заявивший даже: «Изучение BASIC вызывает неизлечимое повреждение мозгов» и «Обучение BASIC может нанести увечье, караемое законом».

4 . В 1975 году появился компьютер Altair 8800 с записанным в постоянную память интерпретатором BASIC, это стало началом революции персональных компьютеров. А еще через два года Биллом Гейтсом и Полом Аленом была создана компания Microsoft, выпустившая Altair BASIC. Вскоре появились версии для Apple II и IBM PC. Середина 80-х годов полоса зрелости BASIC. Даже компания Borland представила в 1985 году Turbo BASIC 1.0. Следующий импульс язык получил, когда Microsoft предложила Visual Basic. Этот язык использовался в 80% всех коммерческих разработок для Windows. Проигнорировав BASIC, профессионалы уступили дилетантам дорогу к операционным системам и далее, а уж потом «что выросло, то выросло».

5 Нахождение итогового мнения комиссии экспертов. Пусть мнения комиссии экспертов или какой- то ее части признаны согласованными. Каково же итоговое (среднее, общее) мнение комиссии? Согласно идее Джона Кемени следует найти среднее мнение как решение оптимизационной задачи. А именно, надо минимизировать суммарное расстояние от кандидата в средние до мнений экспертов. Найденное таким способом среднее мнение называют "медианой Кемени". Математическая сложность состоит в том, что мнения экспертов лежат в некотором пространстве объектов нечисловой природы. Общая теория подобного усреднения построена в ряде работ, в частности, показано, что в силу обобщения закона больших чисел среднее мнение при увеличении числа экспертов (чьи мнения независимы и одинаково распределены) приближается к некоторому пределу, который естественно назвать математическим ожиданием (случайного элемента, имеющего то же распределение, что и ответы экспертов). В конкретных пространствах нечисловых мнений экспертов вычисление медианы Кемени может быть достаточно сложным делом. Кроме свойств пространства, велика роль конкретных метрик. Так, в пространстве ранжировок при использовании метрики, связанной с коэффициентом ранговой корреляции Кендалла, необходимо проводить достаточно сложные расчеты, в то время как применение показателя различия на основе коэффициента ранговой корреляции Спирмена приводит к упорядочению по средним рангам. Бинарные отношения и расстояние Кемени. Как известно, бинарное отношение А на конечном множестве Q = {q 1, q 2,..., q k } - это подмножество декартова квадрата Q 2 = { (q m, q n ), m,n = 1,2,…,k }. При этом пара (q m, q n ) входит в А тогда и только тогда, когда между q m и q n имеется рассматриваемое отношение. Каждую кластеризованную ранжировку, как и любое бинарное отношение, можно задать матрицей || x(a, b) || из 0 и 1 порядка k x k. При этом x(a, b) = 1 тогда и только тогда, когда a < b либо a = b. В первом случае x(b, a) = 0, а во втором x(b, a) = 1. При этом хотя бы одно из чисел x(a, b) и x(b, a) равно 1. Как использовать связь между ранжировками и матрицами? Например, из определения противоречивости пары (a, b) (см. выше, пункт о теории измерений) вытекает, что для нахождения всех таких пар можно воспользоваться матрицами, соответствующими ранжировкам. Достаточно поэлементно перемножить две матрицы ||x(a,b)|| и ||y(a, b)||, соответствующие двум кластеризованным ранжировкам, и отобрать те и только те пары, для которых x(a,b)y(a,b)=x(b,a)y(b,a)=0.

6 В экспертных методах используют, в частности, такие бинарные отношения, как ранжировки (упорядочения, или разбиения на группы, между которыми имеется строгий порядок), отношения эквивалентности, толерантности (отношения сходства). Как следует из сказанного выше, каждое бинарное отношение А можно описать матрицей || a(i,j) || из 0 и 1, причем a(i,j) = 1 тогда и только тогда, когда qi и qj находятся в отношении А, и a(i,j) = 0 в противном случае. Определение. Расстоянием Кемени между бинарными отношениями А и В, описываемыми матрицами || a(i,j) || и || b(i,j) || соответственно, называется число D (A, B) = a(i,j) - b(i,j), где суммирование производится по всем i,j от 1 до k, т.е. расстояние Кемени между бинарными отношениями равно сумме модулей разностей элементов, стоящих на одних и тех же местах в соответствующих им матрицах. Легко видеть, что расстояние Кемени - это число несовпадающих элементов в матрицах || a(i,j) || и || b(i,j) ||.Расстояние Кемени основано на некоторой системе аксиом. Эта система аксиом и вывод из нее формулы для расстояния Кемени между упорядочениями содержится в книге [7], которая сыграла большую роль в развитии в нашей стране такого научного направления, как анализ нечисловой информации [4, 6]. В дальнейшем под влиянием Кемени были предложены различные системы аксиом для получения расстояний в тех или иных нужных для социально-экономических исследований пространствах, например, в пространствах множеств [4]. Медиана Кемени и законы больших чисел. С помощью расстояния Кемени находят итоговое мнение комиссии экспертов. Пусть А1, А2, А3,…, Ар - ответы р экспертов, представленные в виде бинарных отношений. Для их усреднения используют т.н. медиану Кемени Arg min D (Ai,A), где Arg min - то или те значения А, при которых достигает минимума указанная сумма расстояний Кемени от ответов экспертов до текущей переменной А, по которой и проводится минимизация. Таким образом, D (Ai,A) = D (A1,A) + D (A2,A) + D (A3,A) +…+ D (Aр,A). Кроме медианы Кемени, используют среднее по Кемени, в котором вместо D (Ai,A) стоит D2 (Ai,A). Медиана Кемени - частный случай определения эмпирического среднего в пространствах нечисловой природы. Для нее справедлив закон больших чисел, т.е. эмпирическое среднее приближается при росте числа составляющих (т.е. р - числа слагаемых в сумме), к теоретическому среднему: Arg min D (Ai,A) Arg min М D (A1, A). Здесь М - символ математического ожидания. Предполагается, что ответы р экспертов А1, А2, А3,…, А р есть основания рассматривать как независимые одинаково распределенные случайные элементы (т.е. как случайную выборку) в соответствующем пространстве произвольной природы, например, в пространстве упорядочений или отношений эквивалентности. Систематически эмпирические и теоретические средние и соответствующие законы больших чисел изучены в ряде работ (см., например, [4, 6]).

7 Законы больших чисел показывают, во-первых, что медиана Кемени обладает устойчивостью по отношению к незначительному изменению состава экспертной комиссии; во-вторых, при увеличении числа экспертов она приближается к некоторому пределу. Его естественно рассматривать как истинное мнение экспертов, от которого каждый из них несколько отклонялся по случайным причинам. Рассматриваемый здесь закон больших чисел является обобщением известного в статистике "классического" закона больших чисел. Он основан на иной математической базе - теории оптимизации, в то время как "классический" закон больших чисел использует суммирование. Упорядочения и другие бинарные отношения нельзя складывать, поэтому приходится применять иную математику. Вычисление медианы Кемени - задача целочисленного программирования. В частности, для ее нахождения используется различные алгоритмы дискретной математики, в частности, основанные на методе ветвей и границ. Применяют также алгоритмы, основанные на идее случайного поиска, поскольку для каждого бинарного отношения нетрудно найти множество его соседей. Матрица попарных расстояний

8 При проектировании языка использовались следующие восемь принципов: новый язык должен быть простым в использовании для начинающих быть языком программирования общего назначения предоставлять возможность расширения функциональности, доступную опытным программистам быть интерактивным предоставлять ясные сообщения об ошибках быстро работать на небольших программах не требовать понимания работы аппаратного обеспечения защищать пользователя от операционной системы Язык был основан частично на Фортран II и частично на Алгол-60, с добавлениями, делающими его удобным для работы в режиме разделения времени и, позднее, обработки текста и матричной арифметики. Первоначально Бейсик был реализован на мейнфрейме GE-265 с поддержкой множества терминалов. Вопреки распространённому убеждению, в момент своего появления это был компилируемый язык.Фортран II Алгол-60компилируемый