Практические задачи Летней школы
From UniSchools_NN2009
Скачать все задачи в одном файле
Задачи от Intel
Список задач производственной составляющей стажировки
Задача 1: Исследование возможностей и применения технологии Access Control Engine (ACE) в системе SAP CRM*
Выполнение данной работы дает возможность расширить свои знания о стандартных и нестандартных технологиях в системах SAP, конфигурации и бизнес процессах системы SAP CRM, а также получить углубленный опыт программирования на языке ABAP.
Для решения задачи необходимо: исследовать технологию Access Control Engine (ACE), применяемую как альтернативный подход к управлению доступом и правами пользователей в системе SAP CRM.
Планируемые результаты:
Основной: Подготовить шаблоны кода и/или системных настроек для решения типовых задач по разграничению доступа пользователей к различным объектам (мастер данным, транзакциям, иерархиям) в зависимости от позиции пользователей в организационной структуре, территориальной иерархии, адреса и т.д.
Дополнительный: Несколько примеров и пособий по применению данной технологии для демонстации ее возможностей.
Источники информации: документация по данной технологии.
Требуемый уровень подготовки: Базовые теоретические и практические знания о системах SAP.
* Проект осуществляется совместно с Центром компетенций в области современных ERP систем, созданным на базе Государственного Университета – Высшей Школы Экономики, Нижегородский филиал.
Задача 2: Разработка интранет-приложения с использованием Silverlight
Решая задачу, Вы сможете:
- Развить навыки разработки надежных бизнес-приложений;
- Углубить знания о паттернах объектно-ориентированного проектирования;
- Научиться практикам экстремального программирования.
Предлагается исследовать технологию Silverlight на предмет применимости в бизнес-приложениях и разработать интранет-приложение с богатым пользовательским интерфейсом (деловая графика).
Варианты прикладной области:
- Управленческие отчеты по результатам сервисной деятельности;
- Сравнение показателей качества исходного кода интеловских приложений.
Работа над проектом предполагает:
- Изучение доступной документации по данной технологии;
- Составление нескольких примеров по применению Silverlight для демонстации возможностей;
- Сравнительный анализ Silverlight и альтернативных возможностей (например, перенос бизнес-логики в VSTO);
- Собственно, разработка прототипа приложения;
- Подготовка заключения и рекомендаций.
Планируемый результат:
Готовое приложение и типовые рекомендации по использованию технологии Silverlight для разработки интранет-сайтов (основные проблемы программиста, возможные шаблоны архитектуры, возможность разработывать через тестирование (практика TDD), скорость разработки и т.д.).
Задача 3: Сравнительный анализ программ для измерения покрытия кода (code coverage tools)
Задача заключается в изучении различных средств измерения покрытия кода (code coverage tools), представленных на рынке, и сравнении их с разрабатываемым прототипом.
Планируемый результат:
- Выделение общих и специфических качеств (features) каждого из продуктов;
- Оценка производительности и качества результатов для распространенных коммерческих приложений;
- Оценка поведения программы при стрессовых нагрузках (стабильность);
- Оценка поведения и качества результатов при граничных условиях (corner cases), включает написание самостоятельных тестовых сценариев.
Требуемый уровень подготовки: Базовые знания об структуре исполняемого файла в ОС Windows & Linux, знание С++, навыки работы в Windows & Linux, знания об архитектурах IA32/Intel64 и их различиях.
Задача 4: Определение оптимальных конфигураций запуска анализатора корректности Intel® Parallel Inspector
Задача заключается в анализе различных возможных режимов работы новейшего продукта Intel® Parallel Inspector с целью нахождения параметров запуска, оптимальных по качеству результатов и затраченному времени на анализ пользовательского приложения. Не секрет, что в случае глубокого анализа программ (особенно многопотоковых) на наличие ошибок работы с памятью или с потоками накладные расходы на анализ могут многократно превышать время работы самой программы. Однако если есть возможность контролировать коллекцию результатов (например, за счет менее детального анализа каких-то параметров, или отключения какого-то вида анализа вообще), появляется возможность контролировать накладные расходы с целью увеличения производительности анализа.
Планируемый результат: Набор рекомендаций (базирующихся на прогоне популярных коммерческих программ с различными параметрами сбора данных), или предлагаемых «уровней анализа», сочетающих различные компромиссы между «глубиной» анализа и временем работы анализатора. Требуемый уровень подготовки: Общие представления о параллельном программировании, средствах отладки и проверки паралелльных программ, желательно знание Intel® Thread Checker, Intel® Thread Profiler, Numega** Bounds Checker**.
** Торговые марки 3х фирм являются собственностью их владельцев.
Задача 5: Параллельные технологии и инструменты в действии
Проект, предлагаемый отделом Инструментов Анализа, Профилировки и Паралеллизации, предполагает, что Вы:
- Имеете компьютерную программу – приложение, которое Вам интересно как специалисту и которую Вы либо разработали / сопровождаете сами, либо взяли из Open Source;
- Приложение написано на одном из языков: С, С++, Fortran;
- Приложение потребляет нетривиальное количество компьютерных ресурсов;
- Вы заинтересованы в ускорении данного приложения – например, с целью быстрее просчитывать модель, или чтобы реализовать дополнительные возможности;
- У Вас есть идеи по распараллеливанию кода приложения (а может быть, и начальный вариант параллельного кода).
Участвуя в нашем проекте, Вы сможете значительно ускорить свое приложение посредством параллелизации!
Наши инженеры помогут Вам освоить новейшие технологии параллельного программирования, методы профилирования и анализа программ, принципы оптимизации.
Для участия в данном проекте требуется совсем немного:
- Желание;
- Наличие приложения, над ускорением которого Вы бы хотели поработать.
Напишите нам о себе, о Вашем опыте программирования и о приложении.
Задача 6: Разработка физической модели разбиения твёрдого тела для игрового движка
Для продвинутых геймеров, любящих смаковать детали игры (и особенно для гейм-дизайнеров, любящих ввернуть в игру что-нибудь этакое), далеко не последним является вопрос всевозможных украшательств игры, не являющихся частью самого геймплея (т.е. основной нити игры) – например: красивые клубы дыма, идущие от самоходной установки, в которую попал снаряд, либо отражение луча прожектора от мокрых стен, либо "живая" вода, которая даёт волны от ног залезшего в неё героя. Разумеется, большинство из этих эффектных украшательств является ничем иным, как искусным инженерным обманом – гейм-дизайнер на самом деле комбинирует несколько текстур, возможно меняющихся в реальном времени, а глаз игрока думает, что это на самом деле дым.
Предметом особых спекуляций в игровой и околоигровой среде являются более-менее "честные" эффекты, построенные на базе "физического" моделирования. В данном случае для изготовления очередного игрового украшательства используется физическая модель определённой степени грубости, которая может быть применена, исходя из текущих ограничений и условий игры. Украшательств таких немало – например, разваливающиеся домики, дробящиеся кирпичи, рвущаяся одежда.
Основная часть.
Остановимся на одном из игровых моментов – хулиганском желании разбить окошко в домике. И не только окошко – дверь и т.д. Ещё лет 5 назад никакой надежды на физическую подоплёку такого явления не было – максимум, чем могли порадовать производители, была возможность получить заранее заданное разбиение объекта. В час "Х" объект просто распадался по заранее проведённым линиям.
Задачу в данном случае можно сформулировать следующим образом: Существует двумерная поверхность некоторой формы – для начала можно остановиться на прямоугольнике. К некоторой точке поверхности прикладывается импульс. Необходимо промоделировать процесс физического разбиения поверхности, учитывая следующие требования:
- Разбиение должно быть визуально корректным – игрок, видящий эти осколки, не должен сомневаться, что из них нельзя составить первоначальный объект. Хорошим примером может быть падение чего-либо тяжёлого на стекло, лежащее на полу – в этом случае визуальная корректность разбиения должна прослеживаться очень чётко.
- В зависимости от изменения физических свойств объекта должна меняться форма осколков и схема распространения трещин в материале. Пример: стекло и оргстекло. В первом случае удар порождает множество осколков (несколько "круговых" трещин и множество радиальных трещин"), во втором случае – только несколько трещин.
- Необходимо учитывать физические теории, объясняющие форму и распространение трещин в материале.
- Желательно сразу продумывать аспекты технической реализации, от которых зависит возможность интеграции алгоритма в игру:
- сколько надо памяти алгоритму для работы;
- сколько необходимо времени для работы алгоритма и на каком количестве процессоров;
- можно ли распараллелить алгоритм;
- можно ли применить команды векторной обработки данных (SIMD) для увеличения производительности алгоритма.
Задача 7: Разработка алгоритмов и блоков обработки сигналов для современных беспроводных систем связи
В рамках данной работы предполагается знакомство студентов с основными алгоритмами обработки сигналов, используемыми на физическом уровне современных беспроводных OFDM и OFDMA систем связи, таких как Wi-Fi, WiMAX или DVB-T. В процессе работы над проектом будет выполнено построение программной модели изучаемой системы связи (симулятора). После разработки общего программного симулятора каждый из студентов получит индивидуальное задание по созданию одного из блоков обработки сигналов, используемого в OFDM системах связи, на языке описания аппаратуры Verilog.
Задача 8: Разработка примера использования библиотеки Intel® Threading Building Blocks
Предлагается разработать пример кросс-платформенной программы для многоядерных систем, демонстрирующей совместное использование Intel® Threading Building Blocks и операций ввода-вывода для файлов и/или сети для достижения масштабируемой производительности. Язык разработки: C++. Для примера Вы можете предложить свою задачу или развить следующую: программа может функционировать как веб-сервер, предоставляя по запросу клиентов определённые данные, требующие вычислений (и хранения) на стороне сервера. Для участия в проекте необходимо:
- Изучить возможности TBB, используя документацию, примеры и исходные тексты, доступные на сайте http://www.threadingbuildingblocks.org;
- Изучить возможности кросс-платформенной библиотеки организации ввода-вывода, например, входящей в состав Boost (http://www.boost.org/), или другой по Вашему выбору;
- Предложить концепцию организации программы в виде текста описания, диаграмм, псевдокода или исходного кода.
Участвуя в нашем проекте, Вы сможете получить навыки проектирования современных приложений для многоядерных систем, разобраться в особенностях организации вычислений для максимального использования аппаратных ресурсов, попрактиковаться в разработке масштабируемых многопоточных программ.
Задача 9: Алгоритмы для оценки лучшего качества и выбора разбиения/типа макроблока/типа компенсации движения
Необходимо провести исследовательскую работу и придумать алгоритмы для оценки лучшего качества и выбора разбиения/типа макроблока/типа компенсации движения. Исследование включает в себя работу с программой для сжатия H.264 видео. Результаты оцениваются с помощью тестового сжатия эталонных видео-последовательностей и сравнения конечного качества сжатой последовательности до и после «улучшений». Требуемый уровень подготовки: Знание языка C\C++, принципов отладки и построения программного обеспечения, основ видео-сжатия.
Задача 10: Проблемы растеризации сцен
Художники любят оперировать с полигонами, в общем случае невыпуклыми. Современное графическое железо работает исключительно с треугольниками. Следовательно, при растеризации некоторых сцен нам потребуется:
Задача 10.1: Триангуляция невыпуклых многоугольников.
В 3д сценах присутствуют как видимые геометрические объекты, так и невидимые вспомогательные объекты, связанные с видимыми. При многократном перекраивании сцены могут появляться объекты-сироты, ни с кем не связанные и невидимые. В конечном продукте наличие таких моделей недопустимо, следовательно, возникает:
Задача 10.2: Выбрасывание «мертвых» объектов и ссылок.
Часто художник использует множество файлов текстур, которые разбросаны по файловой системе его рабочего компьютера. Наличие в конечной сцене как абсолютных путей, так и длинных относительных путей недопустимо. Следовательно, нам необходимо:
Задача 10.3: Перекладывание внешних ресурсов (картинок).
Для анимации 3д моделей часто используется анимация по ключевым кадрам с заданной интерполяцией между ними. Часто при сохранении сцены такие анимации сэмплируются, и значения анимируемого параметра сохраняются для каждого кадра. Такие сцены занимают много памяти и требуют больших вычислительных ресурсов во время выполнения в реальном времени. Для уменьшения размеров сцен, увеличения скорости работы и скорости загрузки нам нужно:
Задача 10.4 (повышенной сложности): Ресэмплинг анимационных кривых.
Все задачи предлагается выполнить в виде плагинов к open source продукту COLLADA Refinery.
Задача 11: Технологии беспроводной связи***
Участники будут решать индивидуальные задачи и участвовать в интеграции компонент в систему, выполнять экспериментально-тестовые работы, получат навыки работы в команде в перспективном проекте, опыт применения различных современных технологий: беспроводные коммуникации, сенсорика, обработка сигналов, обработка видео информации и машинное зрение, создание специфических баз данных и знаний, искусственный интеллект и машинное обучение, опыт использования современного инструментария и технологий разработки программ.
Цель проекта – создание сервиса, позволяющего с помощью мобильного беспроводного устройства оперативно ориентироваться на территории университетского кампуса, получать информацию об объектах и предметах, находящихся на этой территории, а также иметь мобильный доступ к справочным данным по университету и университетским объявлениям.
Описание системы:
Этот прототип универсальной системы локального информирования предназначен для повышения эффективности взаимодействия с университетской инфраструктурой студентов, сотрудников университета и посетителей. Пользуясь системой, любой владелец сотового телефона, находящийся на территории университетского кампуса, может быстро сориентироваться на открытой территории или внутри зданий с отображением его положения на плане университетского кампуса. Ему предоставляется возможность идентифицировать находящийся вблизи него объект или предмет, а также найти требуемый объект (здание, аудиторию, площадку и т.д.), предмет или службу на территории кампуса.
Система построена по принципу клиент-серверного приложения. Программа-клиент (Java приложение) устанавливается на сотовом телефоне и позволяет пользователю считывать идентификационную информацию об окружающих объектах, специальным образом помеченных с помощью камеры и Bluetooth (WiFi) устройства телефона. По GPRS каналу идентификаторы объектов передаются на сервер, который возвращает в программу-клиент контекстную информацию об объекте или предмете, извлеченную из базы данных.
Предлагаемые задачи:
- 1) Создание системы ориентирования на территории университетского кампуса, как на открытом пространстве, так и внутри зданий.
- 2) Создание системы оперативного получения информации об объектах кампуса и предметах, расположенных на его территории.
- 3) Создание системы инвентаризации материальных ценностей в университете и предоставления оперативной информации о них с распределением прав доступа.
- 4) Создание системы распространения локальных объявлений.
- 5) Поисковые и справочные средства по университету, включая пространственно-временное ориентирование (где, что, когда было, есть, будет).
- 6) Создание интерфейса для добавления и структурирования информации об объектах и предметах, и самопополнения баз данных в стиле Wikipedia.
Используемые ключевые технологии:
- 1) Распределённая система серверов и баз данных, позволяющая агрегировать и обрабатывать информацию.
- 2) Считывание / распознавание QR и им подобных кодов с помощью мобильных телефонов.
- 3) Локальное позиционирование на основе Bluetooth (WiFi)-устройств.
- 4) Передача данных через Bluetooth, WiFi, GPRS, 3G.
- 5) Лексенографическая обработка информации.
*** Проект осуществляется совместно с Лабораторией физических основ беспроводной связи (WLab) ННГУ, созданной при поддержке компании Intel.
Задачи от ННГУ
Список задач производственной составляющей стажировки
Задача 12: Параллельные вычисления в задачах финансовой математики в системах с общей памятью
Данное направление относится к финансовой математике – разделу знаний, занимающемуся анализом финансовых рынков. Среди задач финансовой математики – определение справедливых цен финансовых инструментов, моделирование цен акций и курсов валют, выбор оптимальной стратегии поведения на рынке и др.
В предлагаемом проекте основное внимание уделяется вычислительным особенностям – эффективной реализации известных алгоритмов на современной аппаратуре – программирование, оптимизация кода, распараллеливание.
При распараллеливании акцент делается на достижение хорошей масштабируемости в системах с общей памятью – современных многоядерных CPU, сравнение с графическими ускорителями, с прицелом на системы на базе Intel Larrabee.
Направление представляет интерес для программирующих математиков, которые не боятся математических моделей и, в то же время, интересуются вопросами эффективного использования вычислительных ресурсов.
Задача 13: Параллельные вычисления в системах с общей памятью с использованием библиотеки Intel Threading Building Blocks
В предлагаемом проекте рассматривается один из инструментов параллельного программирования, предназначенный для распараллеливания решения задач в системах с общей памятью, – библиотека Intel Threading Building Blocks (TBB). Основная идея, заложенная в библиотеку, состоит в использовании стандартного высокоуровневого C++ для быстрой разработки кросс-платформенных, хорошо масштабируемых параллельных приложений. Наряду с указанным выше, использование библиотеки TBB предоставляет механизмы абстрагирования от парадигм многопоточного программирования, позволяя сосредоточиться непосредственно на решении прикладной задачи.
В проекте предполагается изучение принципов функционирования и вопросов эффективного использования TBB на примере классических модельных задач. Далее предполагается применение TBB для распараллеливания вычислений в актуальных прикладных задачах из разных областей знаний.
Проект будет интересен слушателям, имеющим навыки разработки объектно-ориентированных программ на C++, интересующимся разработкой параллельных программ.
Задача 14: Методы и программные средства параллельных вычислений для сложных проблем глобального поиска
Общая характеристика проблемы. Как известно, решение большинства научно-технических задач включает этапы выбора решений (оценки значения параметров, при которых показатели выбираемого решения являются наилучшими). В наиболее сложных случаях задачи выбора могут быть представлены как проблемы многомерной многоэкстремальной (глобальной) оптимизации. Как правило, такие проблемы являются вычислительно-трудоемкими, и их численное решение при реалистических затратах времени становится возможным только при самом широком использовании возможностей суперкомпьютерных технологий.
При выполнении проекта планируется следующие этапы работ:
Изучение проблематики проекта (методы многоэкстремальной оптимизации, параллельной программирование),
Разработка программных средств параллельных вычислений для решения вычислительно-трудоемких задач принятия решений на высокопроизводительных кластерных системах (при одновременном использовании большого – сотни и тысячи – числа процессоров),
Проведение массовых вычислительных экспериментов на многопроцессорных компьютерных системах по решению сложных задач глобального поиска.
Планируемые результаты проекта состоят в следующем:
Спектр разработанных программ для решения задач глобальной оптимизации,
Прототип программной системы параллельных вычислений,
Результаты проведенных вычислительных экспериментов,
Tезисы 1-2 докладов на Международную конференцию «Высокопроизводительные вычисления на кластерных системах» (Владимир, ноябрь 2009 г.)
При успешном выполнении проекта участники проекта получают понимание современного состояния проблематики глобального поиска, приобретают навыки параллельного программирования и практический опыт разработки сложного программного обеспечения для высокопроизводительных вычислительных систем.
Требуемый уровень подготовки. В рамках выполнения проекта предполагается органичное сочетание математических аспектов и проблем программирования. Тем самым, для участников проекта необходимым является базовый уровень математической подготовки, хорошие практические навыки программирования на одном из языков программирования. Желательно знание технологий параллельного программирования (MPI).
Для успешности проекта планируется постепенное нарастание сложности выполняемых работ. Для освоения тематики имеются все необходимые научно-технические материалы. Планируемое количество участников проекта – 3-4 человека.
Задача 15: Системы управления параллельными вычислениями для высокопроизводительных многопроцессорных кластерных систем
Общая характеристика проблемы. Современные высокопроизводительные кластеры являются сложными компьютерными системами, имеющиеся в своем составе сотни и тысячи процессоров. Для эффективного использования таких систем является необходимым, с одной стороны, организация простого доступа для пользователей (вычислителей) кластерных систем, а, с другой стороны, автоматизация управления такими сложными многопроцессорными комплексами.
При выполнении проекта планируется следующие этапы работ:
Изучение проблематики проекта (примеры существующих суперкомпьютеров, анализ существующих систем управления кластерами),
Изучение и программная реализация методов планирования вычислительных ресурсов в многопроцессорных кластерных системах,
Изучение и программная реализация методов мониторинга и сбора статистики вычислительных ресурсов в многопроцессорных кластерных системах.
Планируемые результаты проекта состоят в следующем:
Прототип программ планировщика и мониторинга для системы управления кластерами,
Результаты проведенных вычислительных экспериментов,
Тезисы докладов на Международную конференцию «Высокопроизводительные вычисления на кластерных системах» (Владимир, ноябрь 2009 г.)
При успешном выполнении проекта участники проекта получают понимание современного состояния проблематики управления ресурсами высокопроизводительных вычислительных систем и приобретают практический опыт разработки сложного программного обеспечения для высокопроизводительных вычислительных систем.
Требуемый уровень подготовки. Для участников проекта необходимым является базовый уровень математической подготовки, хорошие практические навыки программирования на одном из языков программирования. Желательно знание технологий параллельного программирования (MPI).
Для успешности проекта планируется постепенное нарастание сложности выполняемых работ. Для освоения тематики имеются все необходимые научно-технические материалы.
