30 Días de Diseño - Un Caso de Estudio de Marca

Hay varios aspectos importantes a tener en cuenta cuando se trabaja con clientes: cumplir las expectativas y los plazos, por mencionar sólo algunos. En algún momento de la carrera de cada diseñador vendrá un cliente que tiene una urgencia apremiante con su proyecto. Estos son los proyectos que enseñan el arte de cumplir con los plazos y lo loco que puede llegar a ser.
Normalmente hay dos tipos de proyectos que cada diseñador encontrará durante tu carrera profesional: “Necesito un diseño centrado en el usuario que se corresponda con mi proyecto, sin plazos estrictos. Sólo quiero la mejor solución”. Y ese es el sueño de todo diseñador, pero enfrentémoslo: en realidad las cosas siempre son más desafiantes.
“Quiero una solución innovadora, creativa y fuera de lo común: un buen UX, una interfaz de usuario realmente agradable…y la necesito ayer”.
Entonces, ¿qué sucede cuando te das cuenta de que hay 30 días para crear un logotipo y diseñar los principales elementos de la marca, un sitio web, interfaces de usuario móviles y anuncios o gráficos en las redes sociales?
Después de tener un pequeño ataque de pánico, te das cuenta de que trabajar de manera inteligente es la única manera de hacerlo. Elaborar un plan y pensar las cosas de antemano te ayudará con la productividad, la precisión y la calidad del diseño. Al igual que con cualquier esfuerzo exitoso, el trabajo arduo y las largas horas son algunas de las condiciones obligatorias para hacerlo realidad.
No importa qué, siempre hay estas preguntas insoportables:
  • ¿Vale la pena hacerlo con tales restricciones de tiempo?
  • ¿Las limitaciones de tiempo llevarán a una mala calidad de diseño?
  • ¿Haría un mejor trabajo si tuviera más tiempo?
¡Absolutamente, sí!
Al igual que con cualquier proyecto, siempre hay aspectos positivos, desventajosos y limitaciones que, como diseñadores, debemos encontrar un camino e incluso utilizar a nuestro favor para llegar a soluciones creativas.
Tener una idea clara de las tareas que se deben cumplir para completar con éxito el proyecto es clave, así como también diplomáticamente dejar que el cliente sepa que el breve plazo podría tener un impacto negativo en la calidad del diseño en general. Sin embargo, la presión de una fecha límite aplastante no es una excusa para no dar lo mejor de sí mismo en tu oficio, utilízalo para forzarte a entregar el mejor trabajo posible. Un estudio hecho por la Escuela de Negocios de Harvard sobre el trabajo creativo realizado bajo presión de tiempo concluyó que:
_ “Este estudio sugiere que los gerentes tomen medidas para proteger el tiempo para que los empleados participen en el procesamiento cognitivo creativo, particularmente aquellos empleados cuyo trabajo requiere un alto grado de creatividad. […] Es muy probable que las ideas creativas no ser producido en ausencia total de cualquier presión de tiempo, ya sea autoimpuesto o impuesto externamente “.
Estos hallazgos indican que un gran grado de presión puede funcionar en contra del trabajo creativo, pero al mismo tiempo, el estudio también sugiere que un nivel razonable de presión con respecto al trabajo creativo puede ser útil para ayudar a producir mejores diseños.
Siempre es un desafío hacer todo mientras trabajas como profesional independiente con múltiples proyectos activos, ¡pero es una gran oportunidad para ser diligente con tu agenda y hacer que tu tiempo limitado trabaje para ti! Hacer que el trabajo remoto funcione para ti es simple, pero no fácil. Combina esto con un plan sólido, y tendrás una receta para el éxito.

Día 1-3: Lo primero es lo primero — ¡Planifica!

El primer paso es dividir el proyecto en partes más pequeñas y calcular cuánto tiempo tomará terminar cada etapa del proyecto. Establecer metas aumenta la motivación y el logro. La ciencia del logro de los objetivosrecomienda desglosar tu gran objetivo en pasos de acción claros y definidos. Al hacerlo, obtendrás un gran ventaja en tus esfuerzos para lograrlo.
Con respecto al diseño de marca, una buena práctica es crear varias versiones del diseño para que el cliente tenga diferentes opciones para elegir. Mi preferencia personal es crear tres iteraciones de diseños de logotipos y elementos principales de la marca, como tipografía, paletas de colores, imágenes y conjuntos de iconos. Hacer esto primero te permitirá llevar el concepto y las ideas visuales al próximo paso.
Crear procesos de trabajo y seguirlos.
La creación de procesos de trabajo facilitará el flujo de trabajo y la responsabilidad que conlleva cada proyecto. El siguiente es mi enfoque habitual para un proyecto de diseño típico, ya sea diseño de marca o de interfaz de usuario:

Investigación

Descubre todo sobre el negocio de tu cliente:
  • ¿Cuál es el núcleo de su negocio y cuál es su principal actividad?
  • ¿Quién es su público objetivo y cuáles son sus necesidades?
  • ¿Cuáles son sus objetivos y qué problema debe ser resuelto mediante el diseño?
  • ¿Quién es la competencia y cómo puedes ser mejor?
Un cuestionario o resumen de diseño es una de las maneras más convenientes y eficientes de recopilar la información antes mencionada.

Crear un Mood board

Una de las cosas que puedes usar para crear un mood board es crear el concepto — una parte esencial de cualquier proyecto. Toma una perspectiva más amplia: toma toda tu investigación y ponla en un lienzo grande para que puedas ver todos los elementos que deberían incorporarse en los diseños. Hay varios herramientas gratis que lo ayudan a crear mood boards fácilmente.
Si no te gustan las herramientas en línea, usar Adobe Illustrator funciona bien ya que puede crear, agregar y mover elementos libremente. Piensa en ello como un collage — no te preocupes demasiado por el posicionamiento de los detalles, eres libre de organizar todo a tu gusto. El objetivo principal es ver cómo los colores, las fotos, los íconos, la tipografía, etc. trabajan entre sí visualmente y en la narración de historias.
Representación visual de un mood board
Los mood boards son muy fáciles de hacer y te ayudarán a mostrar tu idea.

Día 3: Crea un concepto de diseño

Crear un concepto es el siguiente paso después de completar tu mood board y es la base de todo tu futuro trabajo. Un concepto se produce como un modelo experimental para probar la viabilidad de las características de diseño.
Un mood board será útil para establecer una dirección visual temprana que corresponda a la audiencia a la que se dirige y los objetivos del negocio. El concepto será la base de tu dirección de UX y, por lo tanto, forma parte de Los 10 Mejores Entregables de UX .
Es necesario apreciar la importancia de este paso porque un concepto sólido ayuda a volver a contar una historia convincente, incluso durante las primeras etapas del proyecto. El enfoque principal debe tener en cuenta los sentimientos y las experiencias que los usuarios encuentran al tratar con los elementos visuales en lugar de los visuales en sí mismos.
Uno de los consultores de marketing más influyentes de la industria y oradores motivadores, Simon Sinek, dio una charla TED brillante sobre este tema.
El mood board puede ayudarte a crear algunos eslóganes cortos o tal vez a establecer estilos de iconos y fotografías en un concepto. Ya que es bueno tener una tipografía que se pueda leer rápidamente independientemente del medio, también es importante considerar la tipografía amigable con la impresión y la web. Este es un elemento clave del gran diseño y también es uno de los principios considerados por prácticas de diseño universales.

Día 4: Diseña los Visuales de Marca

El proceso de creación de marca puede volverse tedioso y lento si se lo detecta siguiendo el enfoque equivocado desde el principio. Comenzar creando iteraciones de logotipo se hace mejor una vez que tienes un concepto aprobado, y los archivos de guía visual están listos. Esto te dará la confianza de que te estás moviendo en la dirección correcta, y te permitirá abordar los desafíos de la marca de una manera inteligente y eficiente en el tiempo.
Es esencial hacer pequeños bocetos de lápiz y papel de tus ideas de diseño primero. Tomará menos tiempo si primero dibujas y luego avanzas a Illustrator, Sketch, etc. para trabajar en tu logotipo. Este paso me ha ayudado a diseñar tres propuestas de logotipo diferentes que están todas en la dirección visual elegida para la marca. Esto tomó algunos días para terminar:
Estudio de caso de marca: ejemplos de logotipo
Puede haber algunos cambios y ajustes adicionales en el diseño del logotipo, pero una vez que el cliente haya decidido el logotipo y aprobado otros elementos como colores, tipografía, iconos y estilo de fotografía, habrás terminado con los elementos de marca básicos.

Día 7-15: Diseño del sitio web

El desarrollo de la marca incluye más que solo el logotipo: cubre casi todos los aspectos del diseño, incluido el sitio web. Comenzar primero con el sitio web puede ser útil, ya que puedes agregar al concepto visual aplicando reglas visuales y viendo cómo funcionan juntas. Esto es particularmente cierto cuando estás creando un sitio web que tiene un objetivo final y elementos similares a la aplicación móvil.

Mapa del sitio

Un mapa del sitio es una lista de páginas de un sitio web al que pueden acceder los rastreadores o los usuarios. Puede ser un documento que se utiliza como una herramienta de planificación para el diseño web o una página que muestra las páginas de un sitio web de forma jerárquica.
Es una gran ayuda si un cliente ya tiene un mapa del sitio porque le da una vista clara de todas las páginas que pertenecen a un sitio web. Si se le adjudica un proyecto donde se necesita un mapa del sitio, tendrá que trabajar con el cliente para armar uno.
Esto podría significar hacerle algunas preguntas a tu cliente:
  • ¿Cuál es el número de páginas en el sitio web?
  • ¿Qué páginas son las más importantes?
  • ¿Hay alguna subpágina?
Esto te dará una idea clara de la estructura del sitio web y ofrecerá una buena idea del alcance del proyecto.

La información primero

Me resulta útil pedirle al cliente por adelantado que me brinde toda la información y el contenido que desea incluir en el sitio. Es una buena práctica hacer que el diseño funcione alrededor del contenido en lugar de crear primero la UI e intentar hacer que el contenido quepa después.
El primer enfoque de copia te ahorra a ti y a los desarrolladores mucho tiempo. Si vas al revés, podrías encontrar problemas. Si bien es útil a veces, el uso de texto ficticio puede afectar negativamente a un proyecto real, especialmente cuando el diseño se basa en gran medida en la tipografía y está diseñado en torno al contenido. Un diseño centrado en la copia no tiene inconvenientes y solo ayuda a realizar trabajos creativos de calidad excepcional.

Diseño de página de inicio

Al seguir todos los pasos anteriores, ya tienes pautas visuales generales, un mapa del sitio y copia. Ahora puede continuar diseñando las páginas para el sitio web.
La página de inicio es lo primero que ven los usuarios cuando visitan un sitio web y, por lo tanto, es la página más importante. Al aplicar el Principio de Pareto se demuestra que la página de inicio posee el 80% de la dirección de diseño (contexto, tipografía, colores, elementos repetibles, etc.) y el resto de las páginas un 20%.
Es una buena idea comenzar tu proceso agrupando y seleccionando secciones para la página de inicio. El contenido completo y la copia generalmente me ayudan a organizar toda la página y ver qué aspectos faltan, así como las secciones que se podrían agregar para maximizar el impacto e impulsar a los usuarios a comprar/usar el producto o servicio.
Representación visual de la página de inicio de un sitio web
Se valiente en tus sugerencias para el cliente. Explica que los plazos implican ciertas limitaciones.
Para enfatizar el servicio o producto, intente usar secciones prominentes de llamada a la acción. Son una excelente manera de publicitar y captar la atención de los usuarios para comprar un producto, suscribirse a un boletín informativo, registrarse, etc. Si la tecnología, el público objetivo y el tipo de negocio del cliente lo permiten, agregar un diseño de movimiento como GIF o animación puede dar lugar a todo el subcontexto del sitio, así como a enfatizar la sección de llamado a la acción. Sin embargo, los diseñadoresdeben tener cuidado de no ir demasiado lejos y crear algo que les lleve mucho tiempo desarrollar.

Día 15-25: Aplicar el diseño universal

El diseño universal, según lo describen sus desarrolladores, “se puede aplicar para evaluar diseños existentes, guiar el proceso de diseño y educar tanto diseñadores como consumidores sobre las características de productos y entornos más utilizables”.
El concepto de diseño universal es una de las soluciones más óptimas para usar cuando se trata de un proyecto de gran alcance: un concepto unificado y una dirección visual enfocada para la marca, el sitio web y las aplicaciones móviles es de gran beneficio cuando se diseñan bajo restricciones de tiempo.
La necesidad de elementos repetitivos puede ser un desafío en sí mismo. Esto sucede cuando encuentras requisitos técnicos. El sitio web receptivo y las plataformas móviles tienen una filosofía y un conjunto de reglas completamente diferentes y, por lo tanto, pueden convertirse en un problema si no se abordan de manera adecuada. Sin embargo, la creación de elementos que se pueden utilizar en múltiples plataformas es uno de los pilares del éxito de cualquier proyecto; en esta circunstancia particular, no habría sido posible cubrir tantas plataformas/dispositivos sin un diseño unificado que establezca claramente la dirección para el desarrollo de la marca
Representación visual de una interfaz de aplicación de iOS
La desventaja de una fecha límite ajustada y el diseño de múltiples plataformas es que es posible que no estés utilizando todo el potencial de cada una de las plataformas para las que estás diseñando. En tales casos, debido a la limitación de tiempo, una solución “a prueba de balas” que sea familiar para la base de usuarios podría ser una idea valiosa.
Por ejemplo: vuelve a aplicar una idea en varias páginas y remodela para cada dispositivo. Los patrones son similares en esencia, lo cual está a tu favor. Podría ser en la forma en que muestra información esencial o invita a los usuarios a comprar un producto. En este caso, incluso una barra de búsqueda podría ser similar si no es la misma.

Diagrama de flujo

El diseño del sitio web está hecho y tú tienes una visión más clara del UX para las aplicaciones. Una de las formas en que puedes hacer que el proceso de creación de UX sea más fácil y claro es crear un diagrama de flujo de usuario.
Representación visual de un diagrama de flujo detallado
El diagrama de flujo explica las conexiones entre las páginas y muestra cómo los usuarios interactuarán con la aplicación.
Hay varios métodos y herramientas que puedes usar para crear diagramas de flujo — la práctica habitual es hacer diagramas gráficos con títulos cortos y, si es necesario, texto explicativo. Usar Sketch o Illustrator para esto es mi preferencia, pero cualquier herramienta que te permita crear y mover elementos está bien para esta tarea.
Will Little ha dado una gran interpretación de esto:
“Aquí es donde los ingenieros y creativos deben trabajar en estrecha colaboración para decidir qué tipo de herramientas de software pueden soportar mejor las interfaces y el comportamiento de clic/deslizamiento, hasta la última pestaña, información sobre herramientas, lightbox, icono , etc.”.

Hazlo alto al hacerlo bajo

Descubrir el propósito principal de la aplicación ayudará a definir el UX. Eso podría ayudar a un usuario a comprar un producto, o quizás ayudarlo a usar un producto, la experiencia del usuario debe adaptarse a eso. Los wireframes de baja fidelidad creados en papel y luego llevados a una mayor fidelidad en Sketch o Photoshop pueden facilitar el proceso considerablemente.
Wireframes de alta fidelidad para una aplicación de Android
Cada proyecto es diferente, y en ocasiones será necesario crear wireframes de alta fidelidad.
En este caso, los wireframes de baja fidelidad eran suficientes ya que la aplicación es simple y solo se necesita seguir los detalles visuales del sitio web.
Si es posible, organiza una pequeña prueba para tu UX. Necesitarás un grupo de prueba de futuros usuarios para ver si los wireframes y el flujo de UX tienen sentido. Después de la prueba, contarás con información valiosa y puedes continuar con el siguiente paso (crear una interfaz de usuario).

Diseño unificado

Después de realizar algunos ajustes en el UX, tienes todo lo que necesitas para crear una interfaz de usuario lógica y bien definida, lo que te permite ajustarla a los requisitos visuales de las plataformas iOS y Android. Dado que iOS tiene algunas pautas de diseño muy específicas que pueden evitar que ingreses en la App Store de Apple, debes conocer esas reglas y verificar cuidadosamente cómo se está implementando tu diseño durante la etapa de desarrollo.
Interfaces de usuario para una aplicación de Android
Puedes crear un diseño unificado para ambas plataformas, iOS y Android, y al mismo tiempo utilizar sus mayores fortalezas siguiendo las pautas y reglas al diseñar la interfaz de usuario.

Día 25-30: Crear anuncios en sincronización con la marca

En este punto, debes haber diseñado un logotipo, elementos de marca, un sitio web y aplicaciones móviles. Aunque lo diseñaste todo en menos de 25 días, es demasiado pronto para celebrar, ya que todavía hay un paso más a considerar: crear anuncios para redes sociales y piezas impresas. Aquí es donde el concepto que creó al principio será de gran ayuda.
Seguir estos consejos cuando diseñe anuncios y materiales de redes sociales mejorará en gran medida la calidad, los niveles de participación y la creatividad general de sus imágenes:
  • Haz uso de colores vivos y brillantes que se destacan.
  • Mostrar personas felices y activas ayuda con la dinámica y los sentimientos sobre tus gráficos.
  • El movimiento, la actividad y la emoción de las personas siempre atrae la atención y ayuda con los sentimientos transmitidos en general.
Todas estas reglas te ayudarán a crear gráficos excepcionales para publicidades. Si corresponde, usa la paleta de colores, la tipografía y otros elementos visuales que hayas utilizado en tu sitio web, marca y aplicaciones. Esto te ayudará a ser consistente en tus diseños y trabajará a su favor cuando trabajes bajo restricciones de tiempo.
Representación visual de anuncios y gráficos de redes sociales
Tus resultados deben corresponder a la dirección visual general del proyecto.

Nunca te comprometas a una fecha límite que no puedes cumplir

En ocasiones, cualquiera puede subestimar la cantidad de esfuerzo y trabajo que un proyecto puede tomar, por eso planificar cada paso es crucial al comienzo de un proyecto. Los objetivos y las metas realistas divididos en partes pequeñas son fundamentales para entregar un trabajo sólido a tiempo.
Benjamin Franklin lo expresó mejor: “Al no prepararse, te estás preparando para fracasar”.
En todo momento, nunca dejes de prepararte, y nunca dejes de anticipar la posibilidad de que haya subestimado el trabajo en términos del tiempo requerido para entregarlo. Aunque los clientes pueden tener fechas límites, tú debes tener las habilidades que te ayudarán a determinar si un proyecto es factible o incluso vale la pena considerarlo en primer lugar. Sin embargo, no permitas que esto sea una excusa para que no acepte un desafío personal que, en última instancia, podría ayudarte a ser un diseñador y gerente más hábil de tu tiempo.

Fuente: https://www.toptal.com/designers/product-design/30-d%C3%ADas-de-dise%C3%B1o-un-caso-de-estudio-de-marca/es

BY IVONA PETROVIC - UI DESIGNER @ TOPTAL (TRANSLATED BY YESICA DANDERFER)

Una Introducción a la Teoría y Complejidad de la Computabilidad

Te has preguntado alguna vez: ¿Cuál es exactamente el dispositivo en el que estás leyendo este artículo? ¿Qué es una computadora? La ciencia de la computación se remonta a un tiempo mucho antes de que se pensara en estos modernos dispositivos informáticos. En una industria donde las preguntas más frecuentes giran en torno a los lenguajes de programación, marcos y bibliotecas, a menudo damos por sentado los conceptos fundamentales que hacen funcionar una computadora.
Pero estas computadoras, que parecen poseer un potencial infinito— ¿tienen alguna limitación? ¿Hay problemas que las computadoras no pueden resolver?
Teoría de la computabilidad y complejidad
En este artículo, abordaremos estas preguntas alejándonos de los detalles de los lenguajes de programación y las arquitecturas de la computadora. Al comprender el poder y las limitaciones de las computadoras y los algoritmos, podemos mejorar la forma en que pensamos y razonar mejor sobre las diferentes estrategias.
La visión abstracta de la informática produce resultados que han resistido la prueba del tiempo, siendo tan valiosos para nosotros hoy como lo fueron cuando se desarrollaron inicialmente en la década de 1970.

Computabilidad

¿Qué es una computadora? ¿Qué es un problema?

En la escuela, a menudo se nos enseña un modelo mental de problemas y funciones que dice algo como esto:
_ Una función es un procedimiento que aplica a una entrada x para encontrar una salida f(x)._
Resulta que la definición matemática es diferente:
Una función es un conjunto de pares ordenados de modo que el primer elemento de cada par proviene de un conjunto X (llamado el dominio), el segundo elemento de cada par proviene de un conjunto Y (llamado co-dominio o rango) y cada elemento del dominio está emparejado con exactamente un elemento del rango.
Eso fue bastante. Pero, ¿qué significa eso exactamente?
Función
Esta definición nos dice que una computadora es una máquina para funciones informáticas.
¿Por qué?
Porque las computadoras transforman la entrada arbitraria a alguna salida. En otras palabras, resuelven problemas. Las dos definiciones de funciones, la que conocemos muy bien y la formal, coinciden para muchos propósitos prácticos.
Sin embargo, la definición matemática nos permite llegar a conclusiones interesantes tales como la existencia de funciones no procesables (es decir, problemas sin solución):
Por qué no todas las funciones se pueden describir como un algoritmo.

Reglas del Juego

Para ayudar con nuestros argumentos, imaginemos a las computadoras como máquinas que tienen una entrada, desarrollan una secuencia de operaciones y después de un tiempo, dan una salida.
Vamos a llamar a la entrada alfabeto de la máquina, que es un set de secuencia de caracteres de algún conjunto finito. Por ejemplo, el alfabeto de la máquina puede ser binario (0s y 1s) o podría ser el juego de caracteres ASCII. Cualquier secuencia finita de caracteres es una cadena—por ejemplo “0110.”
Además, representaremos el resultado de una máquina como una decisión binaria de aceptación y rechazo que se entrega una vez que la máquina (con suerte) finaliza su cálculo. Esta abstracción se ajusta bien a la definición matemática de funciones anteriores.
Computadora aceptar-rechazar
Dados estos parámetros, es importante caracterizar un tipo más: una colección de cadenas de caracteres. Tal vez nos preocupamos por el conjunto de cadenas de caracteres que acepta una máquina, o tal vez estamos construyendo una máquina que acepta cadenas de caracteres en un determinado conjunto y no en otros, o tal vez estamos preguntando si es posible diseñar una máquina que acepte todo en algún conjunto particular y no en otros.
En todos estos casos, un conjunto de cadenas de caracteres se denomina lenguaje—por ejemplo, el conjunto de todas las cadenas binarias que representan números pares o el conjunto de cadenas que tienen un número par de caracteres. Resulta que los idiomas, como los números, pueden ser operados con los operadores como concatenación, unión, intersección y otros similares.
Un operador importante es el operador estrella Kleene que también se usa con expresiones regulares. Esto se puede considerar como la unión de todos los poderes posibles del lenguaje. Por ejemplo, si nuestro idioma A es el conjunto de cadenas de caracteres { ‘01’, ‘1’ }, entonces un miembro de A* es la cadena de caracteres ‘0101111’.

Contabilidad

La última pieza del rompecabezas antes de demostrar nuestra afirmación de que no todas las funciones son computables es el concepto de contabilización. Intuitivamente, nuestra prueba mostrará que hay más idiomas; es decir, más problemas que posibles programas para resolverlos. Esto funciona porque el tema de si una cadena de caracteres pertenece a un idioma (Sí/No) es en sí misma un problema.
Más precisamente, nuestra prueba afirma que el conjunto de posibles programas es infinitamente contable, mientras que el conjunto de idiomas sobre un alfabeto es infinitamente incontable.
En este punto, puedes estar pensando “La infinidad es una idea bastante extraña en sí misma, ¡ahora tengo que lidiar con dos de ellos!”
Bueno, no es tan malo. Un conjunto contablemente infinito es uno que se puede enumerar. Es posible decir: este es el primer elemento, este es el segundo elemento y así sucesivamente, eventualmente asignando un número a cada elemento del conjunto. Toma el conjunto de números pares, por ejemplo. Podemos decir que 2 es el primero, 4 el segundo, 6 el tercero y así sucesivamente. Tales conjuntos son contablemente infinitos o contables.
Sin embargo, con algunos conjuntos como los números reales, no importa cuán inteligente seas; simplemente no hay enumeración. Estos conjuntos son incontablemente infinitos o incontables.

Muchos Programas de Manera Contable

Primero queremos mostrar que el conjunto de programas de computadora es contable. Para nuestros propósitos, hacemos esto al observar que el conjunto de todas las cadenas de caracteres sobre un alfabeto finito es contable. Esto funciona porque los programas de computadora son cadenas de caracteres finitas.
La prueba es sencilla y no cubrimos los detalles aquí. El punto clave es que hay tantos programas de computadora como, por ejemplo, números naturales.
Para reiterar:
El conjunto de todas las cadenas de caracteres sobre cualquier alfabeto (Ej., Conjunto de todos los programas informáticos) es contable.

Incontablemente, Muchos Idiomas

Dada esta conclusión, ¿qué pasa con los subconjuntos de estas cadenas de caracteres? Preguntado de otra manera, ¿qué pasa con el conjunto de todos los idiomas? Resulta que este conjunto es incontable.
_El conjunto de todos los idiomas sobre cualquier alfabeto es incontable. _
Una vez más, no cubrimos la prueba aquí.

Consecuencias

Aunque pueden no ser inmediatamente aparentes, las consecuencias de la incontabilidad de los idiomas y la contabilización del conjunto de todos los programas informáticos son profundas.
¿Por qué?
Supongamos que A es el conjunto de caracteres ASCII; los caracteres ASCII son solo los necesarios para componer un programa de computadora. Podemos ver que el conjunto de cadenas de caracteres que representan, por ejemplo, los programas de JavaScript son un subconjunto de A* (aquí, * es el operador estrella de Kleene). La elección de JavaScript es arbitraria. Dado que este conjunto de programas es un subconjunto de un conjunto contable, tenemos que el conjunto de programas de JavaScript es contable.
Además, consideremos que para cualquier idioma L podemos definir alguna función f que evalúe a 1 si alguna cadena x está en L y 0 en caso contrario. Todas esas funciones son distintas. Debido a que existe una correspondencia 1:1 con el conjunto de todos los idiomas y porque el conjunto de todos los idiomas es incontable, tenemos que el conjunto de todas esas funciones es incontable.
Aquí está el punto en profundidad:
Como el conjunto de todos los programas válidos es contable pero el conjunto de funciones no lo es, entonces debe haber algunas funciones para las cuales simplemente no podemos escribir programas.
Todavía no sabemos cómo son estas funciones o problemas pero sabemos que existen. Ésta es una realización humillante porque hay algunos problemas por los cuales no hay solución. Consideramos que las computadoras son extremadamente poderosas y capaces sin embargo, algunas cosas están fuera de su alcance.
Ahora la pregunta es: “¿Cómo son estos problemas?” Antes de continuar describiendo estos problemas, primero debemos modelar la computación de forma generalizada.

Máquinas de Turing

Uno de los primeros modelos matemáticos de una computadora fue desarrollado por Alan Turing. Este modelo, llamado máquina de Turing, es un dispositivo extremadamente simple que captura por completo nuestra noción de computabilidad.
Máquina de Turing
La entrada a la máquina es una cinta sobre la cual se ha escrito la entrada. Usando un cabezal de lectura/escritura, la máquina convierte la entrada en salida a través de una serie de pasos. En cada paso, se toma una decisión sobre si y qué escribir en la cinta y si se debe mover hacia la derecha o hacia la izquierda. Esta decisión se basa exactamente en dos cosas:
  • El símbolo actual debajo del cabezal y
  • El estado interno de la máquina, que también se actualiza cuando se escribe el símbolo
Eso es todo.

Universalidad

En 1926, Alan Turing no solo desarrolló la máquina de Turing sino que también tuvo varias ideas importantes sobre la naturaleza de la computación cuando escribió su famoso artículo, “Sobre números computables”. Se dio cuenta de que un programa de computadora en sí podría considerarse como entrada a una computadora. Con este punto de vista, tuvo la hermosa idea de que una máquina de Turing podría simular o ejecutar esa entrada.
Si bien damos por sentadas estas ideas hoy, en la época de Turing la idea de una máquina tan universal fue el gran avance que permitió a Turing desarrollar problemas sin solución.

Tesis de Church-Turing

Antes de continuar, examinemos un punto importante: sabemos que la máquina de Turing es un modelo de computación, pero ¿es lo suficientemente general? Para responder a esta pregunta, pasamos a la Tesis de Church-Turing, lo que da credibilidad a la siguiente declaración:
Todo lo computable es computable por una máquina de Turing.
Mientras Turing desarrolló la máquina de Turing como un modelo de computación, Alonzo Church también desarrolló un modelo de cálculo conocido como lambda-cálculo. Estos modelos son potentes ya que ambos describen la computación y lo hacen de una manera igual a cualquiera de las computadoras de hoy o para cualquier computadora. Esto significa que podemos usar una máquina de Turing para describir los problemas irresolubles que buscamos, sabiendo que nuestros hallazgos se aplicarán a todas las computadoras posibles.

Reconocimiento y Decidibilidad

Tenemos que cubrir un poco más de fondo antes de describir concretamente un problema sin solución, a saber, los conceptos de reconocedores de lenguaje y factores decisivos de lenguaje.
Un idioma es reconocible si hay una máquina de Turing que lo reconoce.
y
Un lenguaje es decidible si hay una máquina de Turing que lo decide.
Para ser un reconocedor de un idioma, una máquina de Turing debe aceptar cada cadena de caracteres en el idioma y no debe aceptar nada que no esté en el idioma. Puede rechazar o repetir esas cadenas. Para ser un factor de decisión, una máquina de Turing siempre debe detener su entrada aceptando o rechazando.
Aquí, la idea de detener la entrada es crítica. De hecho, vemos que los factores de decisión son más poderosos que los reconocedores. Además, un problema se puede resolver, o dicho de otra manera, una función es decidible solo si existe una máquina de Turing que decide el lenguaje descrito por la función.

Indecibilidad

Si alguna vez has escrito un programa de computadora, seguramente debes saber la sensación de estar sentado allí, solo mirando la computadora girar las ruedas cuando se ejecuta el programa. No se sabe si el programa tarda mucho o si hay algún error en el código que causa un ciclo infinito. Es posible que incluso te hayas preguntado por qué el compilador no verifica el código para ver si se detendría o se repetirá para siempre cuando se ejecute.
El compilador no tiene dicho control porque simplemente no se puede hacer. No es que los ingenieros de compilación no sean lo suficientemente inteligentes o carezcan de los recursos, es simplemente imposible verificar un programa de computadora arbitrario para determinar si se detiene.
Podemos probar esto usando la máquina de Turing. Las máquinas de Turing se pueden describir como cadenas de caracteres, por lo que hay un número contable de ellas. Supongamos que M1, M2, y así sucesivamente conforman el conjunto de todas las máquinas de Turing. Vamos a definir la siguiente función:
f(i, j) = 1 si Mi acepta <Mj>, 0 al contrario
Aquí, <M> es la sintaxis para la “codificación de cadena de M” y esta función representa el problema de producir 1 si Mi se detiene al aceptar Mj como entrada y salida 0 al contrario. Ten en cuenta que Mi debe detener (es decir, ser un factor decisivo). Esto es necesario ya que deseamos describir una función indecidible (es decir, problema sin solución).
Ahora, definamos también un lenguaje L que consiste en codificaciones de cadenas de máquinas de Turing que NO aceptan sus propias descripciones:
L = { <M> | M no acepta <M> }
Por ejemplo, alguna máquina M1 puede dar en la salida 0 para la entrada <M1&gt, mientras que otra máquina M2puede dar en la salida 1 para la entrada <M2>. Para probar que este lenguaje es indecidible, preguntamos qué hace ML, la máquina que decide el lenguaje L, cuando se le da su propia descripción <ML> como entrada. Hay dos oportunidades:
ML acepta <ML>
o
ML rechaza <ML>
Si ML acepta su propia codificación, entonces eso significa que <ML> no está en el idioma L. Sin embargo, si ese fuera el caso, entonces ML no debería haber aceptado su codificación en primer lugar. Por otro lado, si ML no acepta su propia codificación, entonces <ML> está en el lenguaje L, entonces ML debería haber aceptado su codificación de cadena de caracteres.
En ambos casos, tenemos una paradoja o, en términos matemáticos, una contradicción, que demuestra que el lenguaje L es indecidible; por lo tanto, hemos descrito nuestro primer problema sin solución.

Deteniendo el Problema

Si bien el problema que acabamos de describir puede no parecer relevante, puede reducirse a problemas adicionales irresolubles de importancia práctica, sobre todo el problema de detención:
El lenguaje de las codificaciones de las máquinas de Turing que se detienen en la cadena vacía.
El problema de detención se aplica a la pregunta de por qué los compiladores no pueden detectar nudos infinitos desde antes. Si no podemos determinar si un programa termina en la cadena vacía, entonces ¿cómo podríamos determinar si su ejecución daría como resultado un nudo infinito? En este punto podría parecer que agitamos nuestras manos para llegar a una conclusión simple sin embargo, nos dimos cuenta de que ninguna máquina de Turing puede decir si un programa de computadora se detendrá o permanecerá en un nudo para siempre. Este es un problema importante con aplicaciones prácticas y no se puede resolver en una máquina de Turing o cualquier otro tipo de computadora. Un iPhone no puede resolver este problema. Un escritorio con muchos núcleos no puede resolver este problema. La nube no puede resolver este problema. Incluso si alguien quisiera inventar una computadora cuántica, aún no sería capaz de resolver el problema de detención.

Resumen

En nuestro examen de la teoría de computabilidad hemos visto cómo hay muchas funciones que no son computables en ningún sentido ordinario de la palabra mediante un argumento de conteo. Definimos con precisión lo que queremos decir con computación, remontándonos a la inspiración de Turing a partir de su propia experiencia con lápiz y papel para formalizar la máquina de Turing. Hemos visto cómo este modelo puede calcular cualquier cosa que cualquier computadora actual o prevista para mañana pueda y nos dimos cuenta de una clase de problemas que no son computables en absoluto.
Aun así, la computabilidad tiene una desventaja. El hecho de que podamos resolver un problema no significa que podamos resolverlo rápidamente. Después de todo, ¿de qué sirve una computadora si su cálculo no va a terminar antes de que el sol se vuelva nova sobre nosotros decenas de millones de años en el futuro?
Dejando las funciones computables y los lenguajes atrás, ahora discutimos la complejidad de cómputo, examinando el cálculo eficiente y el famoso problema P vs. NP.

Complejidad

Lento vs. Rápido

Los científicos informáticos reconocen una variedad de clases de problemas y dos clases que nos importan incluyen problemas que las computadoras pueden resolver rápida o eficientemente, conocidos como P y problemas cuyas soluciones se pueden verificar rápidamente pero no se pueden obtener rápidamente, conocidas como NP.
Por ejemplo, supongamos que eres responsable de desarrollar algoritmos para un servicio de citas en línea y alguien plantea la pregunta: “¿Todos pueden obtener una cita?” La respuesta se reduce a emparejar individuos compatibles para que todos estén emparejados. Resulta que hay algoritmos eficientes para resolver este problema. Este problema está en el conjunto P.
Bueno, ¿y si quisiéramos identificar la hermandad más grande entre nuestros usuarios? Por hermandad, nos referimos a la red más grande de individuos que son compatibles entre sí. Cuando el recuento de usuarios es bajo, este problema se puede resolver rápidamente. Podemos identificar fácilmente, por ejemplo, una hermandad con 3 usuarios. Sin embargo, a medida que empezamos a buscar hermandades más grandes, el problema se vuelve cada vez más difícil de resolver. Este problema está en el conjunto NP.

Definiciones Formales

P es el conjunto de problemas que se pueden resolver en tiempo polinomial. Es decir, el número de pasos computacionales está limitado por una función polinómica con respecto al tamaño del problema. Sabemos que la pregunta “¿Todos pueden tener una cita?”, también conocida como problema de coincidencia bipartita, está en P.
NP es el conjunto de problemas que son verificables en tiempo polinomial. Esto incluye todos los problemas en P, por supuesto; sin embargo, no sabemos si esta contención es estricta. Conocemos problemas que son verificables de manera eficiente pero que no se pueden resolver de manera eficiente, pero no sabemos si el problema es verdaderamente insoluble. El problema de la hermandad es uno de esos problemas. Sabemos que podemos verificar la solución de manera eficiente pero no sabemos con certeza si podemos resolver el problema de manera eficiente.
Por último, NP-complete es el conjunto de problemas que son los problemas más difíciles en NP. Se les conoce como los más difíciles porque cualquier problema en NP se puede transformar eficientemente en NPC. Como resultado, si alguien identificara una solución eficiente a un problema en NPC, toda la clase de NP sería absorbida por P. El problema de la hermandad también está en NPC
P vs. NP
Por lo tanto, llegamos al problema de P contra NP. Muchos científicos informáticos y matemáticos creen firmemente que P y NP no son iguales. Si lo fueran, las implicaciones serían más allá de lo profundo. Gran parte de la infraestructura digital actual se basa en el hecho de que hay problemas en NP que no están en P. Si ese no fuera el caso, los métodos criptográficos por ejemplo, colapsarían de la noche a la mañana, permitiendo que una persona que posee una solución eficiente a un problema de NPC pueda subvertir incluso los protocolos de seguridad más estrictos.

Sutilezas de Trazabilidad

Para los principiantes en informática, la diferencia entre los problemas de emparejamiento y hermandad no parece ser un gran problema. De hecho, la diferencia entre un problema en P y un problema en NP puede ser muy sutil. Ser capaz de notar la diferencia es importante para cualquiera que diseñe algoritmos en el mundo real.
Considera el problema de la ruta más corta. Dadas dos ubicaciones, el objetivo es identificar el camino más corto entre ellas. Un iPhone calcula esto en cuestión de milisegundos. Este es un problema computacionalmente tratable.
Por otro lado, considera el problema del vendedor ambulante, donde el objetivo es visitar un subconjunto de posibles destinos que terminan en el origen mientras viajan la distancia más corta posible. Este problema es similar al problema de ruta más corta pero es NP-completo; también explica por qué la logística de la cadena de suministro es una industria de mil millones de dólares.
De hecho, podemos ser aún más sutiles. En lugar de pedir el camino más corto (P), podemos pedir el camino más largo sin nudos. Resulta que el problema de la ruta más larga también es NP-completo.
Hay muchos más ejemplos de esta sutil distinción, incluida la identificación de las coberturas de los vértices en los gráficos bipartitos vs. generales o la satisfacción de las fórmulas booleanas con dos y tres literales por cláusula. El punto es que no es inmediatamente obvio si un problema está en P o NP, por ello la razón del análisis del tiempo de ejecución es una habilidad crítica. Si el algoritmo que uno debe diseñar es para un problema en P, entonces sabemos que hay una solución eficiente. Si, por otro lado, el problema está en NP, entonces tenemos un caso fuerte para argumentar en contra de buscar una solución, porque el algoritmo en general, simplemente tomaría demasiado tiempo para resolver el problema.

Resumen

En este examen de complejidad, definimos las clases de problemas P y NP. P informalmente representa problemas que pueden ser resueltos eficientemente por una computadora, mientras que NP representa aquellos que son verificables de manera eficiente.
Nadie ha podido demostrar que P no es igual a NP. Si estas dos clases de problemas son equivalentes, es lo que se conoce como el problema P vs. NP y es el problema abierto más importante en la informática teórica actual, si no en todas las matemáticas. De hecho, en el año 2000, el Clay Math Institute denominó al problema P vs. NP como una de las siete preguntas abiertas más importantes en matemáticas y ha ofrecido una recompensa de un millón de dólares por una prueba que determina la solución a este problema.

Conclusión

En este artículo nos adentramos en los ámbitos de la computabilidad y la complejidad, respondiendo grandes preguntas como “¿Qué es una computadora?”. Si bien los detalles pueden ser abrumadores, hay una serie de aprendizajes profundos que vale la pena recordar:
  • Hay algunas cosas que simplemente no se pueden calcular, como el problema de detención.
  • Hay algunas cosas que no se pueden calcular de manera eficiente, como los problemas en NPC.
Más importantes que los detalles son las formas de pensar sobre computación y problemas computacionales. En nuestra vida profesional e incluso en nuestro día a día, podemos encontrarnos con problemas nunca antes vistos y podemos usar herramientas y técnicas probadas para determinar el mejor curso de acción.
Fuente:

Seguidores