Алгоритмы и структуры данных

Рис.1

 

 

Содержание

1 Этимология и значение слова

1.1 Эквиваленты в английском языке

1.2 Полисемия

1.3 Полисемия в русском языке

2 История

2.1Отечественная история информатики

2.2Основные достижения

3 Структура информатики

3.1 Теоретическая информатика

3.1.1 Теория алгоритмов

3.1.2 Информация и теория кодирования

3.1.3 Алгоритмы и структуры данных

3.1.4 Теория языков программирования

3.1.5 Формальные методы

3.2 Прикладная информатика

3.2.1 Искусственный интеллект

3.2.2 Архитектура компьютера и компьютерная инженерия

3.2.3 Анализ производительности компьютера

3.2.4 Компьютерная графика и визуализация

3.2.5 Компьютерная безопасность и криптография

3.2.6 Компьютерное моделирование и численные методы

3.2.7 Компьютерные сети

3.2.8 Параллельные и распределённые системы

3.2.9 Базы данных

3.2.10 Информатика в здравоохранении

3.2.11 Информационная наука

3.2.12 Программная инженерия

3.3 Естественная информатика

4 Великие идеи информатики

5 В научном сообществе

5.1 Конференции

5.2 Журналы

6 В образовании

6.1 Образование в США

6.2 Образование в России

7 Основные термины

8 См. также

9 Примечания

10 Литература

11 Ссылки

Этимология и значение слова

Термин «информатика» появился в 1959 году в научном журнале Communications of the ACM^[2], в котором Луи Фейн (Louis Fein) ратовал за создание Высшей школы в области информатики аналогичной Гарвардской бизнес-школе, созданной в 1921 году^{[3][ уточнить ]}. Обосновывая такое название школы, Луи Фейн ссылался на науку управления, которая так же как и информатика имеет прикладной и междисциплинарный характер, при этом имеет признаки, характерные для научной дисциплины. Усилия Луи Фейна, численного аналитика Джордж Форсайта и других увенчались успехом: университеты пошли на создание программ, связанных с информатикой, начиная с Университета Пердью в 1962^[4].

Несмотря на своё название (от англ. Computer Science — компьютерная наука), большая часть научных направлений, связанных с информатикой, не включает изучение самих компьютеров. Вследствие этого были предложены несколько альтернативных названий^[5]. Некоторые факультеты крупных университетов предпочитают термин вычислительная наука (computing science), чтобы подчеркнуть разницу между терминами. Датский учёный Питер Наур предложил термин даталогия (datalogy)^[6], чтобы отразить тот факт, что научная дисциплина оперирует данными и занимается обработкой данных, хотя и не обязательно с применением компьютеров. Первым научным учреждением, включившим в название этот термин, был Департамент Даталогии (Datalogy) в Университете Копенгагена, основанного в 1969 году, где работал Питер Наур, ставший первым профессором в даталогии (datalogy). Этот термин используется в основном в скандинавских странах. В Европе же часто используются термины, производные от сокращённого перевода фраз «автоматическая информация» (automatic information) (к примеру informazione automatica по-итальянски) и «информатика и математика» (information and mathematics), например, informatique (Франция), Informatik (Германия), informatica (Италия, Нидерланды), informática (Испания, Португалия), informatika (в славянских языках) или pliroforiki (πληροφορική, что означает информатика) — в Греции. Подобные слова также были приняты в Великобритании, например, Школа информатики в Университете Эдинбурга^[7].

В русском, английском, французском и немецком языках в 1960-х годах была тенденция к замене термина «документация» терминами, имеющими в своей основе слово «информация»^[8]. Термин нем. Informatik ввёл немецкий специалист Карл Штейнбух в статье Informatik: Automatische Informationsverarbeitung (Информатика: Автоматическая обработка информации) 1957 года^[9]. Французский термин «informatique» введён в 1962 году Филиппом Дрейфусом, который также предложил перевод на ряд других европейских языков.

В русском языке производной от термина «документация» стала документалистика и получили распространение термины научная и научно-техническая информация. Термины «информология» и «информатика» предложены в 1962 году членом-корреспондентом АН СССР Александром Харкевичем. Основы информатики как науки были изложены в книге «Основы научной информации» 1965 года, которая была переиздана в 1968 году уже под названием «Основы информатики»^[10].

Во Франции термин официально вошёл в употребление в 1966 году^[11]. В немецком языке термин нем. Informatik имел вначале двойственное значение. Так, в ФРГ^[8] и Великобритании^[1] он был в значении «computer science», то есть означал всё, что связано с применением ЭВМ, а в ГДР, как и в основном по Европе, обозначал науку по французской и русской модели.

Эквиваленты в английском языке

Считается, что под терминами «informatics» в европейских странах и «информатика» в русском языке понимается направление, именуемое в английском языке «computer science». К другому направлению, посвящённому изучению структуры и общих свойств объективной (научной) информации, иногда называемому документалистикой (документальной информатикой) или автоматическим анализом документов^[1], близок термин «information science».

Принято считать, что в английский язык термин «informatics» независимо от остальных ввёл Уолтер Ф. Бауэр, основатель «Informatics Inc.». В США в настоящее время термин «informatics» (англ.) связан с прикладными вычислениями или обработкой данных в контексте другой области^[12], например в биоинформатике («bioinformatics») и геоинформатике («geoinformatics»).

Во многих словарях informatics и computer science приравниваются к информатике. В тезаурусе ЮНЕСКО «Информатика — Informatics» даётся как синоним к переводу «Computer science — Компьютерные науки»^[13].

Полисемия

Ряд учёных (специалистов в области информатики) утверждал, что в информатике существуют три отдельные парадигмы. Питер Вегнер^[en] утверждал, что эти три парадигмы — наука, технологии и математика^[14]. Рабочая группа Питера Деннинга^[en]утверждала, что это теория, абстракция (моделирование) и дизайн^[15]. Амнон Х. Эден описывал эти парадигмы как «рационалистическую парадигму» (где информатика — это раздел математики, математика доминирует в теоретической информатике и в основном использует логический вывод), «технократическую парадигму» (используемую в инженерных подходах, наиболее важных в программной инженерии) и «научную парадигму» (где информатика — это ветвь естественных (эмпирических) наук, но информатика отличается тем, что в ней эксперименты проводятся над искусственными объектами (программами и компьютерами)^[16].

Полисемия в русском языке

В разные периоды развития информатики в СССР и России в понятие «информатика» вкладывался различный смысл. Информатика — это^[17]:

1. Теория научно-информационной деятельности. В рамках библиотечного дела под термином «научно-информационная деятельность» понимается «практическая работа по сбору, аналитико-синтетической переработке, хранению, поиску и предоставлению учёным и специалистам закрепленной в документах научной информации»^[18]. В 1952 г. в Москве был создан Институт научной информации Академии наук (переименованный позднее в ВИНИТИ). Цели его создания были более широкими, чем выполнение «научно-информационной деятельности» и А. А. Харкевич (директор Института проблем передачи информации АН СССР) предложил в письме А. И. Михайлову (директору ВИНИТИ) новое название: "«информология» или «информатика» («информация» плюс «автоматика)» ^[19]. Третье издание «Большой советской энциклопедии» (1970-е гг.) фиксирует значение информатики как дисциплины, изучающей «структуру и общие свойства научной информации, а также закономерности её создания, преобразования, передачи и использования в различных сферах человеческой деятельности»^[19].

2. Наука о вычислительных машинах и их применении (вычислительная техника и программирование). В 1976 г. профессорá Мюнхенского технического университета Ф. Л. Бауэр и Г. Гооз написали книгу «Информатика. Вводный курс», переведённую в том же году известным советским учёным Андреем Петровичем Ершовым на русский язык. Ершов перевёл «Informatik» словом «информатика» и определил как «науку, занимающуюся разработкой теории программирования и применения ЭВМ»^[19]. Термин «Informatik» Ф. Л. Бауэр и Г. Гооз объясняют как «немецкое название для computer science — области знания, которая сложилась в самостоятельную научную дисциплину в шестидесятые годы, прежде всего в США, а также в Великобритании. … В английском языке, по-видимому, останется „computer science“ (вычислительная наука), причем этот термин имеет уклон в область теории»^[20].

3. Фундаментальная наука об информационных процессах в природе, обществе и технических системах. В начале 1990-х гг. К. К. Колин (заместитель директора Института проблем информатики АН СССР) синтезировал толкования информатики, данные академиками А. П. Ершовым и Б. Н. Наумовым, а также проф. Ю. И. Шемакиным следующим образом: информатика — это наука «о свойствах, законах, методах и средствах формирования, преобразования и распространения информации в природе и обществе, в том числе при помощи технических систем». Предметная область информатики, по Колину, включает такие разделы: (1) теоретическая информатика; (2) техническая информатика; (3) социальная информатика, (4) биологическая информатика и (5) физическая информатика^[21].

Полагают^[17], что одновременное существование всех трёх значений у слова «информатика» затрудняет и мешает развитию данного научного направления.

История

Чарльзу Бэббиджуприписывают изобретение первого механического компьютера.

Аде Лавлейсприписывают написание первого алгоритма, предназначенного для обработки на компьютере.

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

Блез Паскаль спроектировал и собрал первый рабочий механический калькулятор, калькулятор Паскаля, в 1642^[22].

В 1673 году Готфрид Лейбниц продемонстрировал цифровой механический калькулятор, названный «Stepped Reckoner»^[23]. Его можно считать первым учёным в области компьютерных наук и специалистом в области теории информации, поскольку среди прочего, он ещё описал двоичную (бинарную) систему чисел.

В 1820 году Томас де Кольмар^[en] запустил промышленный выпуск механического калькулятора после того, как он создал свой упрощённый арифмометр, который был первой счётной машиной достаточно прочной и надёжной для ежедневного использования служащими. Чарльз Бэббидж начал проектирование первого автоматического механического калькулятора, его разностной машины, в 1822, что в конечном счёте подало ему идею первого программируемого механического калькулятора, его аналитической машины^{[en] [24]}.

Он начал работу над этой машиной в 1834 году и менее чем за два года были сформулированы многие из основных черт современного компьютера. Важнейшим шагом стало принятие перфокарт, произведенных на Жаккардовском ткацком станке ^[25], что открывает бесконечные просторы для программирования ^[26]. В 1843 году, во время перевода французской статьи на аналитической машине, Ада Лавлейс написала в одной из её многочисленных записок алгоритм для вычисления чисел Бернулли, который считается первой компьютерной программой ^[27].

Около 1885 года Герман Холлерит изобрёл табулятор, который использовал перфокарты для обработки статистической информации; в конечном итоге его компания стала частью IBM. В 1937 году, спустя сто лет после несбыточной мечты Бэббиджа, Говард Эйкен, убедил руководство IBM, производившей все виды оборудования для перфорированных карт^[28] и вовлечённой в бизнес по созданию калькуляторов разработать свой гигантский программируемый калькулятор, ASCC/Harvard Mark I^[en], основанный на аналитической машине Бэббиджа, которая, в свою очередь, использовала перфокарты и центральный вычислитель (central computing unit) Когда машина была закончена, некоторые называли её «мечта Бэббиджа сбывается»^[29].

В 1940-х, с появлением новых и более мощных вычислительных машин, термин компьютер стал обозначать эти машины, а не людей, занимающихся вычислениями (теперь слово «computer» в этом значении употребялется редко)^[30]. Когда стало ясно, что компьютеры можно использовать не только для математических расчётов, область исследований информатики расширилась с тем, чтобы изучать вычисления в целом. Информатика получила статус самостоятельной научной дисциплины в 1950-х и начале 1960-х годов^{[31] [32]}. Первая в мире степень по информатике, Диплом Кэмбриджа по информатике, была присвоена в компьютерной лаборатории Кембриджского университета в 1953 году. Первая подобная учебная программа в США появилась в Университете Пердью в 1962 году^[33]. С распространением компьютеров возникло много новых самодостаточных научных направлений, основанных на вычислениях с помощью компьютеров.

Мало кто изначально мог предположить, что сами компьютеры станут предметом научных исследований, но в конце 1950-х годов это мнение распространилось среди большинства учёных ^[34]. Ныне известный бренд IBM в то время был одним из участников революции в информатике. IBM (сокращение от International Business Machines) выпустила компьютеры IBM 704^[35] и позже IBM 709^[36], которые уже широко использовались, в то время как такие устройства ещё только исследовались. «Тем не менее, работа с IBM (компьютером) была полна разочарований… если ты допускаешь ошибку в одной букве в одной инструкции, программа терпит крах и тебе приходится начинать весь процесс заново» ^[34]. В конце 1950-х годов информатика как дисциплина ещё только становилась, и такие проблемы были обычным явлением.

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

Отечественная история информатики

В школах СССР учебная дисциплина «Информатика» появилась в 1985 году одновременно с первым учебником А. П. Ершова «Основы информатики и вычислительной техники»^[37].

4 декабря отмечается День российской информатики, так как в этот день в 1948 году Государственный комитет Совета министров СССР по внедрению передовой техники в народное хозяйство зарегистрировал^{[неоднозначная ссылка]} за номером 10 475изобретение И. С. Брука и Б. И. Рамеева — цифровую электронную вычислительную машину^[38].

Основные достижения

Немецкие военные использовалишифровальную машину «Энигма»(как на изображении) во времяВторой Мировой войны для обмена секретными сообщениями. Масштабные расшифровки трафика Энигмы в Блетчли-Парк были важным фактором, который внёс вклад в победу Союза во Второй Мировой войне^[39].

Несмотря на короткую историю в качестве официальной научной дисциплины, информатика внесла фундаментальный вклад в науку и общество. По сути, информатика, наряду с электроникой, является одной из основополагающих наук текущей эпохи человеческой истории, называемой информационной эпохой. При этом информатика является предводителем информационной революции и третьим крупным шагом в развитии технологий, после промышленной революции (1750—1850 н. э.) и неолитической революции (8000-5000 до н. э.).

Вклад информатики:

· Начало «цифровой революции», включающей информационную эпоху и интернет.

· Дано формальное определение вычислений и вычислимости, и доказательство того, что существуют алгоритмически неразрешимые задачи^[40].

· Введено понятие языка программирования, то есть средства для точного выражения методологической информации на различных уровнях абстракции^[41].

· В криптографии расшифровка кода «Энигмы» стала важным фактором победы союзных войск во Второй мировой войне^[42].

· Вычислительные методы обеспечили возможность практической оценки процессов и ситуаций большой сложности, а также возможность проведения экспериментов исключительно за счет программного обеспечения. Появилась возможность углубленного изучения разума и картирования генома человека, благодаря проекту «Геном человека». Проекты распределенных вычислений, такие как Folding@Home, исследуют сворачивание молекул белка.

· Алгоритмическая торговля повысила эффективность и ликвидность финансовых рынков с помощью искусственного интеллекта, машинного обучения и других статистических и численных методов на больших диапазонах данных ^[43]. Частое использование алгоритмической торговли может усугубить волатильность^[44].

· Компьютерная графика и CGI повсеместно используются в современных развлечениях, особенно в области телевидения, кино, рекламы, анимации и видео-игр. Даже фильмы, в которых нет (явного) использования CGI, как правило, сняты на цифровые камеры и впоследствии обработаны или отредактированы в программах обработки видео.

· Моделирование различных процессов, например в гидродинамике, физике, электрике, электронных системах и цепях, а также для моделирования общества и социальных ситуаций (в частности, военных игр), учитывая среду обитания и др. Современные компьютеры позволяют оптимизировать, например, такие конструкции, как проект целого самолета. Известным программным обеспечением является симулятор электронных схем SPICE, а также программное обеспечение для физической реализации новых (или модифицированных) конструкций, включающее разработку интегральных схем.

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

Структура информатики

Информатика делится на ряд разделов. Как дисциплина, информатика охватывает широкий круг тем от теоретических исследований алгоритмов и пределов вычислений до практической реализации вычислительных систем в области аппаратного и программного обеспечения^[45][46]. Комитет CSAB^[en], ранее называемый «Советом по аккредитации вычислительных наук», включающий представителей Ассоциации вычислительной техники (ACM) и Компьютерного общества IEEE^[en] (IEEE-CS)^[47] — определил четыре области, важнейшие для дисциплины информатика: теория вычислений, алгоритмы и структуры данных, методология программирования и языков, компьютерные элементы и архитектура. В дополнение к этим четырём направлениям, комитет CSAB определяет следующие важные области информатики: разработка программного обеспечения, искусственный интеллект, компьютерные сети и телекоммуникации, системы управления базами данных, параллельные вычисления, распределённые вычисления, взаимодействия между человеком и компьютером, компьютерная графика, операционные системы, числовые и символьные вычисления^[45].

Теоретическая информатика

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

Теория алгоритмов

По словам Питера Деннинга^[en], к фундаментальным вопросам информатики относится следующий вопрос: «Что может быть эффективно автоматизировано?»^[31] Изучение теории алгоритмов сфокусировано на поиске ответов на фундаментальные вопросы о том, что можно вычислить и какое количество ресурсов необходимо для этих вычислений. Для ответа на первый вопрос в теории вычислимости рассматриваются вычислительные задачи, решаемые на различных теоретических моделях вычислений. Второй вопрос посвящён теории вычислительной сложности; в этой теории анализируются затраты времени и памяти различных алгоритмов при решении множества вычислительных задач.

Знаменитая задача «P=NP?», одна из Задач тысячелетия^[48], является нерешённой задачей в теории алгоритмов.

		P = NP?	GNITIRW-TERCES
Теория автоматов	Теория вычислимости	Вычислительная сложность	Криптография	Квантовая теория вычислений

Информация и теория кодирования

Теория информации связана с количественной оценкой информации. Это направление получило развитие благодаря трудам Клода Э. Шеннона, который нашёл фундаментальные ограничения на обработку сигнала в таких операциях, как сжатие данных, надёжное сохранение и передача данных^[49].

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

Алгоритмы и структуры данных

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

Анализ алгоритмов	Алгоритмы	Структуры данных	Комбинаторная оптимизация	Вычислительная геометрия