?

Log in

No account? Create an account

67_itmo


Группа К4132 СПбГУ ИТМО


Стартовое задание для группы К4132 (осень 2016 года)
matholimp wrote in 67_itmo
Чтобы обеспечить обратную связь в перерывах между встречами на занятиях:
1. Создайте (зарегистрируйте) личный блог на http://www.livejournal.com (у кого уже есть, можно использовать прежний, если учебные записи в нём не станут диссонировать с остальными). Либо можно логиниться и писать в ЖЖ через Фейсбук, ВКонтакте или другие социальные сети.
2. Вступите в это сообщество и не реже раза в две недели отслеживайте новые записи в нем.
3. Оставьте комментарий к этой записи с указанием Ваших ФИО (в профиле их можно не называть). Проверьте, что комментарий не анонимен (подписан ссылкой на Ваш блог).
4. Размещайте в своих блогах отчеты по лабораторным работам и иную полезную информацию. Ссылки на такие отчёты оставляйте в комментариях к записям с соответствующими заданиями.
5. Если Вы хотите, чтобы Ваши отчеты по лабораторным работам мог видеть только преподаватель, то делайте нужные записи "подзамочными", но тогда обязательно включите matholimp в число своих "друзей". В противном случае включите в число своих "друзей" также товарищей по группе, либо делайте свои записи открытыми.
6. При желании и-или необходимости Вы можете делать в этом сообществе записи с любыми вопросами, пожеланиями и предложениями, адресованными преподавателю и-или товарищам по группе.

Темы для докладов (программа курса)
matholimp wrote in 67_itmo
Любой вопрос может стать темой Вашего доклада. Чтобы они не повторялись, желающие сделать доклад оставьте комментарий к этой записи. Право выбора принадлежит тому, кто сделает это раньше других.

1. Происхождение термина «искусственный интеллект»
2. Понимание термина «искусственный интеллект»
3. Аналогии искусственного и естественного интеллекта
4. Различия искусственного и естественного интеллекта
5. Предпосылки развития науки ИИ
6. Интеллектуальные машины С.Н.Корсакова
7. История развития ИИ в СССР и России
8. История развития ИИ за рубежом
9. Тест Тьюринга
10. Интуитивный подход к ИИ
11. Вычислительные машины и разум
12. Эвристики и алгоритмы
13. Символьные вычисления
14. Символьный подход к ИИ
15. Логическое программирование
16. Логический подход к ИИ
17. Агентно-ориентированный подход
18. Гибридный подход
19. Моделирование рассуждений
20. Символьное моделирование мыслительных процессов
21. Обработка естественного языка компьютерными методами
22. Понятие знаний в ИИ
23. Инженерия знаний
24. Представление знаний в ИИ
25. Машинное обучение
26. Биологическое моделирование ИИ
27. Интеллектуальная робототехника
28. Машинное творчество
29. Актуарная математика
30. Распознавание речи
31. Распознавание образов
32. Когнитология
33. Методология когнитивного моделирования
34. Экспертные системы
35. Двойственность Галуа
36. Философские проблемы создания ИИ
37. Этические аспекты ИИ
38. Религиозные трактовки ИИ
39. Шахматные программы и автоматы
40. ИИ в компьютерных играх
41. ИИ в научно-фантастической литературе и искусстве
42. Российская ассоциация искусственного интеллекта

Работа №1: Соответствия, замыкания и двойственность Галуа
matholimp wrote in 67_itmo
Выберите не менее ста существительных (объектов) и не менее ста прилагательных (признаков, свойств). Запишите эти существительные в разных строчках в первом столбце Excel, а прилагательные - в разных столбцах в первой строке. На пересечении каждого столбца с каждой строкой поставьте 1, если объект обладает нужным свойством, и 0 - в противном случае.
Для любого множества А объектов можно построить двойственное ему множество Г(А) их общих свойств. Для этого нужно оставить в таблице только выбранные строчки, а затем только те столбцы, в которых (в выбранных строчках) стоят только единицы. Аналогично, для любого множества В свойств можно построить двойственное ему множество Г(В) всех объектов с нужным набором свойств.
В частности, для любого множества А можно построить его замыкание Г(Г(А)). Если Г(Г(А))=А, то А называется замкнутым.
Предъявите примеры незамкнутых множеств А (объектов) и В (свойств). Для этого постройте Г(Г(А)) и Г(Г(В)) и покажите, что они отличаются от А и В.
Покажите, что Г(А) и Г(В) замкнуты. Для этого постройте Г(Г(Г(А))) и Г(Г(Г(В))) и покажите, что они совпадают с Г(А) и Г(В).

Работа №2: Генерализация изолиний рельефа методом Лайминга
matholimp wrote in 67_itmo
Скачайте с http://mapn37.narod.ru/map2/indext.html лист карты N-37-(№), номер № которого совпадает с Вашим порядковым номером в списке группы (по алфавиту). Найдите в нужной карте максимальную и минимальную отметки высот. Их полусумму округлите до десятков и обозначьте через Н.
Выберите 5 точек, расположенных на высоте Н, одна из которых должна располагаться как можно ближе к центру карты, а остальные - к разным её углам. Постройте кривую второго порядка, проходящую через эти 5 точек.

План решения.

Начните с замены географических координат удобными декартовыми: оси направьте по краям листа, а в качестве единицы возьмите дециметр или дюйм на карте. Зафиксируйте значения координат выбранных пяти точек.
При желании можно искать кривую второго порядка методом неопределённых коэффициентов. Для этого придётся найти базисное решение однородной системы пяти линейных уравнений с шестью неизвестными. Если на 1 курсе Вы свободно овладели методом Гаусса, то вычисления займут не больше полутора-двух часов.
Однако есть более удобный способ. Сначала оставьте первые 4 из 5 точек и попытайтесь решить ту же задачу для них. Ясно, что недоопределённая задача будет иметь бесконечно много решений. Сравнительно легко можно найти те три из них, в которых искомая кривая второго порядка вырождается в пару прямых.
Действительно, разбейте множество из четырёх точек на две пары. Через пару точек легко провести прямую. Запишите уравнения обеих прямых в общем виде Ах+Ву+С=0 и перемножьте левые части этих уравнений. Получится какой-то многочлен F1(х,у) второй степени.
Аналогично, разбейте то же самое множество из четырёх точек на две другие пары и найдите другой многочлен F2(х,у) второй степени. Возможен ещё один способ разбиения множества из четырёх точек на две пары, но он не понадобится.
Легко убедиться, что при подстановке любого значения коэффициента С уравнение
(*) (1-С)F1(х,у)+СF2(х,у)=0
задаёт кривую второго порядка, на которой лежат первые 4 из 5 точек. Осталось так распорядиться выбором С, чтобы на нужной кривой оказалась и последняя точка. Для этого нужно подставить значения координат последней точки вместо х и у в (*) и решить получившееся линейное уравнение относительно С.
Так как длинная серия вычислений чревата ошибками, то проверку ответа подстановкой в него ВСЕХ пяти точек я считаю обязательной. Если несоответствий окажется мало, то легко можно будет локализовать и исправить ошибки.
Для наглядности изобразите фрагмент найденной кривой в пределах листа карты. Сравните его с реальным расположением горизонталей уровня Н.

Работа №3: Упражнение по теме "Основные системы счисления"
matholimp wrote in 67_itmo
Пользуясь кодовой страницей 1251 (или 0866), запишите свою фамилию в виде числа в 256-чной (байтовой) системе счисления. Заменив каждую 256-чную цифру двумя 16-чными ("дампом"), переведите это число в шестнадцатеричную систему счисления. Затем (уже из шестнадцатеричной) переведите его в системы счисления с основаниями 8, 2, 3, 9, 10.
Наконец, переведите это число в факториальную и фибоначчиевскую системы счисления.
Кодовые страницы можно найти, например, на http://mech.math.msu.su/~shvetz/54/inf/perl-problems/chIO_sCodePages.xhtml (таблицы 17.4 и 17.5). Все остальные нужные определения Вы легко найдёте по ссылкам с http://www.mashavph.narod.ru/Cheb02/term.htm .
Поясню на примере собственной фамилии. Read more...Collapse )

Учебно-исследовательская работа по системам счисления
matholimp wrote in 67_itmo
Учебно-исследовательская работа носит факультативный характер, но позволит Вам получить бонусные баллы: от 3-9 за выполнение её на ознакомительном уровне до 40-100 в случае существенного продвижения.

Первой открытой публикацией, посвященной новым системам счисления, был мой доклад 1997г., тезисы которого выставлены на нескольких сайтах в интернете, в том числе, на http://www.mashavph.narod.ru/Cheb02/2.htm . Начните со знакомства с этим текстом. На том же сайте проведена классификация систем счисления - http://www.mashavph.narod.ru/Cheb02/4.htm , а также собрана нужная терминология - http://www.mashavph.narod.ru/Cheb02/term.htm .
Затем познакомьтесь с описанным на http://www.barocko.narod.ru/Pos/15/1.htm методом построения новых систем счисления, который придумала Наталия Баранова. Ваша задача - сначала найти какую-нибудь новую функцию, удовлетворяющую перечисленным в этой статье свойствам, а затем на её основе построить новую систему счисления.
Образец того, как это сделала Анна Кравченко, см. на http://www.aakravchenko.narod.ru/SAMARA/1.htm .
Несколько более трудной является обратная задача - для выбранной системы счисления показать, что она является итерационной (если это на самом деле так!) и построить подходящую для этого функцию.

Работа №4: Моделирование работы мозга при выборе решения в случае нескольких оценочных факторов
matholimp wrote in 67_itmo
Задание. Проанализируйте одну или несколько типовых ситуаций, в которых Вам многократно приходилось решать одну и ту же проблему. Определите, какими мотивами и критериями Вы руководствовались в своём выборе.

Простейшим примером такой ситуации может служить выбор маршрута движения от выхода из метро «Горьковская» к главному корпусу ИТМО. Пойти пешком или ждать трамвая? А если трамвая долго нет, то как быстро Вы измените прежнее решение и уйдёте с остановки?
Конечно, всё зависит от обстоятельств: много ли времени осталось у Вас в запасе, какая погода, нужно ли платить за проезд и т.п. В одних случаях Вы учитываете какой-то фактор, а в других игнорируете его.
Например, время критично в зависимости от риска опоздать. Но если его запас вполне достаточен, то нет необходимости стремиться к минимизации (по крайней мере, пока Вы не потеряете слишком много времени, безуспешно простояв на трамвайной остановке).
Так как Вы изучали дисциплины «Теория принятия решений» и «Методы оптимизации», то можете использовать их аппарат для представления своих выводов. Но при этом обратите внимание, что здесь существенно иная ситуация. Весьма принципиальное отличие состоит в том, что там ранее поставленная задача не менялась по ходу её решения. В реальности же могут происходить события, побуждающие Вас радикально изменить систему приоритетов. Наконец, почти наверняка Ваш мозг работал по иным правилам (тем более, до изучения Вами названных дисциплин).
Обратите внимание на неполноту информации. Как Вы отреагируете на большое скопление людей на остановке? Трамвая давно не было? Но разве это значит, что он вот-вот подойдёт? А если людей нет вообще? Трамвай только что ушёл или сегодня трамваи совсем не ходят?
Пользуетесь ли Вы сервисом "Яндекс. Транспорт" или аналогичной информацией на стенде у станции метро «Горьковская»? Если да, то как эта информация влияет на Ваш выбор решения?

Работа №5: Интеллектуальное администрирование генеалогического форума
matholimp wrote in 67_itmo
Разработайте структуру анкеты и смоделируйте работу «интеллектуальной» программы, обрабатывающей большой массив анкет. Для иллюстрации используйте собственную родословную, а также 2-3 исторических персонажей.
Как известно, в России действует Закон о защите персональных данных, запрещающий выкладывать в интернете большие массивы информации, в том числе, включающей ФИО, даты рождения и т.п. Ещё до принятия этого закона многие пользователи скрывали личную информацию, опасаясь действий злоумышленников. С другой стороны, растёт интерес к восстановлению и изучению родословных. Ваша задача – решить эту проблему, не вступая в конфликт с требованиями закона.
Ваша программа должна отслеживать содержимое анкет пользователей и сравнивать их на предмет поиска возможного дублирования. По умолчанию, все вводимые пользователем данные видны только ему самому и этой программе (но не программисту или администратору форума). Каждый пользователь может вводить анкеты не только за себя, но также за своих близких родственников и предков. Прежде всего, при обнаружении родственников, система должна сообщить об этом обоим пользователям, предложив им открыть друг другу взаимный доступ, чтобы согласовать введенную ими информацию (в частности, исправить ошибки).
В большинстве случаях анкеты будут заполнены лишь частично, что не позволит достоверно установить факт совпадения. Тогда программа сначала должна будет задать пользователям уточняющие вопросы, чтобы снять возникшие сомнения (подтвердить факт родства или опровергнуть его). Формат анкеты должен облегчать эту проверку.
Восходящая родословная в норме представляет собой двоичное дерево, для кодирования вершин которого удобно использовать троичные цифры N, O, P. Здесь О означает фиксацию какого-либо человека, N – переход от него на одно поколение вверх по материнской линии, а Р – по отцовской. В частности, NО – мать, а РО – отец выбранного человека; NРО – бабушка по отцовской линии, РNО – дедушка по материнской и т.д. К сожалению, реальность значительно сложнее: есть внебрачные дети, «биологические» и «юридические» родители, информация о старших поколениях часто утрачена. Наконец, разные линии могут выводить на одного и того же предка. В этом случае нужно зафиксировать тождество соответствующих слов, а родословную этого предка исключить из дерева (иначе пришлось бы дублировать записи по всем вышестоящим предкам).
Нисходящая родословная гораздо сложнее. Для каждого человека нужно каким-то образом упорядочить его детей (сквозной нумерацией или отдельными нумерациями по каждому браку).

Работа №6: Точные аналоги интуитивных решений
matholimp wrote in 67_itmo
Вы должны подобрать и прокомментировать несколько примеров точного обоснования «народной мудрости». В качестве примеров лучше всего брать пословицы, поговорки, крылатые выражения или общеизвестные цитаты. Ваш комментарий к ним должен начинаться со ссылки на математическое утверждение (теорему или иной факт), его автора и источник (достаточно ссылки на страницу в интернете, но лучше указывать бумажную публикацию). Если Вы используете специальные термины, то процитируйте их определения. Затем своими словами поясните, в чём Вы видите связь между «гуманитарной» и точной формулировками.

Образец 1. Поговорка: «Попасть пальцем в небо».
Точный аналог: вероятность случайного выбора заранее фиксированной точки внутри плоской фигуры равна нулю.
Это достаточно общеизвестный факт из теории вероятностей. Например, на http://ssau2011.narod.ru/l1.htm :
""...
1.3.8. Геометрические вероятности
...
вероятность попадания брошенной точки в одну определенную точку области равна нулю, однако это событие может произойти,
...""
Аналогом неба может служить круг. Вероятность попадания брошенной точки в круг точки в заранее выбранное подмножество пропорциональна его площади. Площадь подмножества, состоящего из одной точки, равна нулю.
Содержательный смысл поговорки: непродуманный ответ крайне редко бывает верным.

Образец 2. Пословица: «Умный в гору не пойдёт, умный гору обойдёт».
Точный аналог: теорема А.Д.Александрова о том, что кратчайшая линия на выпуклой поверхности не может проходить через коническую точку.
Полностью изложена в монографии: Александров А.Д. Внутренняя геометрия выпуклых поверхностей. - М.: ОГИЗ, 1948.
Выпуклым телом называется замкнутое выпуклое множество в пространстве, имеющее внутренние точки. Для того, чтобы замкнутое выпуклое множество было выпуклым телом, необходимо и достаточно, чтобы не существовало плоскости, содержащей это множество.
Область (связное открытое множество) на границе выпуклого тела называется выпуклой поверхностью. Связная компонента границы выпуклого тела называется полной выпуклой поверхностью. Если исключить два тривиальных случая, когда выпуклое тело есть все пространство или область между двумя параллельными плоскостями, то полную выпуклую поверхность можно определить просто как границу выпуклого тела.
С каждой точкой S границы выпуклого тела К естественным образом связывается некоторый конус V(S), образуемый полупрямыми, исходящими из точки S и пересекающими тело К по крайней мере в одной точке, отличной от S. Этот конус называется касательным конусом в точке S, а его поверхность - касательным конусом выпуклой поверхности, ограничивающей тело.
В зависимости от вида касательного конуса точки выпуклой поверхности подразделяются на конические, ребристые и гладкие. Именно точка Х выпуклой поверхности называется конической, если касательный конус V(X) в этой точке не вырождается. Если же касательный конус V(X) вырождается в двугранный угол или плоскость, то Х называется ребристой или соответственно гладкой точкой. Негладкие точки на выпуклой поверхности представляют собой в некотором смысле исключение. Именно, множество ребристых точек имеет меру нуль, а множество конических точек не более чем счетно.
Понятие кратчайшего расстояния неразрывно связано с той поверхностью, по которой оно измеряется. Кратчайшая — это кривая в метрическом пространстве, соединяющая две его точки и не превосходящая по длине любую другую кривую с теми же концами.
Концы кратчайшей могут быть коническими точками. Но проходить через коническую точку кратчайшая не может.
Кратчайшая линия может трактоваться здесь как аналог «умного», знающего самую короткую дорогу. Тогда как коническая точка служит подходящей математической моделью горной вершины.