Основы компьютерных наук: 3 важные области для разработчиков

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

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

• Вычислите временную и пространственную сложность алгоритма
• Максимально используйте доступные структуры данных
• Докажите правильность алгоритма

Вам также может понадобиться решить, какой язык программирования лучше всего подходит для ваших задач. Для этого вы должны понимать:

• Когда язык программирования должен быть высокоуровневым или низкоуровневым
• Когда предпочесть язык программирования с компилятором или интерпретатором

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

1. Основы аппаратного и программного обеспечения

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

Что нужно узнать в первую очередь об оборудовании

Некоторые темы компьютерного оборудования, о которых следует знать, включают:

Аппаратные компоненты

• Центральный процессор (ЦП) : обрабатывает информацию на компьютере. Это физический объект, который берет данные из основной памяти, обрабатывает их и возвращает обновленные данные в основную память.
• Блок управления (CU) : Подблок ЦП, который управляет потоком данных из основной памяти и в нее.
• Арифметико-логическое устройство (АЛУ) : еще одно подразделение ЦП, отвечающее за обработку арифметических и логических операций.
• Единицы ввода : возьмите данные из мира или устройства ввода и преобразуйте их в потоки байтов. Примеры: клавиатура, мышь, микрофон, камера и USB.
• Единицы вывода : берут обработанные данные из ЦП и отображают их в понятном для человека виде. Примеры: экраны мониторов, принтеры и наушники.
• Единицы хранения : где данные хранятся после извлечения и обработки. Единица хранения, или память, представляет собой пространство физической памяти.
• Память : включает в себя как основную память или оперативную память (ОЗУ), которые представляют собой физические области памяти в компьютере, так и вторичное хранилище, такое как жесткие диски, компакт-диски, флэш-накопители USB и т. д.

Аппаратные архитектуры

• Архитектура фон Неймана : разработка Джона фон Неймана 1945 года, которая до сих пор используется в большинстве компьютеров, производимых сегодня, в которых программные инструкции и данные используют одну и ту же память и пути.
• Гарвардская архитектура : компьютерная архитектура, в которой пути хранения и передачи сигналов для данных и инструкций разделены, в отличие от архитектуры фон Неймана.
• Архитектура набора инструкций (ISA) : абстрактная модель компьютера. Реализация — это устройство, которое выполняет инструкции, заданные ISA. Как правило, ISA определяет следующее для семейства реализаций:
  • Инструкции
  • Типы данных
  • Регистры
  • Аппаратная поддержка управления основной памятью
  • Основные характеристики
  • Модель ввода/вывода

Что нужно узнать в первую очередь о программном обеспечении

Некоторые темы программного обеспечения, о которых следует знать, включают:

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

• Машинный язык : единственный язык, который может обрабатывать компьютер, — это поток единиц и нулей, называемый двоичным. Машинный язык считается языком программирования низкого уровня.
• Язык ассемблера : низкоуровневый язык программирования, читаемый людьми, который переводит двоичные файлы в инструкции по ассемблеру, которые должны быть переведены на машинный язык для компьютера. Языки ассемблера являются связующим звеном между машинным языком и языками программирования высокого уровня.
• Языки высокого уровня : также известны как языки программирования (например, Python, C++, Java). Эти языки позволяют создавать мощные, сложные, удобочитаемые программы без большого количества низкоуровневых инструкций (например, инструкций на языке ассемблера).

Ключевые типы программного обеспечения

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

2. Структуры данных и их свойства

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

Что нужно узнать в первую очередь о структурах данных

Некоторые темы структуры данных, о которых нужно знать, включают:

• Массив : набор элементов одного и того же типа переменных, которые последовательно хранятся в памяти. Каждый элемент массива индексируется, начиная с 0, и каждый элемент называется элементом. Массивы лучше всего подходят для извлечения данных за постоянное время (с использованием индекса), но не обеспечивают быстрой вставки или удаления данных.
• Связанный список : линейная последовательность узлов, которые связаны друг с другом. В односвязном списке каждый узел содержит значение и указатель на следующий узел в списке. В отличие от массивов односвязные списки не имеют индексов, поэтому вы должны начать с первого узла и проходить через каждый узел, пока не дойдете до n-го узла.
• Списки ссылок обеспечивают более быстрое удаление и вставку, но более медленное извлечение данных по сравнению с массивами.
• Дерево : нелинейная структура данных, часто используемая для представления иерархических данных. Например, иерархическая структура компании использует для организации дерево.
• Стек : линейная структура в порядке «последний пришел — первый ушел» (LIFO). Это может помочь представить стопку тарелок. Последняя тарелка, которую вы поставите на вершину стопки, будет первой, которую вы вытащите. Стеки так работают.
• Очередь : аналогична стеку в том смысле, что обе они представляют собой линейные структуры данных с динамическим размером. Однако очереди представляют собой структуры данных по принципу «первым пришел — первым обслужен» (FIFO). Представьте, что вы стоите в очереди на американские горки. Первые люди, выстроившиеся в очередь, могут выйти из очереди на аттракцион первыми.
• График : Абстрактное обозначение, представляющее связь между всеми парами объектов.
• Хеш-таблица : зависит от процесса хеширования или присвоения объекта уникальному индексу, известному как ключ. Каждый объект идентифицируется с помощью пары ключ-значение, а коллекция объектов называется словарем. Хеш-таблица реализуется путем хранения элементов в массиве и их идентификации с помощью ключа. Хэш-функция принимает ключ и возвращает индекс, для которого хранится значение.
• Heap : расширенная древовидная структура данных, используемая в основном для сортировки и реализации приоритетных очередей.

3. Алгоритмы: сложность и дизайн

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

Что нужно узнать в первую очередь об алгоритмах

Некоторые темы алгоритмов, о которых следует знать, включают:

Временная сложность и правильность

• Асимптотическая временная сложность : анализ, который вычисляет точное время выполнения алгоритма и не зависит от платформы и ввода. Такой анализ временной сложности говорит нам, как программа работает по мере роста размера входных данных независимо от базовой машины. Мы используем Big O для представления верхней границы, Big Omega (\ОмегаОм) для представления нижней границы, а Big Theta (\ТетаΘ) для представления жесткой границы времени работы. Асимптотическая временная сложность обычно предпочтительнее анализа, основанного на конкретных входных данных и конкретной платформе.
• Временная сложность рекурсивных алгоритмов. Вычисление асимптотической временной сложности итерационных алгоритмов является простым. Для вычисления временной сложности рекурсивных алгоритмов мы можем использовать либо метод подстановки, либо теорему Мастера, либо дерево рекурсии. Среди них метод подстановки считается наиболее строгим, поскольку он основан на математической индукции.
• Асимптотическая пространственная сложность : анализ того, сколько памяти занимает алгоритм. Те же асимптотические обозначения (большой O, большая омега и большая тета) также используются для представления пространственной сложности алгоритма.
• Методы доказательства правильности : подходы, используемые для доказательства того, что данный алгоритм является правильным и всегда будет давать ожидаемый результат. Одним из примеров может быть доказательство того, что алгоритм сортировки всегда будет сортировать список, независимо от данных в списке. Самый распространенный и широко используемый метод корректности называется » инвариант цикла «, который основан на математической индукции.

Методы разработки алгоритмов

• Грубая сила : метод, который требует использования всех возможностей, чтобы найти решение проблемы. Часто этот алгоритм первым приходит на ум. Это также наименее эффективно и, следовательно, в большинстве случаев не дает нам желаемого решения за приемлемое время. Например, чтобы взломать разумный пароль с помощью грубой силы, может потребоваться несколько сотен лет.
• Разделяй и властвуй : шаблон, который разбивает проблему на более мелкие подзадачи, которые затем решаются с помощью рекурсии и в конечном итоге снова собираются. Рекурсия — это практика, при которой функция прямо или косвенно вызывает сама себя. Примеры алгоритмов «разделяй и властвуй» включают сортировку слиянием и быструю сортировку.
• Динамическое программирование : шаблон, похожий на принцип «разделяй и властвуй». Разбиваем большую проблему на маленькие подзадачи и объединяем их решения. Однако ключевое отличие состоит в том, что подзадача может перекрываться с другими подзадачами. Таким образом, для сокращения времени выполнения мы сохраняем результаты каждой подзадачи в памяти, что называется мемоизацией. Мемоизация гарантирует, что каждая подзадача выполняется только один раз. Всякий раз, когда подзадача требуется снова, ее результат немедленно извлекается из памяти.
• Жадный подход: подход, при котором мы пытаемся решить каждую подзадачу, используя наилучшее доступное локальное решение, называемое локальным оптимумом. Жадный алгоритм дает оптимальные результаты только тогда, когда локальные оптимумы приводят нас к глобальным оптимумам, наилучшему глобальному решению. Примерами жадных алгоритмов являются алгоритм Прима, который находит минимальное остовное дерево, и алгоритм Дейкстры, который находит кратчайший путь в графе.
• Другие методы проектирования : Алгоритмы аппроксимации находят решение, близкое к оптимальному, когда поиск оптимального решения либо требует много времени, либо невозможен. Рандомизированные алгоритмы и линейное программирование являются другими часто используемыми методами разработки алгоритмов.

Ключевые категории алгоритма

• Сортировка и поиск : Алгоритмы, которые упорядочивают элементы списка или проверяют или извлекают элемент из любой структуры данных, в которой он хранится. Примеры сортировки включают сортировку слиянием, быструю сортировку, пузырьковую сортировку, сортировку выбором и сортировку вставками. Примеры поиска включают линейный поиск и бинарный поиск.
• График : Алгоритмы, которые используются для решения задач представления графов в виде сетей (например, полеты авиакомпаний, подключение к Интернету, подключение к социальным сетям). Как было определено ранее, граф — это абстрактная запись, представляющая связь между всеми парами объектов.
• Кратчайший путь : алгоритмы, которые используются для поиска кратчайшего пути в графе, что является фундаментальной проблемой, используемой в различных областях компьютерных наук. Существует множество алгоритмов сортировки, каждый из которых имеет свои преимущества и недостатки. Алгоритм выбирается исходя из типа данных, их размера и пользовательского приложения.