- •Билет 1. Концепция языка Си, его достоинства и недостатки
- •Билет 2. Представление целых чисел в эвм. Основные типы данных в Си и операции над ними. Особенности операций над вещественными числами.
- •Билет 3. Основные управляющие конструкции в Си. Понятие инварианта цикла и его применение.
- •Билет 4. Характеристика алгоритмов, программ, языков программирования и соответствия между ними.
- •Билет 5. Массивы и указатели в языке Си. Их представление, связь между ними.
- •Билет 6. Метод барьера и различные варианты его применения.
- •Билет 7. Процедуры и функции в Си. Формальные и фактические. Входные и выходные параметры, локальные и глобальные переменные.
- •Билет 8. Массивы и указатели в Си, связь между ними. Передача массивов и указателей как параметров процедур.
- •Билет 9. Представление строк и символов в Си. Операции над ними.
- •Билет 10. Понятие эффективности алгоритма, различные способы ее измерения.
- •Билет 11. Понятие рекурсии. Виды и характеристики.
- •Билет 12. Алгоритмы перебора с возвратом. Способы сокращения перебора.
- •Способы сокращения перебора
- •Билет 13. Алгоритмы оптимального поиска. Метод ветвей и границ.
- •Билет 14. Сортировка массивов. Простые методы.
- •Билет 15. Сортировка массивов. Усовершенствованные методы.
- •Билет 16. Алгоритм поиска подстроки в строке.
- •3. Эвристика совпавшего суффикса. Если при сравнении строки и шаблона совпало один или
- •Билет 17. Алгоритм получения случайных чисел. Правильный выбор параметров линейного конгруэнтного генератора.
Билет 4. Характеристика алгоритмов, программ, языков программирования и соответствия между ними.
Алгоритм – это последовательность математических, логических или вместе взятых операций, отличающихся массовостью, направленностью и приводящая к решению всех задач данного класса за конечное число шагов.
- в первую очередь алгоритм должен быть правильным
- также одно из первых требований, которое предъявляется к алгоритму, состоит в том, что описываемый процесс должен быть разбит на последовательность отдельных шагов. Возникающая в результате такого разбиения запись представляет собой упорядоченную совокупность четко разделенных друг от друга предписаний (директив, команд, операторов), образующих прерывную (или, как говорят, дискретную) структуру алгоритма. Только выполнив требования одного предписания, можно приступить к выполнению следующего. Дискретная структура алгоритмической записи может. Например, подчеркиваться сквозной нумерацией отдельных команд алгоритма, хотя это требование не является обязательным. Рассмотренное свойство алгоритмов называют дискретностью.
- Будучи понятным, алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно, т.е. одна и та же команда, будучи понятна разным исполнителям, после исполнения каждым из них должна давать одинаковый результат.
Запись алгоритма должна быть настолько четкой, полной и продуманной в деталях, чтобы у исполнителя не могло возникнуть потребности в принятии решений, не предусмотренных составителем алгоритма. Говоря иначе, алгоритм не должен оставлять места для произвола исполнителя. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды алгоритма исполнителю неясно, какая из команд алгоритма должна выполняться на следующем шаге.
Отмеченное свойства алгоритмов называют определенностью или детерминированностью.
- Обязательное требование к алгоритмам - результативность. Смысл этого требования состоит в том, что при точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определенный результат. Вывод о том, что решения не существует - тоже результат.
- Универсальность. Наиболее распространены алгоритмы, обеспечивающие решение не одной конкретной задачи, а некоторого класса задач данного типа. Это свойство алгоритма называют массовостью. В простейшем случае массовость обеспечивает возможность использования различных исходных данных.
Сначала всегда разрабатывают алгоритм действий, а потом он записывается на одном из языков программирования. В итоге получается текст программы - полное, законченное и детальное описание алгоритма на языке программирования.
Хорошая программа должна обладать определенными свойствами.
Таких свойств достаточно много: корректность, эффективность, удобство эксплуатации, надежность, удобство сопровождения, понятность и еще целый ряд других. Тремя самыми главными из них являются корректность или правильность, эффективность и понятность и модифицируемость.
Прежде всего, программа должна быть правильной, то есть реализующей корректный алгоритм решения исходной задачи.
Большую роль играет и эффективность программ. Однако основной задачей программирования является создание правильных, а неэффективных программ. Эффективная программа не нужна, если она не обеспечивает правильных результатов. Правильную, но не эффективную программу можно оптимизировать и сделать эффективной.
Свойства понятности и модифицируемости программ связаны самым тесным образом: очень трудно изменить программу, которую не понимаешь. В реальной жизни программиста задачи на модификацию уже написанных кем-то ранее программ встречаются едва ли не чаще, чем задачи на разработку программ с нуля. Решение задач на модификацию является также и весьма эффективным способом изучения как языка, так и методов программирования.
Язык программирования - это множество текстов некоторого алфавита, удовлетворяющих правилам синтаксиса и задающих порядок вычислений в соответствии с правилами семантики.
Свойства языков программирования: Надежность языка обеспечивает минимум ошибок при написании программы. Например, благодаря наличию в языке требования, чтобы все переменные были объявлены до использования, ошибки связанные с неправильным написанием имен выявляются при компиляции, т.е. автоматически. Удобочитаемость языка - свойство, которое обеспечивает легкость восприятия программ человеком. Полнота языка обеспечивает описание на языке решения задач определенной предметной области. Гибкость языка обеспечивает легкость выражения на языке необходимых для решения задач действий. Простота обеспечивает легкость понимания семантики языковых конструкций и запоминания синтаксиса. Мобильность языка позволяет обеспечивать независимость его от аппаратных средств. Можно переносить программное обеспечение с машины на машину с относительной легкостью. Если говорить о соответствии между характеристиками алгоритмов, программ и языков программирования, то можно увидеть, что например, из правильности и эффективности алгоритма следует правильность и эффективность программы. Кроме того и программы, и язык программирования должны быть удобочитаемыми.
…