Участник:StasFomin/Innopolis/Wtf — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(→‎3. Структура и содержание дисциплины)
 
(не показаны 22 промежуточные версии этого же участника)
Строка 1: Строка 1:
−
https://eduwiki.innopolis.university/index.php/BSc:_EfficientAlgorithms
+
Требуемая страница
 +
* https://eduwiki.innopolis.university/index.php/BSc:_EfficientAlgorithms
 +
 
 +
Зарегистрироваться-залогинится не дает:
 +
[[File:Wtf_2024-03-30_21-18-38_image0.png|360px|right]]
 +
[[File:Wtf_2024-03-30_21-16-36_image0.png|360px|center]]
 +
 
 +
Поэтому копируйте отсюда:
  
 
= Эффективные алгоритмы для труднорешаемых задач =
 
= Эффективные алгоритмы для труднорешаемых задач =
 
: '''Квалификация выпускника''': бакалавр
 
: '''Квалификация выпускника''': бакалавр
−
: '''Направление подготовки''':  09.03.01 - “Информатика и вычислительная техника”
+
: '''Направление подготовки''':  Направление 01.04.02 «Прикладная математика и информатика».
−
: '''Направленность (профиль) образовательной программы''': Математические основы ИИ
+
: '''Направленность (профиль) образовательной программы''': «Системное программирование и компьютерные науки». Образовательная программа «Вычислительная математика».
 
: '''Программу разработал(а)''': Фомин С.А.
 
: '''Программу разработал(а)''': Фомин С.А.
  
 
== 1. Краткая характеристика дисциплины ==
 
== 1. Краткая характеристика дисциплины ==
 +
<!--- булшит про ИИ оставил, судя по примерам это всем курсам надо, от арифметики и выше --->
 
Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области программного обеспечения и его разработки; искусственного интеллекта и его применения для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают:
 
Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области программного обеспечения и его разработки; искусственного интеллекта и его применения для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают:
 
* Теорию сложности, для определения  
 
* Теорию сложности, для определения  
Строка 18: Строка 26:
 
** вероятностные алгоритмы, и эвристики их порождения — методы Монте-Карло, вероятностного округления и т.п.
 
** вероятностные алгоритмы, и эвристики их порождения — методы Монте-Карло, вероятностного округления и т.п.
 
** методы дерандомизации — получения детерминированных приближенных алгоритмов из вероятностных.
 
** методы дерандомизации — получения детерминированных приближенных алгоритмов из вероятностных.
−
+
* Практические методы программирования для реализации всего перечисленного.
 +
 
 
== 2. Перечень планируемых результатов обучения ==
 
== 2. Перечень планируемых результатов обучения ==
−
: '''Целью освоения дисциплины''' является формирование общего понимания высокоэффективной реализации общих вычислительных алгоритмов с использованием процессоров различных типов и архитектур, а также демонстрация современных подходов к вычислительным алгоритмам на базе технологий машинного обучения.
+
В ходе курса студенты научатся:
 +
* Оценивать вычислительную сложность алгоритмических задач (в терминах вычислительных ресурсов).
 +
* Классифицировать алгоритмические задачи их в основных сложностных классах — базовое ориентирование в огромном «зоопарке» классов сложности — студенты познакомятся с известными теоремами и открытыми гипотезами о соотношении сложностей задач.
 +
* Устанавливать связи между сложностными классами.
 +
* Выделять  сложнорешаемые и практически решаемые алгоритмические задачи.
 +
* Для трудноразрешимых задач, строить приближенные и вероятностные алгоритмы и дерандомизировать некоторые из них — познакомиться с несколькими красивыми и широко используемыми в узких кругах полиномиальными алгоритмами.
 +
* Практически решать на Python классические задачи (возможность в дальнейшем использовать полученные навыки в дальнейшей работе по окончании ВУЗа), применение классических эвристик — «жадность», «динамическое программирование», известных алгоритмов на сортировки и графы и т.п.
 +
* Использовать достижения программной индустрии — ЦЛП-солверы, SAT-солверы, Pyomo-формулировки для постановки и решения задач оптимизации.
 +
 
 +
Дисциплина участвует в формировании следующих компетенций образовательной программы:
 +
* «СПК-9» —  способность осуществлять математическую постановку задачи и решать ее современными оптимизационными методами для оптимального выбора средств защиты информации при ограничениях на их стоимость, габариты, энергопотребление и др.
 +
* «СПК-1» — способность осуществлять поиск, изучение, обобщение и систематизацию научно-технической информации, нормативных и методических материалов в сфере профессиональной деятельности, в том числе на иностранном языке.
 +
* «СПК-7»— способность разрабатывать научно-техническую документацию, готовить научно-технические отчеты, обзоры, публикации по результатам выполненных работ.
  
−
: '''Задачами дисциплины''' являются изучение технологий параллельного программирования на центральных, графических и нейропроцессорах, анализ вычислительных алгоритмов с целью выявления точек параллелизма (hotpoints) и узких мест (bottle necks), а также внедрение технологий искусственного интеллекта и нейронных сетей в классические вычислительные задачи.
 
  
 
=== Общая характеристика результата обучения по дисциплине ===
 
=== Общая характеристика результата обучения по дисциплине ===
−
: '''Знания:'''
+
;Знания:
−
*подходов к параллельному программированию,
+
:* теоретических моделей вычисления.
−
*архитектур современных процессоров,
+
:* классов сложности оптимизационных задач.
−
*программных моделей с общей памятью,
+
:* методов полиномиальной сводимости классических NP-полных задач.
−
*архитектуры современных графических процессоров,
+
:* методов анализа сложности детерминированных и вероятностных алгоритмов, анализа точности в среднем и «для почти всех исходных данных».
−
*основ выполнения вычислений общего назначения на разных платформах,
+
−
*современных подходов к программированию алгоритмов решения задач математики и физики.
+
  
−
: '''Умения:'''
+
;Умения:
−
*SIMD- и MIMD-программирование для CPU,
+
:* постановки оптимизационной формулировки для оптимизационной задачи
−
*SIMD-программирование для GPU,
+
:* использование ЦЛП и SAT-солверов
−
*выполнять синхронизацию потоков,
+
:* доказательство труднорешаемости оптимизационной задачи
−
*выполнять оптимизация общей памяти.
+
:* оценка сложности алгоритма, «в худшем» и «в среднем»
 +
:* оценка качества приближения алгоритма, «в худшем» и «в среднем»
  
−
: '''Навыки (владения):'''
+
;Навыки (владения):
−
*проведения анализ алгоритмов на предмет возможного параллелизма с выявлением "горячих точек" и "бутылочных горлышек",
+
:* программирование на Python
−
*применения современного параллельного программирования к методам статистики,
+
:* работа с Jupyter-ноутбуками
−
*решения систем алгебраических уравнений наиболее эффективным способом,
+
:* работа с IDE VSCode/code-server
−
*решения основных типов дифференциальных уравнений, встречающихся в широком спектре реальных задач,
+
:* использование фреймворка Pyomo, для постановки оптимизационных задач и решения их ЦЛП-солверами
−
*применения современных вычислительных алгоритмов на основе машинного обучения для решения различных типов дифференциальных уравнений.
+
:* Использование фреймворка pySAT для решения SAT-задач
  
 
== 3. Структура и содержание дисциплины ==
 
== 3. Структура и содержание дисциплины ==
−
{| class="wikitable" style="width:70%;"
+
<!--  
−
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
+
нафиг тут таблица,  
−
| style="width:10%" | №<br>п/п
+
* если даже не поставили нормальных экстеншнов для медиавики-таблиц.  
−
| style="width:30%" | Наименование раздела <br> дисциплины
+
* если два столбца никакие, а в одном ожидается куча текста.
−
| style="width:60%" | Содержание дисциплины по темам
+
* нафиг «номер по порядку», если на него нигде не будет ссылок.
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
  -->
−
| style="text-align:center;" | 1. || Введение в высокопроизводительные вычисления, OpenMP и OpenCL
+
−
||- Существующие суперкомпьютерные системы<br>- Модель общей памяти<br>- Подходы к программированию MIMD и SIMD<br>- Массивно-параллельные ускорители<br>- Иерархия памяти
+
−
|- style="background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 2. || Параллельные алгоритмы линейной алгебры
+
−
||- Матричное умножение: оптимизация производительности различных реализаций на основе различных типов памяти устройства<br>- Прямые методы решения СЛАУ: исключение Гаусса, разложение Холецкого, метод прогонки, параллельная реализация<br>- Итерационные методы решения СЛАУ: метод Якоби, метод Зейделя,  релаксационные методы, параллельная реализация
+
−
|- style="background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 3. || Параллельные методы решения дифференциальных уравнений
+
−
||- Решение систем обыкновенных дифференциальных уравнений<br>- Решение волнового уравнения<br>- Решение задачи теплопроводности<br>- Решение задачи Дирихле для уравнения Пуассона
+
−
|- style="background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 4. || Физически информированные нейронные сети
+
−
||- Основы нейронных сетей<br>- Основы методов оптимизации<br>- Принципы преобразования задач, записанных в терминах дифференциальных уравнений, в оптимизационные<br>- Повышение эффективности процедуры обучения
+
−
|- style="background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 5. || Параллельные методы Монте-Карло
+
−
||- Вычисление определенных интегралов<br>- Способы уменьшения дисперсии<br>- Генераторы псевдослучайных чисел<br>- Подходы к распараллеливанию методов Монте-Карло
+
−
|- style="background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 6. || Высокопроизводительные вычисления и современные языки программирования
+
−
  ||- Многопоточность в современных языках программирования<br>- Существующие обертки для OpenCL и CUDA<br>- Другие высокоуровневые подходы к параллельному программированию
+
−
|}
+
  
−
== 4. Методические и оценочные материалы ==
+
Полугодовой курс состоит из двух основных частей:  
−
===Задания для практических занятий:===
+
* Закладываются основы теории сложности вычислений, которые далее при желании можно развивать в различных направлениях.  
−
{| class="wikitable" style="width:70%;"
+
* Рассказывается о нескольких эффективных алгоритмах и подходах для решения труднорешаемых задач.  
−
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
+
−
| style="width:10%" | №<br>п/п
+
−
| style="width:30%" | Наименование раздела<br>дисциплины (модуля)
+
−
| style="width:60%" | Перечень рассматриваемых тем (вопросов)
+
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 1. || Введение в высокопроизводительные вычисления, OpenMP и OpenCL||1) Напишите программу, которая получает ID потока, печатает на консоли "Привет из потока #", печатает общее количество потоков из главного потока. Введите необходимые переменные локально, а затем сделайте их глобальными. Протестируйте программу. Используйте необходимые пункты для решения возникших проблем.<br>2) Напишите программу, которая хранит 3 массива фиксированной длины, инициализирует элементы массивов их индексами, печатает общее количество потоков из главного потока, суммирует элементы двух первых массивов и записывает их в третий, а также печатает результат из текущего потока. Запустите задачу в параллельной секции и с помощью параллельного цикла. Протестируйте программу. Попробуйте использовать параллельный цикл с параллельной секцией и без нее. Попробуйте измерить время вычислений.<br>3) Напишите программу, которая вычисляет определенный интеграл заданной функции на заданном интервале (с использованием метода трапеций). Протестируйте программу. Измерьте время вычисления.
+
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 2. || Параллельные алгоритмы линейной алгебры||1) Реализуйте матрично-векторное умножение в OpenMP и OpenCL. Обсудите различные технологии хранения данных.<br>2)Выполните матричное умножение, попробуйте оптимизацию.<br>3) Реализуйте методы развертки и редукции для полосато-матричного СЛАУ. Использование инструментария OpenMP и OpenCL для распараллеливания.<br>4) Решите СЛАУ с помощью итерационного алгоритма. Реализуйте решение с помощью подходов OpenMP и OpenCL.
+
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 3. || Параллельные методы решения дифференциальных уравнений||1) Реализуйте решение задачи распространения тепла с ленточной матрицей с помощью прямых методов.<br>2) Реализуйте решение задачи распространения тепла с ленточной матрицей с использованием итерационных методов.<br> 3) Сравните вычислительную производительность реализаций на CPU и GPU.<br>4) Реализуйте визуализацию вычислительных экспериментов.<br> 5) Напишите компьютерную программу, которая решает систему ОДУ, продумайте способы распараллеливания решения.
+
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 4. || Физически информированные нейронные сети||1) Напишите компьютерную программу, которая решает обыкновенное дифференциальное уравнение с помощью классических численных алгоритмов.<br>2) Напишите компьютерную программу, реализующую физически информированную нейронную сеть для решения обыкновенного дифференциального уравнения.<br>3) Заранее реализуйте процедуру сравнения. Протестируйте решение на различных уравнениях. Сделайте вывод о сходимости алгоритма и о процедуре обучения.<br>4) Реализуйте параллельную версию алгоритма. Сравните вычислительную производительность.
+
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 5. || Параллельные методы Монте-Карло||1) Реализуйте вычисление определенных интегралов с помощью классических квадратурных формул. Сравните погрешность вычислений с помощью метода Монте-Карло. Сравните время работы обоих подходов для достижения одинаковой точности.<br>2) Реализуйте технику уменьшения дисперсии для метода Монте-Карло. Проведите эксперименты, подтверждающие эффективность реализации.<br>3) Реализуйте генератор равномерного распределения. Проведите эксперименты по оценке корректности и производительности генератора.<br> 4) Реализуйте генератор нормального распределения. Проведите эксперименты по оценке корректности и эффективности работы генератора.
+
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 6. || Высокопроизводительные вычисления и современные языки программирования||Нет.
+
−
|}
+
  
−
===Текущий контроль успеваемости обучающихся по дисциплине:===
+
Основные вопросы курса: какие бывают вычислительные ресурсы, как подсчитывать их необходимое количество для решения данной алгоритмической задачи, как отличить решаемые на практике задачи от нерешаемых и как наиболее эффективно работать с решаемыми. Много внимания уделяется изучению различных сложностных классов, связей между ними и классификации конкретных задач.
−
{| class="wikitable" style="width:70%;"
+
−
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
+
−
| style="width:5%" | №<br>п/п
+
−
| style="width:20%" | Наименование раздела<br>дисциплины
+
−
| style="width:25%" | Форма текущего контроля<br>
+
−
| style="width:50%" | Материалы текущего контроля<br>
+
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 1.
+
−
| Введение в высокопроизводительные вычисления, OpenMP и OpenCL
+
−
| Проверка выполнения домашних заданий;<br>Тестирование (письменное или компьютерное)
+
−
| Тестирование (письменное или компьютерное)<br>
+
−
- Как включить поддержку OpenMP в проекте?<br>- Как определить, поддерживает ли GPU OpenCL или нет?<br>- Как собрать информацию о CPU?<br>- Как собрать информацию о GPU?<br>- Как выполнять код параллельно с использованием OpenMP?<br>- Как выполнять код параллельно на GPU?
+
−
|-
+
−
| style="text-align:center;" | 2.
+
−
| Параллельные алгоритмы линейной алгебры
+
−
| Проверка выполнения домашних заданий;<br>Тестирование (письменное или компьютерное);<br>Проверка разработки отдельных частей кода программного продукта
+
−
| Тестирование (письменное или компьютерное):<br>
+
−
- Что такое разреженные матрицы?<br>- Опишите особенности умножения разреженных матриц<br>- Объясните прямой и обратный путь разложения Гаусса<br>- Как составить схему решения метода прогонки?<br>- Как организовать итерации для приближенного решения СЛАУ?<br>- Как понять, нужно ли останавливать итерационный процесс или нет?<br>- Как оптимизировать алгоритмы умножения матриц с точки зрения затрат памяти и времени?
+
−
|
+
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 3.
+
−
| Параллельные методы решения дифференциальных уравнений
+
−
| Проверка выполнения домашних заданий;<br>Тестирование (письменное или компьютерное);<br>Проверка разработки отдельных частей кода программного продукта
+
−
| Тестирование (письменное или компьютерное):<br>
+
−
- Что такое волновое уравнение?<br>- Что такое уравнение  теплопроводности?<br>- Как задача теплопроводности связана с задачей диффузии?<br>- Как описать такие задачи с помощью дифференциальных уравнений?<br>- Что такое "преобразование" с точки зрения математики?<br>- Какие типы преобразований вы знаете для решения дифференциальных уравнений?<br>- Как численно решать системы обыкновенных дифференциальных уравнений?
+
−
|
+
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 4.
+
−
| Физически информированные нейронные сети
+
−
| Проверка выполнения домашних заданий;<br>Тестирование (письменное или компьютерное);<br>Проверка разработки отдельных частей кода программного продукта
+
−
| Тестирование (письменное или компьютерное):<br>
+
−
- Что такое нейронная сеть?<br>- Какова структура однослойного и многослойного перцептрона?<br>- Как переформулировать задачу Коши с начальным значением в терминах задачи оптимизации?<br>- Как оценить погрешность  алгоритма PINN?
+
−
<br>- В чем плюсы и минусы подхода PINN по сравнению с классическими численными методами?<br>- Как ускорить процедуру обучения с помощью параллельного программирования?
+
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 5.
+
−
| Параллельные методы Монте-Карло
+
−
| Проверка выполнения домашних заданий;<br>Тестирование (письменное или компьютерное);<br>Проверка разработки отдельных частей кода программного продукта
+
−
| Тестирование (письменное или компьютерное):<br>
+
−
- Что такое определенный интеграл?<br>- Каковы классические формулы квадратур?<br>- Что такое равномерное распределение?<br>- Что такое нормальное распределение?<br>- Как использовать распределения при построении генераторов случайных величин?<br>- Как использовать статистический подход для оценки определенного интеграла?<br>- Как вычислить число Пи с помощью метода Монте-Карло?
+
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
−
| style="text-align:center;" | 6. || Высокопроизводительные вычисления и современные языки программирования
+
−
|| Проверка выполнения домашних заданий;<br>Устный опрос;<br>Доклад
+
−
|| Темы докладов:<br>
+
−
- Обзор Nvidia CUDA<br>- Обзор OpenACC<br>- C# и многопоточное программирование (Task Parallel Library)<br>- C# и программирование графических процессоров Nvidia CUDA (AleaGPU и альтернативы)<br> -C# и программирование на GPU OpenCL (Cudafy.NET, или Cloo.NET и альтернативные варианты)<br>- Java и многопоточное программирование<br>- Программирование на Java и Nvidia CUDA GPU<br>- Программирование на Java и OpenCL GPU<br>- Python и многопоточное программирование<br>- Обзор программирования на Python и GPU<br>- Swift и многопоточное программирование<br>- Swift и программирование на GPU<br>- Go и многопоточное программирование<br>- Go и программирование на GPU<br>- Rust и многопоточное программирование и программирование на GPU<br>- Erlang и многопоточное программирование
+
−
|}
+
  
−
===Контрольные вопросы для подготовки к промежуточной аттестации:===
+
Как правило, в семестре разбираются следующие темы.
−
{| class="wikitable" style="width:70%;"
+
 
−
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
+
 
−
| style="width:10%" | №<br>п/п
+
;Формально об алгоритмах. Вычислительные модели:
−
| style="width:25%" | Наименование <br> раздела дисциплины
+
* Примеры простых алгоритмов
−
| style="width:65%" | Вопросы
+
* Random Access Machines
−
|-  style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
* Одно и много-ленточные Машины Тьюринга
−
| style="text-align:center;" | 1. ||Введение в высокопроизводительные вычисления, OpenMP и OpenCL
+
* Универсальная машина Тьюринга
−
||1) OpenMP: подпрограммы библиотеки времени выполнения, переменные окружения<br>2) Директивы компилятора OpenMP: секции parallel<br>3) Директивы компилятора OpenMP: синхронизация<br>4) OpenCL: платформа и модели выполнения<br>5) OpenCL: модель памяти
+
* Вычислимость и разрешимость
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
 
−
| style="text-align:center;" | 2. ||Параллельные алгоритмы линейной алгебры ||1) Матричная алгебра: разреженные матрицы<br>2) СЛАУ: устранение гаусса<br>3) СЛАУ: разложение Холецкого<br>4) СЛАУ: методы прогонки<br>5) СЛАУ: итерационные методы
+
;Временная и пространственная сложность алгоритмов:
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
* Классы DTIME, P, EXPTIME
−
| style="text-align:center;" | 3. ||Параллельные методы решения дифференциальных уравнений ||1) Волновые уравнения<br>2) Сеточные методы<br>3) Задача теплопроводности<br>4) Задача Дирихле для уравнения Пуассона<br>5) Системы обыкновенных дифференциальных уравнений и соответствующие решения
+
* Классы DSPACE, PSPACE
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
 
−
| style="text-align:center;" | 4. ||Физически информированные нейронные сети ||1) Физически обоснованные нейронные сети<br>2) PINN для решения обыкновенных дифференциальных уравнений<br>3) PINN и системы обыкновенных дифференциальных уравнений<br>4) PINN и частичные дифференциальные уравнения
+
;Полиномиальные сводимости и NP-полные задачи:
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
* Полиномиальные сводимости по Куку и Карпу.
−
| style="text-align:center;" | 5. ||Параллельные методы Монте-Карло ||1) Математический анализ: определенные интегралы и методы их вычислений<br>2) Статистика: свойства случайной величины<br>3) Статистика: равномерное распределение<br>4) Статистика: нормальное распределение<br>5) Метод Монте-Карло
+
* Классы NP, coNP, NPC
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
 
−
| style="text-align:center;" | 6. ||Высокопроизводительные вычисления и современные языки программирования
+
;Вероятностные вычисления и их сложность:
−
||1) Модель программирования Nvidia CUDA<br>2) Модель памяти Nvidia CUDA<br>3) Модель программирования OpenACC
+
* Классы «эффективно решаемых задач» RP, coRP, BPP
−
|}
+
* Класс «Безошибочно решаемых задач» ZPP
 +
* Неамплифицируемый класс PP
 +
 
 +
;Жадные алгоритмы и анализ их качества:
 +
* Жадные алгоритмы в задачах о покрытии о покрытии множеств и вершин
 +
* Жадный алгоритм в задаче о рюкзаке:
 +
 
 +
;Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке:
 +
* Динамическое программирование для задачи о рюкзаке
 +
* Использование жадных алгоритмов и эвристик округления для получения FPTAS-алгоритма
 +
 
 +
;Алгоритмы полиномиальные в среднем:
 +
* Полиномиальный в среднем алгоритм для задачи о рюкзаке:
 +
* Полиномиальный в среднем алгоритм для SAT:
 +
* Полиномиальный в среднем алгоритм для задачи упаковки:
 +
 
 +
;Приближенный алгоритм для метрической задачи коммивояжера
 +
;Вероятностные алгоритмы:
 +
* Вероятностная проверка тождеств
 +
* Вероятностный подсчет числа выполняемых наборов для ДНФ
 +
* Вероятностное округление для задач MAX-SAT и MAX-CUT
 +
;Дерандомизация: Детерминированный приближенный алгоритм для MAX-SAT, полученный из вероятностного алгоритма.
 +
;Неаппроксиминуемость:
 +
* Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема
 +
* PCP и аппроксимируемость
 +
 
 +
== 4. Методические и оценочные материалы ==
 +
=== Задания для практических занятий: ===
 +
См. примеры:
 +
* «[https://discopal.ispras.ru/%D0%9F%D1%80%D0%B0%D0%BA%D1%82%D0%B8%D0%BA%D1%83%D0%B5%D0%BC%D1%81%D1%8F_%D0%92_%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0%D1%85 Практикуемся в алгоритмах]»
 +
* «[https://discopal.ispras.ru/%D0%9C%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D1%82%D1%80%D1%83%D0%B4%D0%BD%D0%BE%D1%80%D0%B5%D1%88%D0%B0%D0%B5%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87 Моделирование труднорешаемых задач]»
 +
* «[https://discopal.ispras.ru/%D0%9C%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%B1%D0%B8%D0%B7%D0%BD%D0%B5%D1%81-%D0%B7%D0%B0%D0%B4%D0%B0%D1%87 Моделирование бизнес-задач]»
 +
* «[https://discopal.ispras.ru/%D0%A0%D0%B5%D1%88%D0%B0%D0%B5%D0%BC_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D1%83%D0%BF%D1%80%D0%B0%D0%B6%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F Решаем теоретические упражнения]»
  
−
===Вопросы/Задания к промежуточной аттестации в устной/письменной форме:===
+
=== Контроль успеваемости обучающихся по дисциплине: ===
−
#Что такое закон Амдала?
+
См. примеры тестов:
−
#Перечислите особенности #pragma parallel
+
* https://discopal.ispras.ru/Special:MediawikiQuizzer/Algs-innopolis-exam
−
#Какие типы модификаторов доступа к памяти вы знаете?
+
−
#Сравните секции parallel и задачи OpenMP
+
−
#Как синхронизировать потоки в OpenMP?
+
−
#Опишите структуру программы OpenCL
+
−
#Какие виды памяти в OpenCL вы знаете?
+
−
#Что такое ядра OpenCL?
+
−
#Перечислите сервисные операции OpenCL
+
−
#Как вычислить определенный интеграл?
+
−
#Что такое случайная переменная?
+
−
#Что такое генератор случайных величин?
+
−
#Как построить генератор случайных величин?
+
−
#Как работают методы Монте-Карло?
+
−
#Как выполнить умножение разреженных матриц?
+
−
#Перечислите прямые методы решения СЛАУ
+
−
#В чем разница между устранением Гаусса и разложением Холецкого?
+
−
#Объясните итерационный алгоритм решения СЛАУ на графе
+
−
#Как ускорить алгоритмы линейной алгебры с помощью многопоточного программирования?
+
−
#Как задать граничные условия для дифференциальных уравнений с частными производными?
+
−
#Как задать начальные условия для дифференциальных уравнений с частными производными?
+
−
#В чем разница между явными и неявными конечно-разностными схемами?
+
−
#Перечислите возможные способы решения задачи о распространении тепла в пластине.
+
−
#Переформулируйте поставленную задачу Коши в оптимизационную задачу.
+
−
#Что такое PINN-подход к дифференциальным уравнениям?
+
−
#Перечислите известные оптимизаторы и их особенности.
+
−
#Как избежать влияния начального условия на значение, выдаваемое нейронной сетью?
+
−
#Что делать с начальным распределением функции в задаче PDE, формулируя задачу оптимизации?
+
−
#Что делать с граничными условиями в PDE-задаче при формулировке задачи оптимизации?
+
−
#Как решить систему ODE с помощью PINN-подхода?
+
−
#Сравните Nvidia CUDA и OpenCL. В чем плюсы и минусы обоих наборов инструментов?
+
−
#Сравнение библиотек OpenACC и OpenMP: основные различия и цели другого подхода
+
−
#C#: библиотека параллельных задач
+
−
#Java: Runnable
+
−
#Python: модуль потоков
+
  
 
=== Перечень учебно-методического обеспечения дисциплины ===
 
=== Перечень учебно-методического обеспечения дисциплины ===
−
Список основной литературы:
+
Курс соединяет различные разделы теории сложности вычислений и изучение конкретных алгоритмов. Такой набор редко встречается в литературе, а по сложности вычислений на русском языке имеется совсем немного книг. Студентам предлагается использовать книгу лектора, а также книги на английском языке или книги по отдельным частям на русском.
−
#Barbara Chapman, Gabriele Jost, Ruud van der Pas. (2008) Using OpenMP: Portable Shared Memory Parallel Programming, The MIT Press,
+
−
#Scarpino, M. (2011) OpenCL in Action: How to Accelerate Graphics and Computations, Manning.
+
−
#Banger, R., Bhattacharyya, K. (2013) OpenCL Programming by Example, Packt Publishing.
+
−
#Sanders, J., Kandrot, E. (2010) CUDA by example: an introduction to general-purpose GPU programming, Addison-Weslye
+
  
−
Список дополнительной литературы:
+
;Основная книга: «[https://discopal.ispras.ru/%D0%A4%D0%B0%D0%B9%D0%BB:Book-advanced-algorithms.pdf Эффективные алгоритмы и сложность вычислений]»
−
#Введение в высокопроизводительные вычисления: [https://hpc.llnl.gov/documentation/tutorials/introduction-parallel-computing-tutorial introduction-high-performance-computing]
+
;Дополнительные материалы:  
−
#Введение в параллельное программирование: [http://www.hpcc.unn.ru/mskurs/cs338_pp_index.htm introduction-parallel-programming]
+
* https://discopal.ispras.ru/Дополнительные_материалы_по_сложности_вычислений
−
#Учебные материалы по OpenMP: [https://www.openmp.org/resources/tutorials-articles/ OpenMP-tutorials]
+
* https://discopal.ispras.ru/Дополнительные_материалы_по_приближенным_алгоритмам
−
#Учебные материалы по OpenCL: [https://www.nersc.gov/assets/pubs_presos/MattsonTutorialSC14.pdf OpenCL-tutorials]
+
* Н.Н. Кузюрин, С.А. Фомин, Эффективные алгоритмы и сложность вычислений», 2007 издательство МФТИ. ISBN 5-7417-0198-1.
 +
* S.Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
 +
* M. Sipser, Introduction to the Theory of Computation, Course Technology, 2005.
 +
* C.Moore, S. Mertens, The Nature of Computation, Oxford University Press, 2011
 +
* Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ, 3-е издание, Вильямс, 2019.
 +
* O. Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
 +
* A. Wigderson. Mathematics and Computation: A Theory Revolutionizing Technology and Science, Princeton University Press, 2019.
 +
* C.Papadimitriou, Computational Complexity, Addison Wesley, 1994
 +
* В.Н.Крупский. Введение в сложность вычислений, Москва, Факториал Пресс, 2006
 +
* С.А. Абрамов, Лекции о сложности алгоритмов, Москва, МЦНМО, 2009
 +
* Д.В.Мусатов. Курс лекций по сложности вычислений (видеолекций, конспекты).
 +
* М.Гэри, Д. Джонсон, Вычислительные машины и труднорешаемые задачи, Москва, Мир, 1982
 +
* М. Вялый, А. Китаев, А. Шень, Классические и квантовые вычисления, Москва, МЦНМО, 1999.
  
−
Необходимое программное обеспечение:
+
;Необходимое программное обеспечение для студентов: броузер.
−
#Microsoft VS Code / Microsoft Visual Studio / любая другая подходящая среда разработки на языке  C++
+
−
#GNU Plot
+
−
#OpenMP, OpenCL, CUDA библиотеки
+
  
 
=== Методические указания для обучающихся по освоению дисциплины ===
 
=== Методические указания для обучающихся по освоению дисциплины ===
 +
 +
Самостоятельная работа учащихся состоит:
 +
* в изучении лекционного материала, доступных видео и конспектов лекций учебно-методической литературы, включая базовую книгу авторов курса
 +
* подготовки к практическим заданиям текущего контроля и промежуточной аттестации:
 +
* тесты по всем материалам курса
 +
* решение теоретических задач по теории сложности
 +
* решение алгоритмических задач на языке Python
 +
* конструктивная постановка и исследование труднорешаемых задач с помощью ЦЛП и SAT-формулировок, с помощью технологий Jupyter Notebook, Pyomo и др.
 +
 +
 +
<!-- бессмысленный булшит, копирую, как есть -->
  
 
{| class="wikitable" style="width:80%;"
 
{| class="wikitable" style="width:80%;"
Строка 253: Строка 207:
  
 
=== Методы и технологии обучения, способствующие формированию компетенции ===
 
=== Методы и технологии обучения, способствующие формированию компетенции ===
−
{| class="wikitable"
+
<!-- нахер тут таблица -->
−
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
+
 
−
| Методы и технологии обучения, способствующие формированию компетенции
+
* Коллаборативное программирование и другая работа в реальном времени, см. доклад «[https://0x1.tv/20230128F Современные «интерактивные среды» и «живые лаборатории» — эффективное дистанционное образование по алгоритмам и математическим дисциплинам]»
−
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
* Обучающие вики-тесты, см. доклад «[https://0x1.tv/20150125K MediaWikiQuizzer или ВикиЭкзамены — тесты, удобные и для преподавателя и для студента]»
−
| Информационно-коммуникационная технология, проектная технология, технология проблемного обучения, кейс-технология, традиционные технологии, модульные технологии
+
* Коллаборативная среда на wiki-платформе, см. доклад «[https://0x1.tv/20170129D Эффективная «домашка» — задачи студентам на MediaWiki]»
−
|}
+
* Видеозаписи миникурсов, см. доклад «[https://0x1.tv/20190126Q OBS — швейцарский нож передачи знаний]»

Текущая версия на 14:35, 31 марта 2024

Требуемая страница

Зарегистрироваться-залогинится не дает:

Wtf 2024-03-30 21-18-38 image0.png
Wtf 2024-03-30 21-16-36 image0.png

Поэтому копируйте отсюда:

Эффективные алгоритмы для труднорешаемых задач

Квалификация выпускника: бакалавр
Направление подготовки: Направление 01.04.02 «Прикладная математика и информатика».
Направленность (профиль) образовательной программы: «Системное программирование и компьютерные науки». Образовательная программа «Вычислительная математика».
Программу разработал(а): Фомин С.А.

1. Краткая характеристика дисциплины

Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области программного обеспечения и его разработки; искусственного интеллекта и его применения для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают:

  • Теорию сложности, для определения
    • классов задач допускающих эффективное решение детерминированными и вероятностными алгоритмами — классы P, RP, ZPP, BPP и т.п.
    • классов задач, для которых считается невозможным существование эффективных алгоритмов точного решения — NP-complete, PSPACE-complete.
    • классов задач, для которых считается невозможным существование эффективных алгоритмов поиска приближенного решения — APX-complete.
  • Классические алгоритмы решения задач на графах и множествах (кратчайшие пути, покрытия, сортировки)
  • Алгоритмы, подходы и эвристики, для решения NP-полных задач:
    • приближенные алгоритмы с гарантированной точностью, включая алгоритмы с любой, заранее выбранной точностью — PTAS, FPTAS.
    • вероятностные алгоритмы, и эвристики их порождения — методы Монте-Карло, вероятностного округления и т.п.
    • методы дерандомизации — получения детерминированных приближенных алгоритмов из вероятностных.
  • Практические методы программирования для реализации всего перечисленного.

2. Перечень планируемых результатов обучения

В ходе курса студенты научатся:

  • Оценивать вычислительную сложность алгоритмических задач (в терминах вычислительных ресурсов).
  • Классифицировать алгоритмические задачи их в основных сложностных классах — базовое ориентирование в огромном «зоопарке» классов сложности — студенты познакомятся с известными теоремами и открытыми гипотезами о соотношении сложностей задач.
  • Устанавливать связи между сложностными классами.
  • Выделять сложнорешаемые и практически решаемые алгоритмические задачи.
  • Для трудноразрешимых задач, строить приближенные и вероятностные алгоритмы и дерандомизировать некоторые из них — познакомиться с несколькими красивыми и широко используемыми в узких кругах полиномиальными алгоритмами.
  • Практически решать на Python классические задачи (возможность в дальнейшем использовать полученные навыки в дальнейшей работе по окончании ВУЗа), применение классических эвристик — «жадность», «динамическое программирование», известных алгоритмов на сортировки и графы и т.п.
  • Использовать достижения программной индустрии — ЦЛП-солверы, SAT-солверы, Pyomo-формулировки для постановки и решения задач оптимизации.

Дисциплина участвует в формировании следующих компетенций образовательной программы:

  • «СПК-9» — способность осуществлять математическую постановку задачи и решать ее современными оптимизационными методами для оптимального выбора средств защиты информации при ограничениях на их стоимость, габариты, энергопотребление и др.
  • «СПК-1» — способность осуществлять поиск, изучение, обобщение и систематизацию научно-технической информации, нормативных и методических материалов в сфере профессиональной деятельности, в том числе на иностранном языке.
  • «СПК-7»— способность разрабатывать научно-техническую документацию, готовить научно-технические отчеты, обзоры, публикации по результатам выполненных работ.


Общая характеристика результата обучения по дисциплине

Знания
  • теоретических моделей вычисления.
  • классов сложности оптимизационных задач.
  • методов полиномиальной сводимости классических NP-полных задач.
  • методов анализа сложности детерминированных и вероятностных алгоритмов, анализа точности в среднем и «для почти всех исходных данных».
Умения
  • постановки оптимизационной формулировки для оптимизационной задачи
  • использование ЦЛП и SAT-солверов
  • доказательство труднорешаемости оптимизационной задачи
  • оценка сложности алгоритма, «в худшем» и «в среднем»
  • оценка качества приближения алгоритма, «в худшем» и «в среднем»
Навыки (владения)
  • программирование на Python
  • работа с Jupyter-ноутбуками
  • работа с IDE VSCode/code-server
  • использование фреймворка Pyomo, для постановки оптимизационных задач и решения их ЦЛП-солверами
  • Использование фреймворка pySAT для решения SAT-задач

3. Структура и содержание дисциплины

Полугодовой курс состоит из двух основных частей:

  • Закладываются основы теории сложности вычислений, которые далее при желании можно развивать в различных направлениях.
  • Рассказывается о нескольких эффективных алгоритмах и подходах для решения труднорешаемых задач.

Основные вопросы курса: какие бывают вычислительные ресурсы, как подсчитывать их необходимое количество для решения данной алгоритмической задачи, как отличить решаемые на практике задачи от нерешаемых и как наиболее эффективно работать с решаемыми. Много внимания уделяется изучению различных сложностных классов, связей между ними и классификации конкретных задач.

Как правило, в семестре разбираются следующие темы.


Формально об алгоритмах. Вычислительные модели
  • Примеры простых алгоритмов
  • Random Access Machines
  • Одно и много-ленточные Машины Тьюринга
  • Универсальная машина Тьюринга
  • Вычислимость и разрешимость
Временная и пространственная сложность алгоритмов
  • Классы DTIME, P, EXPTIME
  • Классы DSPACE, PSPACE
Полиномиальные сводимости и NP-полные задачи
  • Полиномиальные сводимости по Куку и Карпу.
  • Классы NP, coNP, NPC
Вероятностные вычисления и их сложность
  • Классы «эффективно решаемых задач» RP, coRP, BPP
  • Класс «Безошибочно решаемых задач» ZPP
  • Неамплифицируемый класс PP
Жадные алгоритмы и анализ их качества
  • Жадные алгоритмы в задачах о покрытии о покрытии множеств и вершин
  • Жадный алгоритм в задаче о рюкзаке:
Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке
  • Динамическое программирование для задачи о рюкзаке
  • Использование жадных алгоритмов и эвристик округления для получения FPTAS-алгоритма
Алгоритмы полиномиальные в среднем
  • Полиномиальный в среднем алгоритм для задачи о рюкзаке:
  • Полиномиальный в среднем алгоритм для SAT:
  • Полиномиальный в среднем алгоритм для задачи упаковки:
Приближенный алгоритм для метрической задачи коммивояжера
Вероятностные алгоритмы
  • Вероятностная проверка тождеств
  • Вероятностный подсчет числа выполняемых наборов для ДНФ
  • Вероятностное округление для задач MAX-SAT и MAX-CUT
Дерандомизация
Детерминированный приближенный алгоритм для MAX-SAT, полученный из вероятностного алгоритма.
Неаппроксиминуемость
  • Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема
  • PCP и аппроксимируемость

4. Методические и оценочные материалы

Задания для практических занятий:

См. примеры:

Контроль успеваемости обучающихся по дисциплине:

См. примеры тестов:

Перечень учебно-методического обеспечения дисциплины

Курс соединяет различные разделы теории сложности вычислений и изучение конкретных алгоритмов. Такой набор редко встречается в литературе, а по сложности вычислений на русском языке имеется совсем немного книг. Студентам предлагается использовать книгу лектора, а также книги на английском языке или книги по отдельным частям на русском.

Основная книга
«Эффективные алгоритмы и сложность вычислений»
Дополнительные материалы
  • https://discopal.ispras.ru/Дополнительные_материалы_по_сложности_вычислений
  • https://discopal.ispras.ru/Дополнительные_материалы_по_приближенным_алгоритмам
  • Н.Н. Кузюрин, С.А. Фомин, Эффективные алгоритмы и сложность вычислений», 2007 издательство МФТИ. ISBN 5-7417-0198-1.
  • S.Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
  • M. Sipser, Introduction to the Theory of Computation, Course Technology, 2005.
  • C.Moore, S. Mertens, The Nature of Computation, Oxford University Press, 2011
  • Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ, 3-е издание, Вильямс, 2019.
  • O. Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
  • A. Wigderson. Mathematics and Computation: A Theory Revolutionizing Technology and Science, Princeton University Press, 2019.
  • C.Papadimitriou, Computational Complexity, Addison Wesley, 1994
  • В.Н.Крупский. Введение в сложность вычислений, Москва, Факториал Пресс, 2006
  • С.А. Абрамов, Лекции о сложности алгоритмов, Москва, МЦНМО, 2009
  • Д.В.Мусатов. Курс лекций по сложности вычислений (видеолекций, конспекты).
  • М.Гэри, Д. Джонсон, Вычислительные машины и труднорешаемые задачи, Москва, Мир, 1982
  • М. Вялый, А. Китаев, А. Шень, Классические и квантовые вычисления, Москва, МЦНМО, 1999.
Необходимое программное обеспечение для студентов
броузер.

Методические указания для обучающихся по освоению дисциплины

Самостоятельная работа учащихся состоит:

  • в изучении лекционного материала, доступных видео и конспектов лекций учебно-методической литературы, включая базовую книгу авторов курса
  • подготовки к практическим заданиям текущего контроля и промежуточной аттестации:
  • тесты по всем материалам курса
  • решение теоретических задач по теории сложности
  • решение алгоритмических задач на языке Python
  • конструктивная постановка и исследование труднорешаемых задач с помощью ЦЛП и SAT-формулировок, с помощью технологий Jupyter Notebook, Pyomo и др.


Вид учебных
занятий/деятельности 		Деятельность обучающегося
Лекция Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практические (лабораторные) занятия Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
Самостоятельная работа Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка презентаций. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Доклад Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Дискуссия Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию.
Разработка отдельных частей кода Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
Выполнение домашних заданий и групповых проектов Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.
Индивидуальная работа При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
Тестирование (устное/письменное) При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.

Методы и технологии обучения, способствующие формированию компетенции

Источник — «https://discopal.ispras.ru/index.php?title=Участник:StasFomin/Innopolis/Wtf&oldid=28775»