Обсуждение участника:Сергей: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: «= Пункт 1 = Все пункты должны именоваться строго по шаблону. например, в данном случае, пер…»)
 
 
(не показано 10 промежуточных версий 2 участников)
Строка 1: Строка 1:
= Пункт 1 =
+
Хорошая работа, но есть несколько замечаний.
Все пункты должны именоваться строго по шаблону. например, в данном случае, первый уровень: "1 ЧАСТЬ. Свойства и структура алгоритмов"
+
 
 +
= Пункт 1.1 =
 +
 
 +
'''~ есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;'''
 +
 
 +
'''~ в каждой строке не превышает 10 в типичном случае;'''
 +
 
 +
'''~ ограничено <math>n^{1+\gamma}</math>, где <math>\gamma < 1</math>.'''
 +
 
 +
 
 +
- Если первое определение подходит только для “теоретического анализа”, то чем лучше третье?
 +
 
 +
- Второе определение, по-моему, не совсем корректно – оно слишком строгое, не понятно, что за типичный случай, почему именно используется привязка к строкам матрицы, почему именно 10 и т.д. Есть ли какие-то ссылки на литературу, где такое определение использовалось для анализа или для практических задач? Нужно пояснить смысл такого определения.
 +
 
 +
- В силу того, что определить разреженную матрицу строго не получается, то можно упомянуть то, что разреженными матрицами можно считать именно те, для которых применение специализированных алгоритмов обработки и/или хранения является оправданным (см., например, короткое обсуждение в Gilbert et al., Sparse Matrices in MATLAB: Design and Implementation, 1992)
 +
 
 +
 
 +
'''Огромные разрежённые матрицы часто возникают при решении таких задач, как дифференциальное уравнение в частных производных.'''
 +
 
 +
Это предложение нужно переформулировать. Разреженные матрицы часто возникают при решении дифференциальных уравнений именно численными методами.
 +
 
 +
 
 +
'''Более того, разреженный строчный формат обеспечивает эффективный доступ к строчкам матрицы; доступ к столбцам по прежнему затруднен. Поэтому предпочтительно использовать этот способ хранения в тех алгоритмах, в которых преобладают строчные операции.'''
 +
 
 +
Что здесь понимается под эффективностью доступа к строкам матрицы и тем, что доступ к столбцам затруднен? Если речь идет об устройстве компьютерной памяти, то это нужно пояснить, поскольку до этого в разделе описывается просто структура данных.
 +
 
 +
 
 +
= Пункт 1.2 =
 +
 
 +
'''Пусть матрица размером <math>N\times M</math> содержит в себе <math>NZ</math> ненулевых элементов, где <math>NZ\ll N^2</math>'''
 +
 
 +
Из этого определения можно получить матрицу со всеми ненулевыми элементами при <math>N \gg M</math>, тогда <math>N M \ll N^2</math>
 +
 
 +
 
  
 
= Пункт 1.3 =
 
= Пункт 1.3 =
Лучше избегать ссылок на соседние пункты. Подразделы д.б. самодостаточны.
 
  
= Пункт 1.4 =
+
'''Итого: <math>NZ</math> умножений + <math>x</math> сложений(<math>NZ-N<x<NZ-1</math>).'''
Следует просто привести описание макроструктуры, без ссылки на другие пункты.
+
 
 +
Оценка для операций сложения здесь не до конца правильная (например, если матрица нулевая). Лучше оценку записать в форме равенства. Или вообще не рассматривать случай нулевых строк.
  
= Пункт 1.5 =
 
Добавить описание к псевдокоду.
 
Если заимствован, дать ссылку на источник.
 
  
 
= Пункт 1.6 =
 
= Пункт 1.6 =
Указать итоговую сложность.
 
  
= Пункт 1.7 =
+
'''<math>\bullet \ x</math> сложений(<math>NZ-N<x<NZ-1</math>).'''
Оформить как рисунок с номером и подписью.
+
 
Если рисунок заимствован, надо дать ссылку на источник.
+
См. пункт 1.3
 +
 
 +
'''Всего <math>2NZ</math> операций, где <math>NZ</math> - количество ненулевых элементов.'''
 +
 
 +
Почему <math>NZ + x = 2NZ?</math>
 +
 
 +
 
 +
= Пункт 1.9 =
 +
 
 +
'''Для матрицы размером <math>N\times M</math>, содержащей в себе <math>NZ</math> ненулевых элементов, где <math>NZ\ll N^2</math>,'''
 +
 
 +
См. пункт 1.2
 +
 
 +
 
 +
= Пункт 1.10 =
 +
 
 +
'''Данный алгоритм обладает свойством детерминированности.'''
 +
 
 +
Будет ли влиять выполнение свойства ассоциативности для сложения на детерминированность алгоритма?
 +
 
 +
 
 +
= Пункт 2.4 =
 +
 
 +
Включает ли численный эксперимент генерацию матрицы? Нужно также указать размерность самой матрицы, помимо числа ненулевых элементов. 
 +
 
 +
'''Можно заметить небольшой всплеск эффективности при использовании 64 процессоров.'''
 +
 
 +
С чем связан этот «всплеск»? С алгоритмом, программой или вычислительной системой?
  
= Пункт 2 =
 
Аналогично, именование пункта д.б. по шаблону.
 
  
 
= Пункт 2.7 =
 
= Пункт 2.7 =
Добавить ссылки на реализации.
 
  
= Литература =
+
опечатка - '''... также математических пакет [http://matlab.ru/products/matlab Matlab] имеет собственную реализацию.'''
Отсутствует раздел источников, необходимо добавить.
 

Текущая версия на 01:34, 1 декабря 2016

Хорошая работа, но есть несколько замечаний.

1 Пункт 1.1

~ есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;

~ в каждой строке не превышает 10 в типичном случае;

~ ограничено [math]n^{1+\gamma}[/math], где [math]\gamma \lt 1[/math].


- Если первое определение подходит только для “теоретического анализа”, то чем лучше третье?

- Второе определение, по-моему, не совсем корректно – оно слишком строгое, не понятно, что за типичный случай, почему именно используется привязка к строкам матрицы, почему именно 10 и т.д. Есть ли какие-то ссылки на литературу, где такое определение использовалось для анализа или для практических задач? Нужно пояснить смысл такого определения.

- В силу того, что определить разреженную матрицу строго не получается, то можно упомянуть то, что разреженными матрицами можно считать именно те, для которых применение специализированных алгоритмов обработки и/или хранения является оправданным (см., например, короткое обсуждение в Gilbert et al., Sparse Matrices in MATLAB: Design and Implementation, 1992)


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

Это предложение нужно переформулировать. Разреженные матрицы часто возникают при решении дифференциальных уравнений именно численными методами.


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

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


2 Пункт 1.2

Пусть матрица размером [math]N\times M[/math] содержит в себе [math]NZ[/math] ненулевых элементов, где [math]NZ\ll N^2[/math]

Из этого определения можно получить матрицу со всеми ненулевыми элементами при [math]N \gg M[/math], тогда [math]N M \ll N^2[/math]


3 Пункт 1.3

Итого: [math]NZ[/math] умножений + [math]x[/math] сложений([math]NZ-N\lt x\lt NZ-1[/math]).

Оценка для операций сложения здесь не до конца правильная (например, если матрица нулевая). Лучше оценку записать в форме равенства. Или вообще не рассматривать случай нулевых строк.


4 Пункт 1.6

[math]\bullet \ x[/math] сложений([math]NZ-N\lt x\lt NZ-1[/math]).

См. пункт 1.3

Всего [math]2NZ[/math] операций, где [math]NZ[/math] - количество ненулевых элементов.

Почему [math]NZ + x = 2NZ?[/math]


5 Пункт 1.9

Для матрицы размером [math]N\times M[/math], содержащей в себе [math]NZ[/math] ненулевых элементов, где [math]NZ\ll N^2[/math],

См. пункт 1.2


6 Пункт 1.10

Данный алгоритм обладает свойством детерминированности.

Будет ли влиять выполнение свойства ассоциативности для сложения на детерминированность алгоритма?


7 Пункт 2.4

Включает ли численный эксперимент генерацию матрицы? Нужно также указать размерность самой матрицы, помимо числа ненулевых элементов.

Можно заметить небольшой всплеск эффективности при использовании 64 процессоров.

С чем связан этот «всплеск»? С алгоритмом, программой или вычислительной системой?


8 Пункт 2.7

опечатка - ... также математических пакет Matlab имеет собственную реализацию.