Розділ 2. Чисельні методи

З дисципліни

АЛГОРИТМИ І МЕТОДИ ОБЧИСЛЕНЬ

Для спеціальності: 5.05010201

ОБСЛУГОВУВАННЯ КОМП'ЮТЕРНИХ СИСТЕМ І МЕРЕЖ

Загальна кількість годин 22 години

Практичні роботи розроблені на основі

навчальної програми дисципліни

затвердженої комісією «Інформатики та комп'ютерної техніки

від «_03_» вересня 2012 р.

Практичні роботи розроблені Бєзмєнової О.Ю.

Розглянуті та схвалені на засіданні циклової комісії «Інформатики та комп'ютерної техніки» Протокол № 1 от «03» вересня 2012 р. Голова циклової комісії __________Бєзмєнова О.Ю.

Розділ 1. Алгоритмізація

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. Що називають конфігурацією машини Тьюрінга у момент часу t?

26. Що повністю задає роботу машини Тьюрінга?

27. Що представляє собою нормальний алгоритм Маркова?

28. Що потрібно задати для опису нормального алгоритму Маркова?

29. Що представляє собою асоціативне числення?

30. Які слова утворюють дедуктивний ланцюжок?

31. Коли нормальні алгоритми Маркова вважають еквівалентними?

32. Коли функцію називають нормально обчислюваною?

33. Коли зупиняється робота нормального алгоритму Маркова?

34. Що представляють собою рекурсивні функції?

35. Які є основні алгоритми сортування та пошуку інформації?

36. Що представляє собою часова та місткісна складність алгоритмів?

Розділ 2. Чисельні методи

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. Як відбувається статистична перевірка гіпотез?

43. Що представляють собою розподіли випадкових величин?

44. Які є числові характеристики вибірки?

45. Що представляють собою регресійний та кореляційний аналізи?

1. Из каких этапов состоит решение любой задачи на ЭВМ?

Ответ:

Решение любой задачи на ЭВМ состоит из нескольких этапов, а именно:

- Постановка задачи;

- Формализация (математическая постановка задачи);

- Выбор (или разработка) метода решения;

- Разработка алгоритма;

- Составление программы;

- Отладка программы;

- Вычисление и обработка результатов.

Наряду с этими этапами пользователь в процессе решения задачи может выполнять также следующие:

- Выбор языка программирования;

- Описание структуры данных;

- Оптимизация программы;

- Тестирование;

- Документирование и др.

2. Что представляет собой информационная модель?

Информационная модель — модель объекта, представленная в виде информации, описывающей существенные для данного рассмотрения параметры и переменные величины объекта, связи между ними, входы и выходы объекта и позволяющая путём подачи на модель информации об изменениях входных величин моделировать возможные состояния объекта. Информационная модель — совокупность информации, характеризующая существенные свойства и состояния объекта, процесса, явления, а также взаимосвязь с внешним миром.

Информационные модели делятся на описательные и формальные.

Описательные информационные модели - это модели, созданные на естественном языке (т.е. на любом языке общения между людьми: английском, русском, китайском, мальтийском и т.п.) в устной или письменной форме.

Формальные информационные модели - это модели, созданные на формальном языке (т.е. научном, профессиональном или специализированном). Примеры формальных моделей: все виды формул, таблицы, графы, карты, схемы и т.д.

3. Что называют алгоритмом?

Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время.

4. Кто может быть исполнителем алгоритма?

Исполнитель алгоритма - это человек или автомат (в частности, им может быть процессор ЭВМ), умеющий выполнять некоторый, вполне определенный набор действий, т.е объект, умеющий выполнять определенный набор действий (команд).

5. Что подразумевают под формальным выполнением алгоритма?

Формализация - построение математической модели рассматриваемого явления. В результате анализа сути задачи определяется объем и специфика данных, вводится система условных обозначений, устанавливается принадлежность решаемой задачи к одному из известных классов задач, выбирается соответствующий математический аппарат.

Формальное выполнение алгоритма позволяет выполнять заданные действия (команды) различным техническим устройствам (исполнителям).

6. Какие свойства должен иметь алгоритм?

- Детерминированность(определенность, точность) - через полную однозначность правил, установленных в алгоритме, применение алгоритма к одинаковых входных данных должно приводить к одинаковому результату;

- Дискретность - процесс, который определяется алгоритмом, можно расчленить (разделить) на отдельные элементарные этапы (шаги), каждый из которых называется шагом алгоритмического процесса или алгоритма;

- Массовость(понятность) - алгоритм должен быть пригодным для решения всех задач определенного типа. Например, алгоритм для решения системы линейных уравнений должен быть пригодным для системы, состоящей из произвольного количества уравнений, причем для него существует множество данных, которые допускаются в качестве входных, то исходная система величин может выбираться из некоторой потенциально бесконечного множества;

- Результативность - указывает на наличие таких вариантов входных данных, для которых вычислительный процесс, который реализуется по предоставленному алгоритму, должен через конечное число этапов (шагов) остановиться и дать искомый результат или сигнал о том, что предоставленный алгоритм неприменим для решения поставленной задачи. (Обязательное получение результата за конечное число шагов)

7. Какие существуют формы записи алгоритмов?

Формы записи алгоритма:

- Словесная или вербальная (речевая, формульно-словесная)

- Псевдокод (формальные алгоритмические языки);

- Схемная (структурограмы, графическая).

8. Какие можно выделить уровни языков программирования в зависимости от степени детализации предписаний?

1. машинные;

2. машинно-оpиентиpованные (ассемблеpы);

3. машинно-независимые (языки высокого уровня).

9. Перечислите основные компоненты алгоритмического языка