- •7. Разработка эффективных алгоритмов: методы «Разделяй и влавствуй» и динамическое программирование.
- •2. Общие принципы код-я информации и формы ее представления в эвм
- •5. Анализ алгоритмов сортировки: обменная сортировка методом «пузырька», метод «простого выбора».
- •17. Анализ алг-мов поиска: послед-ый поиск в неупорядоч .Массиве, бинарный поиск в упорядоч. Массиве.
- •6. Разработка эффективных алгоритмов: методы «Разделяй и влавствуй» и «Балансировки».
- •8. Разработка эффективных алгоритмов: методы жадные алгоритмы. Задача о выборе заявок. Принцип жадного выбора.
- •Задача о выборе заявок
- •9. Алгоритм: содержательный и формализованный подходы к понятию «алгоритм». Свойства алгоритма и способы его описания.
- •10.Линейность, ветвление и цикл. Их реализация в языках программирования.
- •21. Классификация ппо. Текстовые редакторы, издательские системы. Технологии обработки текстовой информации.
- •4. Задача сортировки. Алгоритмы сортировки. Сортировка и индексирование.
- •12. Логические яп. Декларативность программ. Решение логических задач.
- •13. Функц яп. Декларативность прогтамм. Лямбда-исчислениею
- •29. Накопители инф-ции, принципы их действия. Физ. И лог. Стр-ра диска.
- •14. Языки программирования. Основные элементы. Обзор и классификация. Методологии программирования.
- •15. Понятие типа данных. Простые (базовые) типы данных. Ссылочный тип.
- •16. Структурированные типы данных (массивы, записи, множества, файлы)
- •18. Объектно-ориентированное программирование. Инкапсуляция. Наследование. Полиморфизм.
- •19. Программное обеспечение эвм. Операционные системы. Развитие ос. Оболочки ос.
- •20. Программное обеспечение эвм. Сервисные программы (антивирусы, архиваторы, дефрагментаторы, диагностика и отладка).
- •22. Классификация ппо. Табличная организация информации. Табличные модели. Табличные процессоры.
- •11. Подпрограммы. Их реализ. В яп. Рекурсия, модул. Пр-ние
- •23. Классификация ппо. Базы данных. Проектирование баз данных. Субд.
- •25. Реляционная алгебра. Операции над таблицами.
- •26. Эвм как средство обработки информации. Класс-кация эвм. Перспективы раз-ия вт
- •45. Нейр. Сети. Одн. Перцептр. Актив. Ф-ия. Лог. Операц. На основе прст. Перцептр.
- •27. Понятие архитектуры эвм. Центральные устройства эвм, их наз-е и характеристики
- •28. Устройства ввода и вывода информации, их назначения и функции.
- •30. Базовая эталонная модель взаимодействия открытых систем международной организации стандартизации и ее значение в развитии телекоммуникации.
- •Взаимодействие уровней модели osi
- •31. Протоколы общения компьютеров в сети (ip, tcp, udp, ftp, smpt, http, nntp) и интерфейсы. Области взаимодействия открытых сетей.
- •32. Принципы функционирования локальных вычислительных сетей. Основные компоненты и типы лвс. Одноранговые сети. Сети на основе сервера. Комбинированные сети.
- •33. Основные типы кабельных сред передачи данных. Узкополосная и широкополосная передача сигналов. Асинхронная передача и автоподстройка. Сетевой адаптер.
- •34. Беспроводные сети. Передача "точка-точка". Инфракрасные лазерные лвс. Беспроводные лвс с радиопередачей. Мобильные сети.
- •35. Классификация моделей. Моделирование физических процессов. Понятие вычислительного эксперимента, его этапы и фазы. Области применения вычислительного эксперимента.
- •36. Моделирование стохастических систем. Моделирование случайных величин с равномерным распределением. Методы проверки случайности данных.
- •37. Приближенное число. Абсолютная и относительная погрешности. Виды, основные источники, способы устранения погрешностей.
- •38. Решение уравнений методами бисекций и итераций.
- •40. Постан. З-чи интер-ния. Интер-ный многоч. Сплайны.
- •43. Обработка результатов наблюдений. Уточнение параметров методом средних и методом наименьших квадратов.
- •44. Нечеткая логика. Ф. Принадлежности. Ф. Ограничения. Основные операции в нечеткой логике.
- •46. Нейр. Сети. Обуч. С пом-ю алгор. Обр. Распр.
- •54. Алгебра высказываний. Нормальные формы. Совершенные нормальные формы. Теорема существования нормальной формы. Приложение алгебры высказываний к логико-математической практике.
- •47. Знания. Классификация. Экспертные системы. Искусственный интеллект
- •48. Представление знаний (логическая модель, семантические сети, фреймы, продукции).
- •49. Представление задачи оптимизации в канонической, стандартной и матричной форме. Постановка задачи линейного программирования. Математическая модель все типов задач линейного программирования.
- •50. Решение задач линейного программирования графическим методом.
- •1. Система огранич-й представл. В канонич. Видет
- •2. Пусть система огр-ий злп представлена в виде:
- •3. Пусть система ограничений злп представлена в виде
- •52. Элементы теории двойственности. Прямая и двойственная задачи линейного программирования. Основные теоремы двойственности. Применение двойственного симплексного метода.
- •53. Основные понятия теории графов. Степень вершины графа. Ориентированные графы, связные графы и компоненты связности. Понятие взвешенного графа. Способы задания графа.
37. Приближенное число. Абсолютная и относительная погрешности. Виды, основные источники, способы устранения погрешностей.
Часто при измерении вместо числа А приходится использовать другое число В. Число А будем называть точным значением, а число В приближенным значением измеряемой величины.
Число В называют приближенным числу A, если В незначительно отличается от A и заменяет его в вычислениях. Ошибкой называют разность R=А-В (в некоторых учебниках R=В-A). Имеем A=В+R, т.е. для получения точного значения к приближенному числу нужно добавить ошибку. Ошибка измерений может быть положительной и отрицательной. Если R>0, то В приближается к А по недостатку. Если R<0, то В приближается к А по избытку. Точное число – это приближенное число с ошибкой равной 0. Обычно точное значение А неизвестно, значит не известно ни значение ошибки R, ни ее знак. В этом случае используется понятие абсолютной погрешности числа.
Абсолютной погрешностью замены величины А числом В называется любое число Д, удовлетворяющее условию: Д>=R. Очевидно, что, если известна некоторая абсолютная погрешность замены А на В, то любое большее число абсолютной погрешности также можно считать абсолютной погрешностью этой замены. Обычно стараются найти абсолютно меньшие погрешности.
Из
определения: А-В<=Д
/ А-В<=Д
/ А<=Д+В
В-Д<=А<=В+Д
А=В
Д
\ -А+В<=Д \ А>= В-Д
Иногда
выполняя различные измерения, например,
определяя высоту окна и высоту
многоэтажного дома, можно иметь одно и
тоже значение абсолютной погрешности.
Для выявления разницы используют понятие
относительной погрешности. Относительной
погрешностью замены
величины А на В называют любое число Е,
Е>=|R/A|.
На практике обычно А
В.
Иногда можно считать: E>=|R/B|.
Из определения E>=|(B-A)/A|: можно получить А=В(1 Е).
Между относительной и абсолютной погрешностями имеется связь:
Погрешности бывают двух видов: устранимые и неустранимые. Устранимые погрешности – это погрешности, величину которой можно уменьшить.
Основные источники погрешностей: 1) погрешность задачи (связана с заменой реальной задачи математической моделью); 2) погрешность методов (возникает при замене в задаче, которую в точной постановке решить невозможно, на близкую по результата приближенную задачу); 3) начальная погрешность(применение приближенных вычислений, например g=9,8); 4) погрешность округления (связана с системой счисления. В компьютерах возникает из-за ограниченной разрядной сетки для чисел); 5) погрешность действий (арифметические действия над приближенными числами); 6) остаточная погрешность (связана с наличием бесконечных процессов и предельными переходами).
Неустранимые погрешности: погрешность задачи, начальная погрешность, погрешность действий. Остальные погрешности – устранимые. Способы устранения погрешностей зависят от вида погрешностей. Устранимые погрешности регулируются путем изменения порядка действий от исходных данных, заменой искомой задачи на более точную, выбора большего количества цифр в записи чисел, увеличением количества рассматриваемых шагов от бесконечных процессов.
41. Вычисление определенных интегралов методом трапеций и методом Симпсона. Метод двойного пересчета.
В
о
мног. случ. выч. опр-го инт-ла: где f(x)
для опред-ти неоп-на на [a,b]
затрудн. Прибл. вычисл. м/но пров. исп-я
инт-ые суммы, разбив. отрез. интег-ния
для упрощ. оценки погрешн. на рав. части.
I
.
Ф-ла трапеций.
Раз-ем отрез. интег-ия на n-рав.
частей и заменим на каждом Δxi
кривую y=f(x)
хордой. Замен. в вычисл. площадь кривол.
трапец. площ-ю прямоуг.:
Суммируя,
получ.
Ф-ла трапеций.
М/но
показ. что погрешность:
II.
М-д Симпсона.
Разобъем отрез. интег-ия на 2n
равных частей точками: a=x0<=x1<=…<=x2n=b.
На каж. из отрезков [x2i,x2i+2]
где i=0,n-1
ч/з точки: (x2i,y2i),(x2i+1,y2i+1),(x2i+2,y2i+2)
провед. квадратич. параболу с осью ||-ой
оси Oy.
Б/м считать, что:
Отметим,
что
…
Ф-ла
Симпсона (квадратич. ф-ла)
Погреш.
ф-лы м.б. оценена след-щим нерав-ом:
I
II.
На практике чаще задают точность чем
n,
чтобы не вычисл. n
по ε исп-ют м-д 2-го пересчет: Выбир.
нек-рое знач. N
и вычисляют инт-л при этом N,
J1,
з/м N
удваивают 2N
и вновь инт-л – J2,
если |J2-J1|<=ε
за рез/т берут J2,
иначе вновь удваивают (4N)
и J3
и т.д.
