Что я слышу, я забываю,
Что я вижу, я запоминаю,
Что я делаю, я знаю.
Области человеческой деятельности в которых применяются компьютеры:
- банковские операции;
- бронирование билетов;
- организация систем связи;
- нефте- и газодобыча;
- торговля.
Несмотря на постоянный рост производительности вычислительных систем, объемы данных, подлежащих обработке, растут с не меньшей скоростью. Скорость компьютеров ограничена скоростью перемещения электронов по проводам, скоростью распространения света по оптическим кабелям и скоростью коммутации каналов связи компьютеров, участвующих в вычислениях.
Наиболее распространенные классы задач:
- поиск;
- сортировка;
- сравнение с образцом;
- численные алгоритмы;
- алгоритмы на графах;
- алгоритм Флойда;
- алгоритмы параллельной обработки;
- конечные и магазинные автоматы (с магазинной памятью);
- контекстно-свободные грамматики;
- регулярные и контекстно-свободные языки;
- синтаксический разбор и компилирование программ;
- машина Тьюринга;
- тезисы Черча-Тьюринга;
- задача об остановке;
- перебор с возвратом;
- ветвление и предельное значение;
- динамический алгоритм, дающий приближенное решение задачи о рюкзаке или укладке рюкзака;
- аппроксимация порядка роста рекуррентных соотношений;
- рекурсивные алгоритмы;
- приближение последовательности рекуррентных соотношений;
- поиск ближайшей пары точек;
- выпуклая оболочка множества точек;
- генерирование перестановок множества чисел.
Для решения разнообразных задач необходимо освоить "джентльменский набор" базовых алгоритмов:
- алгоритмы сортировки и поиска, на которых основана работа современных СУБД;
- алгоритмы сравнения с образцом, лежащие в основе текстовых редакторов, компиляторов и программ синтаксического анализа текстов;
- анализ графов, применяемый в разработке транспортных и компьютерных сетей связи;
- параллельные алгоритмы;
- вероятностные алгоритмы;
- элементарные численные алгоритмы.
Первай шаг - более строгая формулировка решаемой задачи, отделение существенного от неважного.
Суть теории сложности - разбиение задач на классы по эффективности решающих их алгоритмов.
